/ 比赛

NOIP2017 集训散记

炮艇大赛之正式赛

EZOJContests/1330/A
做这题只需要知道一个事情:相邻的两个人先相遇。然后优先队列模拟就可以了。正常的想法!多么自然的思路!我偏偏就没想到!

还有另外一种做法。最后剩下的人一定是编号为nn的,那就变换一下参考系,碰到零点的人淘汰。再提取出那些不会被倒着跑的人干掉,能到达零点的那些人(显然有两组),再考虑同向的这些人谁能到而且最晚到。

从距离短到长加人,维护一个编号递减的单调栈,开一个set维护在栈中的人最晚到达的时间。加入的人看栈中最晚到达的会不会比自己晚,这样就可以判断能否到达零点;如果能到达,那么就把自己加入栈中。最后栈中剩下的时间最长的就是最后到达的。

一个小细节:在求同向的人能否到达终点时,这个人的编号只需要比上一个能到达终点的同向的人后面的反向的人的编号大就可以了。

匹配

EZOJContests/1330/B
树形DP。我怕转移超时,又看模数这么NTT,就NTT了一波,果然超时了。

结果是,暴力转移就能O(nm)O(nm)

转移相当于是两两子树合并。分几种情况讨论贡献:

  • 至少有一棵子树的匹配数是大于等于mm的:总时间复杂度为O(mxi)=O(m\cdot\sum{x_i})=O(nm)$;
  • 两棵都小于mm
    • 合起来小于mm:和下面这种情况一起讨论;
    • 合起来大于mm:子树内部相当于每两个点在LCA处被统计一次,大小为kk的子树时间复杂度为kk;而这里两棵子树都小于mm,故总大小<2m<2m,最多有nm\frac{n}{m}次这样的合并,总时间复杂度为O(nm(2m)2)=O(nm)O(\frac{n}{m}\cdot(2m)^2)=O(nm)

所以直接搞就可以AC了。

前缀min和

EZOJContests/1330/C EZOJContests/1310/B
只需要维护区间的一个信息:区间的答案。设为sum

我们要让每一个节点能在给定左边的初始min的情况下O(logn)O(\log n)的求出答案。设这个函数为int ask(node x,int min)。分两种情况讨论:

  • 如果min小于等于lson->min:左儿子全部铲平,递归调用右儿子;
  • 如果min大于lson->minmin对右儿子没有影响,所以右儿子被左儿子铲掉的部分没有变化,答案就是ask(lson,min)+(sum-lson->sum)

这个实际上是一个二分的过程。

Maze

EZOJContests/1331/A
我比较没有水平,考试的时候直接上了支配树,忽略了这道题拥有的众多优秀性质。

解法1
如上所述,Lengauer-Tarjan求支配树即可。

解法2
Tarjan求割点,注意子树要包含目标点。

解法3
问题相当于求枚举空地,问将其变为障碍点后是否仍然存在合法路径,如果不存在,那么这就是一个必经点。如果不存在,那在障碍点上八联通搜索,一定有一条八联通的路径分割这张图,比如说就用左上-右下。那就两次BFS,再枚举空地O(1)O(1)看是否能联通左上角和右下角。

解法4
BFS两次,尽可能不走同一条路,实在没办法再过必经点。如何保证正确性?

不遗漏显然。

考虑路径A、B,对于某一个非必经点,A经过了,我们想要让B没有经过,那么只要保证在这个点之前的最后一个A和B的交点上,A的选路方法与B的不同。也就是说,我们要构造两个不同的选择顺序,使得在有不少于两个选择的时候这两个选择顺序总会做出不同的决策。

举个例子,A:上右下左;B:左下右上。

或者感性地理解一下,就是两条路尽量往不同的方向走。

道路建设

EZOJContests/1331/C
最小生成树的最常用求法是Kruskal按边从小到大贪心插入。然而,在处理这样一种问题的时候,可以考虑用一个略劣于O(eloge+eα(n))O(e\log e+e\cdot\alpha(n))的的做法。

这是一个区间问题,当然要先把边排好序。如果从小到大添加边,那么删去[1,l1][1,l-1]后的[l,r][l,r]内生成树的信息是无法快速维护的。

考虑Kruskal的操作过程,在添加完[1,l][1,l]这些边之后,前面的边选/不选是已经确定的了,与后面继续添加进来的边无关。也就是说,维护从每个点开始的选边情况,添加右端点的限制是非常容易的。

如何维护从每个点开始的选边情况?自然地,我们有两种思路:

  • 一开始把所有边加入,然后一条一条删除,记录每次删除前的选边信息;
  • 一开始一条边都没有,一条一条加入,记录以这条边为Kruskal起点的选边信息。

第二种做法,相当于从大到小插入。如果从大到小插入,新加入的边一定会被选上;如果新加入的边的两个端点本来就被连上了,那就把连接这两个点的路径上边权最大的边删掉。这个操作用LCT维护可以做到O(nlogn)O(n\log n)

考虑每次最多删掉一条边,加入一条边,因此总的复杂度有保证;如果强制在线,那就用可持久化数据结构维护一下就可以了。

当然,用LCT做最小生成树是不需要按边大小顺序加入的。这也算是另一种O(nlogn)O(n\log n)的最小生成树求法吧。

2048

EZOJContests/1332/B

这题本身不难,感觉和状压也没什么关系。但是有两个值得回顾的问题。

首先比赛时我脑子一抽,觉得2132^{13}非常大,遂用long long来存下两侧的状态。状态数那么庞大怎么办?我想了一个贪心,好不容易写完,发现贪心不对!最后没办法,写了一个优化过的暴力搜索,因为这题用的是子任务,一分都没水多。白白浪费了两个小时,这些时间完全可以拿去过A题啊!

考完发现数据原来这么小。我改成了广搜,在记录哪些点被更新时,我开了一个set<int>来存,多一个log\log总比跑满2132^{13}个状态好吧?但就这一个log\log,导致后面80分的子任务整个过不了!

问一波yww,“我没有用数据结构啊?记忆化深搜,不存在这个问题。”“那广搜怎么办呢?”“直接用队列搞一搞就行了啊?”

于是我就发现,用队列记录被更新的状态,并不会导致复杂度增加!同样的,在做插头DP的时候,只要状态可以用数组存下,那就完全不需要用哈希表。

这就是我受到的一点启发吧。

sequence

Baltic OI2004 BZOJ1367 EZOJContests/1333/C
这道题是被用在2005年黄源河的左偏树的论文里当例题,但是这题并不一定要用左偏树做。

考虑一些简单的情况,比如说:

  • {an}\{a_n\}递增:取bi=aib_i=a_i就好了。
  • {an}\{a_n\}递减:取中位数!

下面证明一个莫名其妙的结论(感谢zwl同学的指点):

{an}\{a_n\}的最优答案为{u}\{u\},对于任意的合法方案{v},{cn}\{v\},\{c_n\}使得uvc1u\leq v\leq c_1{cn}\{c_n\}不比{v}\{v\}优。

归纳证明。根据归纳假设,{cn}\{c_n\}的第22nn项都可以变为c1c_1而不会变差。如果变差了,那就说明最后n1n-1个元素的最优解>c1u>c_1\geq u,如果后面n1n-1项直接取最优解,会得到一个比{u}\{u\}更优秀的方案,与假设矛盾。然后考虑式子的几何意义,uu一定是在这个距离和函数f(x)=i=1nxaif(x)=\sum_{i=1}^n\left|x-a_i\right|的最高点,而这个距离和函数是个凸函数,因此{c1}\{c_1\}不会比{v}\{v\}好。证毕。

如果数列{an}\{a_n\}[1,m][1,m]上的答案是u,u,...,uu,u,...,u,在[m+1,n][m+1,n]上的答案是v,v,...,vv,v,...,v,现在考虑怎么合并这两个答案:

  • uvu\leq v:直接合并就好;
  • u>vu>v:设最终答案为{bn}\{b_n\}。由于对前面有影响的就是bnb_n的取值,所以如果能够bn>ub_n>u,则i[1,m],bi\forall i\in[1,m],b_i能取uu,那{bn}\{b_n\}就不是最优答案了,所以只能bmub_m\leq u。根据前面证明的结论,此时bi=bmb_i=b_m不会使答案更差。同理,[m+1,n][m+1,n]也能全部变成bm+1b_{m+1},现在要考虑的就是bmb_mbm+1b_{m+1}的取值。请在心中想象一根数轴,bmb_muu的位置,bm+1b_{m+1}vv的位置,而且u>vu>v。现在移动bmb_mbm+1b_{m+1},目标:bmbm+1b_m\leq b_{m+1}。同时,bmb_m偏离uu越多,答案越差;bm+1b_{m+1}偏离vv越多,答案越差。那移动后的结果是……bm=bm+1b_m=b_{m+1}!如果最终的{bn}\{b_n\}一一个常数数列,那最佳的取值方案,就是{an}\{a_n\}的中位数。

用上这个结论,合并后的最优的答案在一半情况下是常数数列,使得两个序列在合并之后可以作为一个新的合并前子序列。那思路大概就出来了:我们需要维护一不下降的队列,队列中的每一个元素代表一个区间的最优值。考虑在末尾追加一个元素,只要末尾的两个元素下降,就合并,一直合并到新队列仍然单调不降。

怎么维护中位数?考虑已经在队列中的区间,他们被合并后的中位数一定不大于当前的中位数,所以用堆维护小一半(向上取整)的元素即可;但是新加进来的区间是要求得到它的全部元素的信息的。一般来说,新加进来的区间,都是单点,单点就是全部信息。

树上怎么做?假如说树上要求父亲大于等于儿子,那同样可以推出一个结论:

设一个子树取最优答案时,子树的根的取值为uu,且子树的根所在的某一个极大连通块G=(V,E)G=(V,E)的取值均为uu;改变GG的取值为另一合法方案TVZT\in V\rightarrow\mathbb{Z},且v,uvminxVT(x)\exists v,u\leq v\leq\min_{x\in V}{T(x)},则TT不比全取vv优。

直观理解,就是父亲和儿子一样高,如果有一种方案让子树中最低的节点都比在一个平面上的最优高,那不如把整个子树放平成最低节点的高度。

同样归纳证明。设最低(权值最小)的节点为xx,那么把其他点的权值设为xx的权值不会让答案变差。再根据所有点取相同值的时候中位数最优,得此时答案没有vv优。

于是做法又出来了:如果把权值相同点的称作在一个块里(显然连通),那么每次只需要找子树的根所在块能连到的比自己值域大的块,合并之。能否用堆来维护中位数?当然可以!只是我们需要按从大到小的顺序来合并。对于一个块,他能合并到当前子树根所在块当且仅当它是子树根节点能连到的块中取值最大的一个,且这个块的取值比当前子树根所在块小。那么当前子树的其它块都没有它大,它能连到的子块也没有它大,它的大一半元素就没有用了。所以只需要堆维护小一半(向上取整)即可。

实现细节
每次要找一个块连到的所有块中的最大取值的那个块,这个也可以用一个可并堆维护。一旦把某个块并入根所在块,那也把它还没有合并的儿子并入自己还没有合并的儿子中去。

Point Pairs

EZOJContests/1334/A
对两两形成点对的点之间连边。考试的时候一看是一般图最大匹配我就弃了。

图的确不是二分图,但是它也具有一些特殊的性质啊,不然怎么做?要做此题,得先观察出仅适用于这道题的一个结论:一个连通块存在完美匹配当且仅当连通块内点个数为偶数。

我想了一个证明:

  • 对于任意连通无向图总能找到一个点,使得删去这个点后的图仍然连通。感谢owen补充了这一个必要的引理。
    • owen的证法:考虑将无向图按点双连通分量缩点,然后将割点提取出来,向点双连边,这样能得到一棵含有两种不同点的树。首先这棵树连通,每个点度数1\geq1;然后一定有点度数=1=1,否则总度数将2n\geq2n,使得边数n\geq n,图就不为树了。选择一个度数为11的点,如果它就是一个点,那就可以删掉,原图仍然连通;如果它是点双,那就任选一个它里面的点。
    • 我的证法:假设任意删掉一个点都会导致图不连通。现构造一个序列PP,它前两项为两个不同的点。序列PP满足,删去PP中最后一个点后PP中剩下的点仍然连通。
      • 设现在序列长度为nn。找一个点Pn+1P_{n+1}使得在删去PnP_n之后Pn+1P_{n+1}P1,P2,...,Pn1P_1,P_2,...,P_{n-1}均不相连。如果不存在这样的点,那每个点都能连到P1,p2,...,Pn1P_1,p_2,...,P_{n-1}这个连通块中,则删去PnP_n不影响图的连通性,与假设矛盾。点Pn+1P_{n+1}在删去PnP_n前与P1,P2,...,Pn1P_1,P_2,...,P_{n-1}连通,而删去PnP_n后不与P1,P2,...,Pn1P_1,P_2,...,P_{n-1}连通,说明PnP_{n}P1,P2,...,Pn1P_1,P_2,...,P_{n-1}没有经过Pn+1P_{n+1}的简单路径(无重复点),那么在删去Pn+1P_{n+1}P1,P2,...,PnP_1,P_2,...,P_{n}仍然连通。故归纳假设对PP长度为n+1n+1时成立。
      • 这样就能构造出一个无限长的序列,而序列中的元素各异,与图中的点数有限矛盾。原引理得证。
  • 对于一个存在完美匹配的连通块,现在加入一个新的点AA,则该点未匹配。由于连通,AA必然连到该块内某点CC,那么可以把CC的匹配点设为AA,从而CC的原匹配点DD变为未匹配点。这样操作,就实现了“未匹配点的跳跃”,未匹配点可以跳着走。如果有三点在同一条直线上,则未匹配点可以达到所有的点。
  • 再加入一个点BB。分情况讨论:
    • 在加入BB之前,所有的点都可以被匹配点达到,那么把匹配点移动到与BB相连的一个点处,然后BB和那个未匹配点就可以匹配上了,有完美匹配。
    • 在加入BB之前,不是所有点都可以被达到:
      • 加入BB之后,仍然没有三点共线:每个点最多只与两个点相连,则图构成了环或者链;由于总共有偶数个点,必然存在完美匹配。
      • 加入BB之后,有三点共线:
        • AA在这个三点共线中:直接AABB匹配即可。
        • AA不在这个三点共线中:考虑改变加入顺序,先加入BB,再加入AA
  • 综上,对于一个2n2n个点的连通块,可以删点,递归求完美匹配之后再加点。故一个连通块存在完美匹配当且仅当连通块内点个数为偶数。

如果直接建图,边数会比较大。可以只添加一个点和旁边直接能到的点之间的边;为了保证删去某个点后的连通性,再向隔一个的点连边。

当然,另一种经典的建图方式就是以横纵坐标为点,以原来的点为边。然后将问题转化为求边数是否为偶数。

最短路径

EZOJContests/1334/C
这题非常明显的线段树。但是要维护什么信息呢?

假设一个询问横跨了一个节点的中间,那无论它怎么走,都至少要跨过一次中间;那就预处理出中间那个柱子到两边的最短距离,然后枚举经过了柱子上的哪个点。如果一个询问没有横跨一个节点的中间,那它也可能绕了过来,同样枚举经过了柱子上哪个点,然后递归给儿子处理。时间复杂度O(W2Hlog2(WH))O(WlogH)O(W^2H\log^2{(WH)})-O(W\log H)

另一种做法基于分块。首先预处理出每个柱子自己到自己的最短距离(一个10×1010\times10的矩阵),然后在块内做ST表,得到块左边到块右边的10×1010\times10距离矩阵。对于每一个询问,块内块外转移。块大小为SS的话,时间复杂度应该是O(W2HlogS)O(W2(logS+HS))O(W^2H\log{S})-O(W^2(\log S+\frac{H}{S})),跑得飞快。

循环移位

EZOJContests/1335/C
显然用SAM。假如一个节点对某个字符有转移,它所代表的起始区间中以该字符为起点的子串都满足条件。

设子串为cTcT,则要求TcTc也是子串。如果有一个节点刚好代表TT,那就要特殊判断了。最终的解决办法其实并不是容斥,而是将它归为某一种情况特殊处理。比如说,在计算某个节点的时候,不要计算p->pos-p->len这个位置开始的子串,而是直接帮父亲特殊判断。

memory

EZOJContests/1337/A
显然对ll状压,然后DP。设f[S]f[S]为问过的位置集合为SS时,期望还要多少步猜出来,则答案就是f[]f[\varnothing]。再预处理出问过位置集合为SS时,哪些串一定可以辨别出来。这个预处理卡了我很久。

zwl的做法是,预处理出每个串每个位置与哪些串该位置不同,从而知道在选择这个串的哪些位置的时候可以将这个串与其它串完全分辨出来,从而知道在选择某些位置的时候哪些串可以辨别出来。O(n2l)O(n\cdot2^l)

另一种做法,算出每个串其它串哪些位置相同,这个位置相同集合的子集一定是无法辨别出这个串的;后面从大到小每一个push down一层即可。O(nnl+l2l)O(n\cdot n\cdot l+l\cdot2^l)

fairy

Codeforces19E BZOJ4424 EZOJContests/1338/A
先染一下色。

  • 对于不在DFS树上的连接不同色点的边,删去不改变图的可二分性;
  • 对于不在DFS树上的连接同色点的边(称为Error Edge),如果只有一条,那么只能删掉那一条;如果有多条Error Edge,那么这几条边删掉任意一条都不影响剩下图的可二分性;
  • 对于在DFS树上的边:
    • 如果没有Error Edge两端点在树上的路径覆盖它,删掉它不影响可二分性;
    • 如果有Error Edge覆盖它,删去这条边后,把这条边把树分成的两部分中的一个黑白交换,就可以保证覆盖它的Error Edges合法,而将覆盖它的非Error Edges转为不合法边;故能删去这条边后是二分图当且仅当所有的Error Edges都覆盖它且没有其他的正常边覆盖它。

wind

Codeforces768G EZOJContests/1338/C
最佳方案一定是将size最大的子树中的一个子树剪掉之后贴到size最小的子树上。答案也一定不会小于第二大的子树大小。

如果二分判断的话,对于一个ans,只需要知道在最大子树中是否存在子树的size满足maxsize-size<=ans&&minsize+size<=ans。换句话说,设剪掉的子树大小为size,那ans=max(maxsize-size,minsize+size)。画出图像来,sizemaxsizeminsize中点时ans取最大值。那取最接近中点的size就好了。

考虑怎么知道可行的size。搞一个可并可求lower_bound的数据结构,比如set或可持久化线段树。DFS每一个节点的时候,维护四个位置的size集合:

  • 还在栈中的节点,这一部分的size要减去当前节点的size
  • 已经访问过的节点;
  • 未访问过的节点;
  • 当前子树;

然后分两类情况讨论:

  • 最大子树是重儿子:直接查重儿子子树;
  • 最大子树是根:查询另外三个。已访问的节点要在DFS进入的时候查,未访问的要在DFS退出的时候查,在栈中的无所谓。

skyscraper

Codeforces768G EZOJContests/1339/B
有30分,是从Bob推Alice。直接输出Bob计数器的值就可以了。

怎么证明?

假如Bob在第ii层上溜了一次,计数器就会多2i12^{i-1}。为了求AliceAlice计数器的期望,我们要求他这一次过溜索期望经过了多少栋楼。不妨让这个期望包括右边不包括左边。

在我们考虑的所有样本中,Bob在这个位置只可能从第ii层过,所以左边高度一定i\geq i。无论左边是>i>i还是=i=i,最左边以右的所有房子高度在总体中的概率分布是不变的。而,如果某一栋房子高度i\geq i,那么Bob一定会停下来;Bob会停下来,当且仅当某一栋房子高度i\geq i

设一栋楼高度<i<i的概率是PP,则他经过jj栋楼的概率是Pj1(1P)P^{j-1}(1-P),那么经过的楼的数量的期望就是

j=1+Pj1(1P)j=(1P)j=1+Pj1j=(1P)dj=0+PjdP=(1P)d11PdP=(1P)1(1P)2=11P=11(12(i1))=2i1\begin{matrix} &\sum_{j=1}^{+\infty}P^{j-1}(1-P)\cdot j\\ =&(1-P)\sum_{j=1}^{+\infty}P^{j-1}\cdot j\\ =&(1-P)\frac{\mathrm{d}\sum_{j=0}^{+\infty}P^j}{\mathrm{d}P}\\ =&(1-P)\frac{\mathrm{d}\frac{1}{1-P}}{\mathrm{d}P}\\ =&(1-P)\frac{1}{(1-P)^2}\\ =&\frac{1}{1-P}\\ =&\frac{1}{1-(1-2^{-(i-1)})}\\ =&2^{i-1} \end{matrix}

和Bob的计数步数一样!所以无论Bob走了多少步,Alice也期望走了那么多步。在第一栋楼处,Alice和Bob都可以被看作走了1步。

神奇的是,Alice推Bob却会得到不一样的结果。这也有很多种做法。

一种做法是逐渐增加可以溜索的高度。假设现在考虑到第ii层。考虑某一次溜的长度为jj(同样包括右边不包括左边,即经过了几个间隙),在某一固定位置出现这次事件当且进当左边、右边高度同时i\geq i(注意因为高度限制为ii所以同时>i>i也只会在第ii层过)且中间高度<i<i。这个事件的概率是(2(i1))2(12(i1))j1(2^{-(i-1)})^2(1-2^{-(i-1)})^{j-1}。然后,长度为jj的溜索可能在(nj)(n-j)个地方出现。

新的溜索一定会覆盖旧的溜索,而且在加入第ii层的时候下面一定都是i1i-1层的溜索。问题就在有几根i1i-1层的溜索?从左边开始数,一开始有一根,每出现一个ii层高的楼就多一根。而在已知中间高度在[1,i][1,i]中,求出中间高度在[1,i1][1,i-1]中的条件概率为2i112i1=12i11\frac{2^{i-1}}{1-2^{i-1}}=\frac{1}{2^{i-1}-1}。那么每一个高度为ii,长度为jj下方的溜索的期望贡献就为2i2(1+j12i11)2^{i-2}\cdot(1+\frac{j-1}{2^{i-1}-1}),减掉即可。

第1层所有溜索都一定会有,所以初始化ans=nans=n,然后就可以顺利解决该题了。

n+i=2hj=1n(nj)(2(i1))2(12(i1))j1(2i12i2(1+j12i11))n+\sum_{i=2}^h\sum_{j=1}^n(n-j)(2^{-(i-1)})^2(1-2^{-(i-1)})^{j-1}(2^{i-1}-2^{i-2}(1+\frac{j-1}{2^{i-1}-1}))

当然DP也可以做,但是没有这个做法那么优美!

补充知识
这题出在MemSQL的比赛里面,然后给大家强行科普跳跃表(Skip List),说什么MemSQL底层也有使用这种优秀的数据结构,然后硬广一波……将主题和题目结合到这个地步的,我才疏学浅,还是第一次见。

跳跃表是链表的优化。链表的随机访问不快,所以采取新增索引的办法加速。选取某一些元素,竖着复制几遍,变成几层链表,越高的链表越稀疏;查找的时候从最上面一层开始,大致找到区间的时候往下走。排列出来就大概是这题楼房的样子。

怎么决定每个元素出现多少层?抛硬币!抛一枚硬币,正面决定就是这一层,反面决定继续往上长。那么就会像这题描述的,有12\frac{1}{2}的几率留在一层,有14\frac{1}{4}的几率留在二层……

这样每添加一个节点,实际添加节点数期望是两个。于是插入、删除期望复杂度O(1)O(1)。访问、lower_bound等就是上面的问题的权值从2i12^{i-1}改成11,一开始有一栋无限高的楼,而且溜索高度无限制。设我们访问的是第nn个元素(nn后面的对nn无影响,可以看作没有),从下到上一层一层考虑,就和刚才的问题几乎一样了,只要特判00号位永远是无限高即可。

ni=2hj=1n(nj)(2(i1))2(12(i1))j1j12i11n-\sum_{i=2}^h\sum_{j=1}^n(n-j)(2^{-(i-1)})^2(1-2^{-(i-1)})^{j-1}\frac{j-1}{2^{i-1}-1}

i=2hj=1n2(i1)(12(i1))j1j12i11-\sum_{i=2}^h\sum_{j=1}^n2^{-(i-1)}(1-2^{-(i-1)})^{j-1}\frac{j-1}{2^{i-1}-1}

我把外面一层化成积分之后让Wolfram去算,然后就得出了一个带cotnπ\cot{n\pi}ii的式子???

于是我就不会分析复杂度了。

surprise

Codeforces809E EZOJContests/1339/C
前面的常数就不用多想了。把后面变形一下:

d=1ndφ(d)i=1nj=1nφ(ai)φ(aj)dis(i,j)δ((ai,aj)d)\sum_{d=1}^n\frac{d}{\varphi(d)}\sum_{i=1}^n\sum_{j=1}^n\varphi(a_i)\varphi(a_j)\mathrm{dis}(i,j)\delta((a_i,a_j)-d)

如果枚举dd,那怎么求后面的东西?设

f(d)=i=1nj=1nφ(ai)φ(aj)dis(i,j)δ((ai,aj)d)f(d)=\sum_{i=1}^n\sum_{j=1}^n\varphi(a_i)\varphi(a_j)\mathrm{dis}(i,j)\delta((a_i,a_j)-d)

F(d)=i=1nj=1nφ(ai)φ(aj)dis(i,j)[d(ai,aj)]F(d)=\sum_{i=1}^n\sum_{j=1}^n\varphi(a_i)\varphi(a_j)\mathrm{dis}(i,j)[d|(a_i,a_j)]

下面的那个东西建虚树求,然后f(n)=F(n)nd,dnf(d)f(n)=F(n)-\sum_{n|d,d\neq n}f(d)O(nlog2n)O(n\log^2n)

ant

EZOJContests/1340/A
线上的版本依赖于每只蚂蚁相对顺序不变。把蚂蚁看作远处的小点,看起来蚂蚁相遇的时候就没有掉头。求出最终位置集合,然后排序,再根据初始相对位置对应出每只蚂蚁的位置。

圆上的版本带来的一个问题就是蚂蚁的位置排名可能会突然就从第一跑到最后。那只要统计出有多少只蚂蚁顺着穿过了原点,有多少只蚂蚁逆着穿过了原点,就可以算出最终的排名了。

alice

EZOJContests/1340/A
倒推,维护可以到达00的初始位置集合SS。我们只需要知道max[0,n]Sn\max_{[0,n]\in S}n是多少,就能判断这个更改有没有可能导致最终位置不为00。又dd递减,所以使n+1n+1可以到达00只有可能是[0,n][0,n]的数,所以大于nn的位置集合(区间)都不用考虑。

eat

EZOJContests/1342/B
可以先将石子按数量排个序。然后发现,两个操作一个是从小开始删除,另一个是从大开始删除。那就可以DP一下,状态就是两个操作各进行了多少次,就得到了一个n2n^2的DP。

如果把所有的石子画成柱状图,也就是把DP数组列出来,会发现对角线上的数字是一样的!这是因为比输的地方的后两个状态是必胜态,这两个必胜态又会造就一个比输态;而必胜态的两个前驱状态中至少有一个比输态,比输态的对角线上都是比输态,所以它旁边至少有一个比输态,所以它的对角线上的下一个也一定是一个必胜态。然后O(n)\mathrm{O}(n)搞一搞就可以了。

deer

EZOJContests/1342/C
追不上的情况,就是逃跑的那个人的可以跑到某条在另一棵树的距离超过2的边。如果有这种情况,逃跑的那个人就可以等着,等人家来了就跳走,如此循环。

讨论一下追的人的最优策略。如果追的人不向着目标跑,那么目标就可以一直等着他跑回出发点,也不会使答案变差。所以追逐者一定会向着目标跑。因为追逐者会朝着自己跑,逃跑者也一定会尽可能逃跑。

如果在警察的树上从警察出发点开始DFS的话,小偷总是会待在警察所在子树内,因为小偷不可能跨过警察到上面去而不被抓到(如果可以那就是追不上的情况)。那在小偷的树上再DFS一次,同时记录如果小偷到这里,警察对应地会到哪个深度(也就是小偷走的步数),就可以判断有没有追上了。如果没有追上,那么可以更新答案为 步数+(小偷深度-警察深度)=小偷深度。

run

EZOJContests/1343/B
我这题想了很久。首先,我们可以知道一个长度为nn,字符集大小为kk的回文串有kn2k^{\left\lceil\frac{n}{2}\right\rceil}个。然后我们可以把这个串循环移位,从而构造出合法串。

但是问题在于,一个合法串可能会被多个回文串,或者同一回文串的不同移位长度得到。如果一个回文串不同移aa次和移bb次相同(不妨设a<ba<b),那就一定存在一个a<c<ba<c<b使得这个串移cc位之后与自己相同。对于某一个串,在cc取最小的正整数时,移位长度在[0,c1][0,c-1]之间的串一定是互异的。那这个cc不就是最小正周期吗?

那我们就枚举cc,也就是枚举长度为nn的串的最小循环节长度。又有回文串性质+循环节性质,每个最小循环节还应该是一个回文串。设f(n)f(n)为长度为nn的回文且没有更小最小循环节为nn的串的个数。容易得到DP方程:

f(n)=kn2dn,d<nf(d)f(n)=k^{\left\lceil\frac{n}{2}\right\rceil}-\sum_{d|n,d<n}f(d)

确定下最小循环节的每一位,整个串也就确定了。由于每移一位都会得到不同的串,所以答案就是dnf(d)d\sum_{d|n}f(d)\cdot d

Wait!有没有可能不同的串循环移位之后得到同样的串?有可能!在这个时候,如果SS串和TT串循环移位之后得到了一个相同的串,说明SS循环移位能得到TT。而SSTT又都是回文串,那就有很好的性质了。

我在考试的时候忘了用循环移位后相等,直接用回文串的性质,推出来的结果恰好能解决这个问题。设回文串SStt位后得到TT,下标是在模nn意义下的表示,且从00开始。则可以得到

Si=Sn1iSi=Sn1+2ti}Sn1i=Sn+2t1iSi=Si+2t\left.\begin{matrix}S_i=S_{n-1-i}\\ S_i=S_{n-1+2t-i}\end{matrix}\right\}\Rightarrow S_{n-1-i}=S_{n+2t-1-i}\Rightarrow S_i=S_{i+2t}

所以2t2t是一个周期。然后又由于各种数论性质可以把周期缩小到gcd(n,2t)\mathrm{gcd}(n,2t)。由于还有回文串性质,这给出的是最小正周期的一个上界,我在考试的时候还算出了更精确的上界,但是并没有什么用……总之,观察这个上界,发现在t=n2t=\frac{n}{2}的时候是一定会变成另外一个回文串导致重复。感性想象一下:最小循环节长度为偶数dd的串SS,在循环移位d2\frac{d}{2}之后是一定会得到另一个回文串。

而这也是唯一一个会造成重复的情况。对于其它所有情况的移位长度t(t[0,d1])t(t\in[0,d-1]),考虑每一个循环节,如果移位后相等,说明这个循环节拥有长度为gcd(d,2t)<d\mathrm{gcd}(d,2t)<d的循环节,与dd为最小循环节长度矛盾。

然后就可以做了,2d\forall 2|df(d)df(d)\cdot d除以22即可。可以暴力枚举nn的因子O(σ02(n))\mathrm O(\sigma_0^2(n)),也可以类似杜教筛每次O(n)\mathrm O(\sqrt{n})分解因数O(n34)\mathrm O(n^{\frac{3}{4}})O(n23)\mathrm O(n^{\frac{2}{3}})

classroom

EZOJContests/1343/C
考试时看错成了求期望。什么翻译啊,选KK个数说成“随机选KK个数”。

一个数对答案的贡献取决于被合并了多少次,被合并dd次后贡献就乘上了KdK^{-d}。那么最终答案,就是Kd\sum K^{-d}的形式,也就是一个不超过N+M1K1\frac{N+M-1}{K-1}位(由合并次数得)的KK进制小数。

我们需要考虑怎么构造出合法的方案,为了这个操作我们需要得到一些必要的限制条件。

  • 考虑合并操作的逆过程,可以得到Kd=1\sum K^{-d}=1
  • 设最终得到的KK进制小数为zz,第i-i位为ziz_i。对于那NN00MM11对称考虑),假如zz不会进位,那zi=N\sum z_i=N。但是现在会有进位,所以ziN\sum z_i\leq N。每次进位的时候,后面减少KK,高一位增加11,相当于在模K1K-1意义下不变,所以另一个必要条件是模K1K-1意义下ziN\sum z_i\equiv N

这是一个挺明显的数位DP。但是要求和是11,怎么办呢?我们只需要把MM减去一,得到两个小数之后再加上KdK^{-d}就可以了。这样只要知道其中一个小数,就可以用K1K-1去减每一位得到另一个小数。

下面来证明满足以上要求的小数一定有方案能得到它。我们每次可以选择某一个非00位,把它退位,即该位1-1,后一位+K+K,来尝试使zi=N\sum z_i=N。现在的问题就是,ziz_i有可能在退到第N+M1N+M-1位的时候,zi\sum z_i仍然不够NN。由于NNM1M-1的小数和为0.(K1)(K1)...(K1)0.(K-1)(K-1)...(K-1),在枚举的时候就已经固定下来了,我们不妨证明在最坏情况下,仍能构造一个方案满足条件。

M1M-1那边的数尽可能大,这样zz就最小,退到第N+M1N+M-1位的时候zi\sum z_i就最小了。那M1M-1的结果看起来应该是这个样子:

0.(K1)(K1)...(K1)a0.(K-1)(K-1)...(K-1)a

zz最小,那看起来就是这个样子:

0.0000...00(K1a)0.0000...00(K-1-a)

为了让这两个小数合法,其中aa满足a[0,K1]a\in[0,K-1]且在模K1K-1意义下aN-a\equiv N

接下来的证明是zwl给出的,这个放的刚刚好,比我的全部暴力退到最后一位好多了……

zz(K1a)(K-1-a)展开成(K2a)(K1)(K1)...(K1)K(K-2-a)(K-1)(K-1)...(K-1)K。那么两个数的和恰好是0.(K1)(K1)...(K1)0.(K-1)(K-1)...(K-1),各个位置上的数的和恰好是(N+M1)(N+M-1)。由于M1M-1那边的小数各位和M1\leq M-1,那么zz展开后的各位和N\geq N。证毕。

rabbit

EZOJContests/1345/B
容易得到第ii只兔子跳完之后的位置期望是xi1+xi+1xix_{i-1}+x_{i+1}-x_i,看起来很线性,所以就有很多性质可以用了。那其实已经可以构造矩阵了,但是这样的速度太慢。

我考试的时候猜了一个结论,就是任何时刻第ii只兔子的位置期望都可以表示成xl+xrxmx_l+x_r-x_m的形式,好不容易写出来却过不了……直接零分。有待证明或证伪。

如果把转移矩阵列出来,不仅可以看到上面提到的现象,还能看到竖着的值比较连续。那就可以考虑差分(其实看到xix_i的这个形式,我就感觉会有很好的性质,但是真的没想到差分,这样的东西就应该差分),用另外一个数组的前缀和表示xix_i,就可以推出很奇妙的东西。

xi1+xi+1xi=j=1i1yj+j=1i+1yj+j=1iyjx_{i-1}+x_{i+1}-x_i=\sum_{j=1}^{i-1}y_j+\sum_{j=1}^{i+1}y_j+\sum_{j=1}^iy_j

=j=1i1+yi+1=\sum_{j=1}^{i-1}+y_{i+1}

新的xix_i和原来的差别就在于一个是前i1i-1yy加上第ii个,另一个是前i1i-1yy加上第i+1i+1个,而我们又要保持其他yj\sum y_j不变,前i1i-1xjx_j显然不变,后面的只要让新的yi=yi+1y_i=y_{i+1}就也能保持不变。这里相当于是交换了yiy_iyi+1y_{i+1},这是一个非常简单的对换操作,一套操作可以合并成一个置换,一个置换又可以分解成一系列轮换的乘积,那做kk次轮换岂不是很容易??

我一开始在这里想到要用倍增,后来发现根本就不用,只要用kk模一下循环节长度就知道实际位移了。

cleaning

EZOJContests/1345/C
这个题目的DP做法很容易想到。每棵子树有多少条路径需要连出去是确定的,所以可以用子树的信息算出更大的树的信息。为了合并信息,我们需要知道如果将现在子树的路径两两匹配起来最多能匹配多少组。

显然不能一般图匹配瞎搞。有一个结论是,如果最大的那一堆个数比其他堆个数和大,那显然一直用最大的那一堆和其他的匹配后剩余的就是根本没有办法匹配的;如果最大的一堆个数小于等于其他堆个数之和,那总可以使匹配近似完美,在奇数个的时候只剩一个,在偶数个的时候完美匹配。后面一个需要归纳证明。

考虑现在的一种状态,如果最大的那一堆小于等于其他之和,那我们把最大和次大的匹配一个,此时最大和次大还是不会超过一半。但是其他是有可能超过一半的,设原来总共有nn个,有一个原本大小为ss的堆,它既不是最大也不是次大,但是在匹配这一次之后它大于总大小的一半,破坏了我们的递归条件,那它一定满足n22+12sn3\frac{n-2}{2}+\frac{1}{2}\leq s\leq\frac{n}{3},这个不等式有解的条件是n3n\leq3,这么小的数据就可以随便讨论了。否则一直递归下去,石子数有限,要不出现一个>n2>\frac{n}{2}的,要不就递归到一个比较小的、可以手动考虑的状态。

这样的结论的确很简洁、很好用,但是为什么能想到呢?这是从特殊情况入手,逐渐深入、分析。我考试的时候太贪恋于eat这道题,想了一个类似的做法,非要把那个连续删最大和次大的过程模拟出来,前后调试了两个多小时,多多少少导致了我今天0分的结局。

这两天状态真的是差得不行。在考试临近的时候又开始掉链子,可以算是我的传统和特长了。虽然今天没有部分分,但也埋怨不得谁,毕竟大家都还有分。而我又不能止步于赶上大家,这让我感到更彻底的失败。

考试的时候实在想太多了,思维有广度没有深度,多线程工作,没有效率,有效思考时间很少。然而该放一放的时候又死揪住不放,不顾全局,颇有NOI前的风范。心态不变,效率不提,纵千遍万遍,哪条道行得通?

redblue

EZOJContests/1346/B
这道题的做法很好想,每次找一条只被一条红色边覆盖的蓝色边,删去,再继续找。如果能删掉所有蓝色边,加入所有红色边,就OK。树剖+线段树+set三个log\log

值得记录的是zjt的一个小技巧。因为每次满足条件的蓝色边只会被一个红色边覆盖,如果记录覆盖这条蓝边的编号和,在只剩一条边的时候这个编号和就恰好是覆盖它的红边的编号。

xj提供了另外一个做法。如果答案为YES,那么就一定可以倒推,最后一条删掉的红边和蓝边一定重合。把这两个点缩起来成为一个新的树,依然满足刚才的那个性质,就一直可以倒推回去了。

shik

EZOJContests/1346/C
二分答案,树形DP,然后考虑优化。树形DP是一段一段的,所以可以维护拐点。记录二元组(们)表示可以进入到深度a然后从深度b出。启发式合并,一通减枝就过了。

记录这题是因为之前好像做过,第一眼看到想到了正解,但又let it go。不过心想没出事,因为后来仔细观察发现每条边不一定需要一进一出,就不会做了。考完试通知题目改了……

shuffle

EZOJContests/1347/C
首先可以把多余的0都去掉。

  • Ai=1,Bi=1A_i=1,B_i=1是一定不能与Aj=1,Bj=0A_j=1,B_j=0这一类位置交换的。如果交换了,相当于没有变,却浪费jj的一次机会,以后AjA_j就没有机会变成00了,那最终AA也一定不会等于BB
  • 如果Ai=1,Bi=1A_i=1,B_i=1Aj=1,Bj=1A_j=1,B_j=1交换了,无论怎么交换,看起来都一样。这部分的答案直接阶乘枚举就好了。
  • 如果Ai=1,Bi=1A_i=1,B_i=1Aj=0,Bj=1A_j=0,B_j=1交换了,只能是BjB_j那边提供了一个,AiA_i那边提供了一个,交换完之后Ai=0,Aj=1A_i=0,A_j=1。相当于是00进行了一次移动。那么这个00最终一定会移动到一个Ak=1,Bk=0A_k=1,B_k=0的位置,从而满足相等,不再移动。

从上面最后一点看出,我们需要把整个操作序列分成一些由Ai=1,Bi=0A_i=1,B_i=0开头,以Ai=0,Bi=1A_i=0,B_i=1结尾的排列,以及剩下的Ai=1,Bi=1A_i=1,B_i=1乱搞的排列。枚举完这些排列之后再用多项式系数穿插起来,就能得到最终的答案了。

Ai&Bi=1A_i\&B_i=1的个数为mmAi&Bi=0A_i\&B_i=0的个数为2n2n,操作序列长度为n+mn+m,那答案就是(m+n)!m!n!(ex1x)n1x(m+n)!m!n!\frac{(\frac{e^x-1}{x})^n}{1-x}xmx^{m}项系数(这里可能会有问题,仅供参考)。倍增FFT是两个log\log,可以用对数函数和指数函数优化到一个log\log

garden

EZOJContests/1349/B
这道题好像经常出,但是我没有做过,场上我也没有想到怎么做。

有一个比较经典的思路是,考虑某个数对当前所有数的影响,按顺序从小到大或从大到小加入。比如说,我们可以利用Floyd最外层循环的性质,排序后使得中间点权值逐步增大,来求解路径上最大值一类的最短路径问题。

在这题中,我们可以考虑从小到达添加数字。这样一来,所有还没有填的数字都是确定比当前数字大的,相对大小就这样巧妙地确定下来了。极小值的位置如果还没有填,那是一定不嫩在它周围填的。由于可能极小值位置最多八个(更多的话要特判为0,第一次WA就是没有特判),可以轻松状压起来。

这样填可能会让某些没有被钦定的位置也成为局部极小值。在这样的状态量下,是不可能讨论出来的。其实容斥一下就可以了。

第一题

EZOJContests/1352/B
我只是记录一下这题的一个积分式的答案:0+x4x2α3πex2a2dx=2aπ\int_0^{+\infty}x\frac{4x^2}{\alpha^3\sqrt{\pi}}e^{-\frac{-x^2}{a^2}}\mathrm{d}x=\frac{2a}{\pi}。Wolfram(Mathematica)还是蛮强大的,我用它来验算了一波。

第四题

EZOJContests/1352/C
一道简单的DP题,有的时候,真的是想复杂了。选人为参考系,把出口向上、下、左、右最远到达过的位置作为状态就行了。转移要小心新加入的一行也有被删掉的。

美丽的yxq

EZOJContests/1354/A
DP很容易想。设f[i]f[i][0,i][0,i]的答案,如果x=ix=i允许为边界,则f[i]=j=0n1f[j](ij)2f[i]=\sum_{j=0}^{n-1}f[j]* (i-j)^2。这个式子可以用前缀和优化到O(n)\mathrm{O}(n),然后就没法做了。

这个东西看起来可以用生成函数表示,我还真推出了那个生成函数的表达式,但是不知道怎么快速求某一项系数……

换种写法,f[i]=j=1nf[nj]jf[i]=\sum_{j=1}^nf[n-j]* j,就发现可以矩阵快速幂了……场上竟然没有人能够做出来……有限制的地方停下来,换个转移矩阵就好了。

Comb Avoiding Trees

EZOJContests/1354/B
这题可以把数据出的很大。

简化一下题意,要求从根节点到任意叶子节点向左走不超过k1k-1次的二叉树数量。随便DP一下,设f[i][j]f[i][j]为“左”深度不超过ii,叶子数量为jj的合法二叉树数量。

f[i][j]=k=1j1f[i1][k]×f[i][jk]f[i][j]=\sum_{k=1}^{j-1}f[i-1][k]\times f[i][j-k]

这是O(n2k)\mathrm{O}(n^2k)的,有60分。

用生成函数改写之后是这个样的:

Fi(x)=Fi(x)×Fi1(x)+xF_ i(x)=F_ i(x)\times F_{i-1}(x)+x

Fi(x)=x1Fi1(x)F_i(x)=\frac{x}{1-F_{i-1}(x)}

拼命求逆可以做到O(nklogn)\mathrm{O}(nk\log n),但是因为常数过大拿的分并不比O(n2k)\mathrm{O}(n^2k)多。

每次Fi(x)F_i(x)都是一个分式,如果我们不会求逆,设Fi(x)=Ai(x)Bi(x)F_i(x)=\frac{A_i(x)}{B_i(x)},则Fi(x)=xBi1(x)Bi1(x)Ai1(x)F_i(x)=\frac{xB_{i-1}(x)}{B_{i-1}(x)-A_{i-1}(x)},这样一次转移是O(k)\mathrm{O}(k)的,最后求逆也可以暴力求(然而我现在只会FFT求逆了……),总复杂度O(k2+n2)\mathrm{O}(k^2+n^2)。这样就已经能解决问题了。这种回归朴素的思想派上了用场,在待会的做法中也可以看到。

能不能优化呢?发现A(x)A(x)B(x)B(x)是两个多项式常系数齐次线性递推,可以构造转移矩阵……当然可以把多项式带着算,但是那样太慢了。可以先点值,然后再用IDFT插值回来,得到A(x)A(x)B(x)B(x)。加上快速多项式求逆,时间复杂度是O(klogk+nlogn)\mathrm{O}(k\log k+n\log n)的。这个做法虽然不是最快的,但是思路十分值得学习!

但是这个线性递推看起来很有规律,拿Wolfram打出表来,发现系数是组合数……那分子分母都可以O(k)O(k)算了。此时数据可以出到n106n\leq10^6k105k\leq10^5

nn已经到极限了。如果我们只要求一个nn而不是11nn中的所有数,算法还可以更优秀。

为了让nn能够更大,逆元是瓶颈。现在我们真的要认真考虑如何求多项式逆元了。假设已经计算出了前i1i-1项的系数,现在要求第ii项的系数。由于逆元要求除了x0x^0项以外其他项系数都是00,而卷积之后对xi1x^{i-1}有影响的就是现在求的前ii项了。那通过一次卷积,就可以求出这一位的系数。

ii比较大的时候,因为我们是对一个O(k)\mathrm{O}(k)的多项式求逆,卷积后对xi1x^{i-1}有影响的,也只有最近的这kk项了。这时我们就能发现,这就是在对逆元的系数做常系数齐次线性递推……然后n1018n\leq10^{18}就可做了……

还有一个要解决的问题是,我们不能仅求一个位置的系数,为了得到最终答案,还要卷积上A(x)A(x),所以要知道最后kk个位置的系数。在用Cayley-Hamilton定理之后,得到了一个转移矩阵(假装我们得到了)。将这个转移矩阵乘以初始向量之后,需要得到的是结果向量的第一个位置的值。如果我们需要得到转移多一次,两次,……,直至kk次的结果,可以强行把结果向量再乘几次转移矩阵(显然不可做);也可以把初始向量再乘几次转移矩阵,和多项式系数点积,从而得到向量第一位的值。这也就是说,我们只要求出数列的前2k2k项,就可以求出第nk+1n-k+1nn项了。

乘积

EZOJContests/1353/B
和《寿司晚宴》很像,按是否含有大于O(n)O(\sqrt{n})的质数把数字分类。选了哪些比较小的质数可以状压,然后做背包DP,用大质数的倍数集合更新。

math

EZOJContests/1353/C
我完全没有花时间想这道题,直接就被告知结论了。

分情况讨论。

如果aa为奇数,则解有且仅有一个。可以递归证明,小情况so easy,当n=kn=k时,由归纳假设知xa+2k1p(mod2k)x\equiv a+2^{k-1}p(\mathrm{mod}2^k)p{0,1}p\in\{0,1\},代入原式,左边欧拉定理,右边二项式展开:

aaaa+(a1)2k1ap(mod2k)a^a\equiv a^a+\binom{a}{1}2^{k-1}ap(\mathrm{mod}2^k)

2k1a2p02^{k-1}a^2p\equiv 0

所以p=0p=0,故归纳假设xa(mod2n)x\equiv a(\mathrm{mod}2^n)n=kn=k成立。证毕。

对偶数的情况,发现如果aa一旦有2t2^t的因子,axa^x立刻就会有2tx2^{tx}的因子,在xx比较大的时候axmod2na^x\mathrm{mod}2^n就全是00了,所以把答案分两部分考虑,一部分暴力检验,一部分直接算。

stable

EZOJContests/1357/C
思考一番发现删完边之后这个图应该是一条从11nn的路径,路径上每个点上可以挂若干个图。为了使代价最小,这些挂到同一个路径上的点的图内部是不删边的。

然后就考虑状压DP。哪些店现在已经和起点联通,哪个点将会成为当前最靠近终点的点记为状态。每次可以把一堆点挂到当前点上,也可以新加入一个点到那条唯一路径上。复杂度O(3nn2)O(3^nn^2)

我考试的时候把路径上的点枚举完之后求最短路,然后再背包DP哪些点挂到哪些路径上的点上,十分复杂,没时间调试,结果考完交一发过了70分,剩下30分卡常……