里阿奴摩西-CSDN博客

原创高三日志

原标题高三志开坑 2017.09.02 23:47 高三，还是记录一下吧。 DATE EVENT HINT 07.22 退役 07.25-07.27 CodeM Final，Beijing 点赞 08.04-08.18 Codechef August Long Challenge 2017 高三可能都不会这么认真的打比...

2017-09-03 00:08:24 4244

原创 AFO & 博客已搬 manchery.co

抱歉，退役了，Blog下的留言我可能不会回答了吧。UPD. 博客已搬 [雯舞 - Manchery's Space](manchery.co) ——2018.05.25

2017-07-24 10:19:51 2585

原创 [中等题] Project Euler 608 Divisor Sums

2018-01-20 18:16:47 1018

原创 [简单题] Project Euler 601 Divisibility streaks

(k+1)|(n+k)(k+1) | (n+k) 就是 (k+1)|(n−1)(k+1) | (n-1) 这个函数就是最大的 kk 使得 1,2,⋯,k1,2,\cdots,k 都整除n-1吧随便容斥下咯#include#include#includeusing namespace std;typedef long long ll;inline ll Gcd(ll a,ll

2018-01-20 17:57:53 686

原创 [简单题] Project Euler 603 Substring sums of prime concatenations

直接考虑每一位的贡献，应该是一个 ai×i×(1+10+⋯+10n−i)a_i\times i\times (1+10+\cdots+10^{n-i}) 的形式，这就是个等比数列求和然后因为是循环串，还是个等比数列求和，就好了#include#include#includeusing namespace std;typedef long long ll;const int P

2018-01-20 17:54:56 647

原创 [杜教筛] Codechef January Challenge 2018 #SQRGOOD Simplify the Square Root

二分转化为μ2\mu^2的前缀和。然后转化为O(n13)O(n^{1\over 3})的运算，但是需要预处理μ\mu的前缀和，大力杜教筛求和。然后感谢阿爷教我把二分改成了迭代，小范围内一个一个挪，用rho求μ(n)\mu(n)，然后就能卡进去了。复杂度似乎是萎的吧。#include#include#include#include#include#include#defi

2018-01-19 14:16:38 638

原创 [整体二分] Codechef January Challenge 2018 #MONSTER Killing Monsters

整体二分，然后问题变成，子集加，单点查询，然后像CTSC吉夫特可以用经典的二进制分高位低位的搞搞。调个参，大概是高5位低12位。不知道在线怎么做。#include#include#include#include#define pb push_backusing namespace std;typedef long long ll;inline char nc(){

2018-01-19 14:11:46 795

原创 [后缀数组后缀树] Codechef January Challenge 2018 #KILLKTH Killjee and k-th letter

建出后缀树，记录每个子串的出现次数，然后二分下答案在哪个子串中就好了退役选手不会写后缀自动机#include#include#include#include#define pb push_backusing namespace std;typedef long long ll;inline char nc(){ static char buf[100000],*p1=b

2018-01-19 14:07:23 682

原创 [数学 FFT] Codechef July Challenge 2017 #APRPS Irrational Root

跟 51Nod 1356 代数数的次数是一样的不过这里都是质数也就是就是 2n2^n 关键是输方案这个不一定有二次剩余感谢sxt 一个一个数加进答案转化成已知F(x)F(x)，求F(x+a√)F(x+\sqrt a)和F(x−a√)F(x-\sqrt a)的系数这个推一下就是一个FFT拷了myy的板子自己的太慢了QAQ#include<cstdio>#include<cs

2017-07-24 10:18:34 687

原创 [杂题] Codechef July Challenge 2017 #MULDIG Multiplication Program

大意是把二元运算化成一元运算感谢sxt的帮助剩下的看代码注释吧 //我觉得蛮清楚了唯一不爽的是没想到临时变量这么多 mmp#include<cstdio>#include<cstdlib>#include<algorithm>#include<vector>#define pb push_backusing namespace std;int B;struct abcd{ i

2017-07-24 10:12:29 529

原创 [杂题] Codeforces 830C Round #424 Div1 C. Bamboo Partition

随便搞搞吧#include<cstdio>#include<cstdlib>#include<algorithm>using namespace std;typedef long long ll;#define read(x) scanf("%d",&(x))const int maxn=200005;const int P=1e9+7;const int N=505;int n,a[N]

2017-07-24 10:05:45 507

原创 [FWT] UOJ #310. 【UNR #2】黎明前的巧克力

这是若干个 2xai+12x^{a_i}+1 的东西的卷积然后这个FWT一下发现每一项只有 −1-1 或 33 那么卷积的FWT每一项就是若干个 −1-1 和 33 的乘积这个不好求直接加在一起FWT，那么我们得到了每一项 −1-1 和 33 的和因为只有这两个取值，可以直接解方程有多少个 −1-1 和 33 然后快速幂再乘起来#include<cstdio>#include<

2017-07-24 09:59:50 893

原创 [DP] UOJ #311. 【UNR #2】积劳成疾

fi,jf_{i,j}表示长为 ii 的区间最大值是jj 的答案转移就枚举最左边的最大值在区间的位置前缀和优化下就好了好像也可以fi,j,kf_{i,j,k}表示前 ii 个，末尾 KK 个中最大值在 jj ，最大值是 kk，有点复杂？#include<cstdio>#include<cstdlib>#include<algorithm>using namespace std;typ

2017-07-23 14:10:32 615

原创 [色多项式] UOJ #308. 【UNR #2】UOJ拯救计划 & SRM 717 div1 AcyclicOrientation

一个图的 kk 染色数是关于 kk 的 nn 次(?) 多项式称为色多项式那么这里模6 我们只要知道模2和模3的值然后分类讨论下就好了一张图的0染色数是0，1染色数等于[m=0][m=0]，2染色数与二分图的联通块个数有关#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>#define

2017-07-23 14:07:33 840

原创 [线代小记] 树形图求和

未经允许搬了过来代码略丑#include<cstdio>#include<cstdlib>#include<algorithm>using namespace std;typedef long long ll;inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+f

2017-07-23 13:55:01 878

原创 [高斯消元矩阵的秩] 51Nod 1356 代数数的次数

请教了比利首先 2n2^n 次项是没有问题的，比如2√+3√\sqrt2+\sqrt3，可以构造f(x)=(x+2√+3√)(x+2√−3√)(x−2√+3√)(x−2√−3√)f(x)=(x+\sqrt2+\sqrt3)(x+\sqrt2-\sqrt3)(x-\sqrt2+\sqrt3)(x-\sqrt2-\sqrt3) 这个不是最优解最优解应该是构造这样一个矩阵每一行代表一个质因子

2017-07-23 13:50:12 872 1

原创 [数学二分图匹配] SRM 456 div1 FunctionalEquation

本来想自己再推一下的，但是退役了也就弃坑了未经允许的搬了搬题人的题解// BEGIN CUT HERE #include<conio.h>#include<sstream>// END CUT HERE #include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#in

2017-07-23 13:41:16 645

原创 [杂题] Codechef SnackDown 2017 Onsite Final #MINIMAX Minimax

最小值的最大值小于等于最大值的最小值那么只要有一行一列最小值等于最大值，那么矩阵就合法如果我们枚举这一行和这一列，那么最小值最大值一定就是他们的交点那么再枚举交点最后的值是多少这样复杂度是O(n4)O(n^4) 换一下先枚举值再枚举位置可以去一个代价最小值 O(n2logn)O(n^2\log n)#include<cstdio>#include<cstdlib>#in

2017-07-23 13:32:53 568

原创 [数论] LOJ #508. 「LibreOJ NOI Round #1」失控的未来交通工具

这种非简单路一般转化成任意一条路加上若干环这里大概是任意一条路加上若干环长的gcd 任意一条路可以弄出任意一颗生成树？但是这里实际上只需要一个带权并查集详见官方题解#include<cstdio>#include<cstdlib>#include<algorithm>using namespace std;typedef long long ll;typedef pair<

2017-07-23 13:26:30 1115

原创 [反演] LOJ #509. 「LibreOJ NOI Round #1」动态几何问题

μ2(n)=∑d2|nμ(d)\mu^2(n)=\sum_{d^2|n} \mu(d) 然后就是xjb推反正退役了我也就弃坑了 95分代码复杂度分析及优化详见官方题解#include<cstdio>#include<cstdlib>#include<cmath>#include<algorithm>using namespace std;typedef long long l

2017-07-23 13:22:57 1224

原创 [链分治] LOJ #511. 「LibreOJ NOI Round #1」验题

直接按照字典序类似逐位确定先从后往前诸位确定确定答案和当前的LCP 然后在从前往后逐位确定然后就转化为一个某些不能选某些必须选某些随意的独立集计数链分治#include<cstdio>#include<cstdlib>#include<algorithm>#include<vector>#define pb push_backusing namespace std;

2017-07-23 13:18:07 756

原创 [DP 分块] UOJ #300. 【CTSC2017】吉夫特

DP的转移是一个子集和的形式直接做是3183^{18} 按照高9位低9位分块可以做到29×39=692^9\times 3^9=6^9#include<cstdio>#include<cstdlib>#include<algorithm>using namespace std;#define read(x) scanf("%d",&(x))const int N=1<<18;cons

2017-07-23 13:15:37 696

原创 [计数] 美团 CodeM 复赛排列

#include<cstdio>#include<cstdlib>#include<algorithm>using namespace std;typedef pair<int,int> abcd;typedef long long ll;#define read(x) scanf("%d",&(x))const int P=1e9+7;inline ll Pow(ll a,int b){

2017-07-11 22:35:35 654

原创 [数论] LOJ #510. 「LibreOJ NOI Round #1」北校门外的回忆

这个题跟树状数组没有半毛钱关系首先这是一个最低位翻倍的过程，如果这一位最终会变成 00 ，那么步数是 O(logn)O(\log n)的？要是这一位不能变成 00 ，也就是在环上跑了，似乎跑到环上的步数也是 O(logn)O(\log n)的？然后就变成了，修改要是跑到 00 就暴力跑，跑到环上，询问照样设某个修改最早到环上的起点是w+z×kmw+z\times k^m，那么会对 w

2017-07-11 22:29:55 989

原创 [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends

两道类似的题 819D考虑一个人应该能够观察的位置 ti,(ti+S)modT,(ti+2S)modT⋯t_i,(t_i+S)\bmod T,(t_i+2S)\bmod T\cdots 这个应该是形成 gcd(S,T)\text{gcd}(S,T) 个环，每个环是长度 TgT\over g 然后把同一个环的一起处理，把点放到环上，那么沿环的方向到下一个点为止应该都是归到这个点答案里面的#inc

2017-07-11 22:22:39 619

原创 [二分图匹配线段树] Codeforces 573D Round #318 [RussianCodeCup Thanks-Round] (Div. 1) D. Bear and Cavalry

如果没有限制，显然根据排序不等式当每个点最多有一个限制不能选的时候，有一个很重要的性质性质:i对应的点与i的距离<=2 证明: 设有一种情况i对应i+3 i—–(i+3) i+1—(i+2) i+2—(i) i+3—(i+1) 那么,对于i,i+1来说,必定在(i–i+2),(i+1–i+3)中有一个限制必选,否则交换i,i+1更优同理,(

2017-07-11 22:12:27 492

原创 [分块] Codeforces 436F Zepto Code Rush 2014 F. Banners

可以转化成区间加，询问ai×ia_i\times i的最大值这个不好维护，分块，零散的加，直接重构整块，否则在块上打标记同时我们在块上还要维护当前最大值所在的 ii 和接下来至少要整块加多少次才能使得最大值变化每次在块上打标记，当达到临近就重构更新最大值，注意这个最大值随着全局加肯定是单调右移的，那么重构复杂度也是对的#include<cstdio>#include<cstdlib>

2017-07-11 22:09:21 338

原创 [最小生成树] Codeforces 632F Educational Codeforces Round 9 F. Magic Matrix & SRM 687 div1 AllGraphCuts

Magic Matrix把aa矩阵当成邻接矩阵，设bb为两点间路径最大值的最小值，那么ai,j≥bi,ja_{i,j}\ge b_{i,j}，然后ai,j≤max(ai,k1,ak1,k2,⋯,akm,j)a_{i,j}\le \text{max}(a_{i,k_1},a_{k_1,k_2},\cdots,a_{k_m,j})，所以ai,j≤bi,ja_{i,j}\le b_{i,j} 那么a=b

2017-07-09 08:09:30 459

原创 [递推] Codeforces 660E Educational Codeforces Round 11 E. Different Subsets For All Tuples

对于一个确定串ss，求不同子序列的个数有经典dpfi,si=∑jfi−1,jf_{i,s_i}=\sum_j f_{i-1,j}fi,j=fi−1,j,j≠sif_{i,j}=f_{i-1,j},j\neq s_i因为转移都是形式一样的我试着把所有串的fif_i都加起来，然后就发现FjF_j除了j=ϕj=\phi之外都是一样的，然后就记录两个量，然后就递推出来了#include<cstdio>

2017-07-09 07:52:53 491 2

原创 [期望] UOJ #214. 【UNR #1】合唱队形

首先考虑如果要完成指定 kk 个课程，那么期望应该是 Fk=∑k−1i=01k−iF_{k}=\sum_{i=0}^{k-1} {1\over k-i} 令 ftf_t 表示 tt 时刻之前要求未被完成的概率令 pS,tp_S,t 表示 tt 时刻之前位置集合 SS 未被完成的概率然后瘦腿一发 E======∑t=0∞ft∑t=0∞∑S(−1)|S|(1−pS,t)∑t=0∞−∑

2017-07-06 16:30:41 821

原创 [DP优化] POJ 1160 Post Office

另解：四边形不等式优化考虑这个最优解关于段数是凸的，那么我们不限制段数，而是给每段一个额外的权值，随着这个权值单调变化，最优解的段数也会单调变化，二分出最优解是 mm 段就好了这个的本质是二分出那个凸函数在 mm 上的斜率然后这个dp是满足决策单调性的复杂度O(nlog2n)O(n\log ^2n)#include<cstdio>#include<cstdlib>#include<algo

2017-07-06 15:53:43 517

原创 [单调栈线段树] Codeforces 407E Round #239 (Div. 1) E. k-d-sequence

首先肯定是一段模 dd 相同的数然后枚举左端点那么右端点应该满足条件数字不重复出现且 maxvl,r−minvl,r≤r−l+kmaxv_{l,r}-minv_{l,r}\le r-l+k，这个最大最小值是除过 dd 的也就是maxvl,r−minvl,r−r≤k−lmaxv_{l,r}-minv_{l,r}-r\le k-l 左端点边挪边用单调栈维护最大最小值入栈出栈就线段树上区间

2017-07-05 20:16:13 510

原创 [递推 || 容斥 FFT] SRM 717 div1 DerangementsStrikeBack

首先像我这种无脑的人可以大力上fft fin!=∑j=0i(−1)j(ij)(n+i−j)!n!{f_i \over n!}=\sum_{j=0}^i (-1)^j {i\choose j} {(n+i-j)!\over n!} 然而考虑经典错排的递推公式 dn=(n−1)(dn−1+dn−2)d_n=(n-1)(d_{n-1}+d_{n-2}) 这个东西的递推式是把第nn个和n−1n-1

2017-07-05 19:50:22 443

原创 [贪心构造] SRM 717 div1 ScoresSequence

首先他保证图唯一确定，那么可以把图给构出来类似这个题，按照出度从大到小排序，出度最大那个点怎么分配，类似无向图可图判定，应该是向出度小的点连，使得出度大的向他连，让出度大的出度减小// BEGIN CUT HERE #include<conio.h>#include<sstream>// END CUT HERE #include<cstdio>#include<cstdlib>

2017-07-05 19:11:09 361

原创 [最短路主席树 Hash] 51Nod 算法马拉松26 E Travel

跟这个题一毛一样，那个题还高明一点，还会进位#include<cstdio>#include<cstdlib>#include<algorithm>#include<queue>#include<map>using namespace std;typedef unsigned int uint;typedef unsigned long long ull;inline char nc(

2017-07-05 19:02:37 485

原创 [FWT] 51Nod 算法马拉松26 A A国的贸易

相当于每次每个点会变成自己和与自己相差一个二进制位的数的和直接FWT 快速幂#include<cstdio>#include<cstdlib>#include<algorithm>using namespace std;typedef long long ll;inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; r

2017-07-05 18:59:24 509

原创 [通信题] JOI Open Contest 2017 Amusement Park

题目大意：这是一道通信题第一个程序输入一张无向图的点和边再给一个2^60以内的数第一个程序要给每个点赋值0/1 第二个程序也会读入这张图然后读入当前点编号以及当前点的值，其他点的值一律不知，每次可以调用一个函数走向一个相邻的点，并得知这个点的值，120步以内得出只有第一个程序知道的那个数VIEW PROBLEM - AMUSEMENT PARK (JOI17_AMUSEMENT_P

2017-07-05 07:56:07 773

原创 [几何扫描线最大子段和] JOI Open Contest 2017 Bulldozer

题目大意：给出平面上n个带权点，有正有负，求平面上两条平行直线之间的点权和最大是多少 VIEW PROBLEM - BULLDOZER (JOI17_BULLDOZER)直接枚举斜率，点按照距离排序后是一个最大子段和问题然后考虑扫描线旋转斜率，两个点相对关系变化只会发生在斜率与两点连线平行的情况，那么两点位置swap一下，更一般的如果是一段都满足这个，那么这一段要reverse一下就是把两

2017-07-05 07:50:00 520

原创 [最短路 Bfs 二维线段树] JOI Open Contest 2017 Golf

题目大意：给出平面上n个不相交的矩形障碍，以及起点和终点，要求从起点走到终点的折线段段数最少 VIEW PROBLEM - GOLF (JOI17_GOLF)首先最优解肯定可以只在矩形边所在的直线以及过起点终点平行坐标轴的直线上移动先预处理出矩形边界能够左右上下延伸的最远距离，转化成一些线段，可以扫描线加线段树然后就直接bfs，关键操作是找出所有跟当前线段相交的且没被走过的线段，可以把线段

2017-07-05 07:44:48 620

原创 [分块随机Hash] Romanian IOI 2017 Selection #6 Jolteon

传送门问有多少个区间，出现过的数出现次数都是奇数给每个数随机一个hash值然后区间中所有数的xor和和所有pre<l≤i≤rpre< l \le i \le r的数的异或和相同那么就合法枚举右端点，新增一个数会对一段造成影响变成区间异或，区间是否存在一个数，分块维护#include<cstdio>#include<cstdlib>#include<algorithm>

2017-07-01 22:41:16 775

USACO全部译题

空空如也