最近几场cf口胡

UPD.最近作业做得很忙。。我的速度是各位大爷的$\frac{1}{10}$。。cf上好玩的题就嘴巴一下，不保证正确性。。不好玩的题懒得管。。有时间会补一补。

从576A开始。。只管div2C及以上的水题。。

没过的题不保证正确性，过了的题不保证复杂度是对的。比如说585E

由于还要做作业所以这个坑不会很认真地填。

TODO LIST：我也没有说我要填完

576DE,580CDE,581CDEF,582D,584E,585C,587DEF,589EKLM,590CDE

【576A】把形如$p^k$的数弄出来就行了。

【576B】如果排列有长度为$1$的轮换，那么以这个轮换为根构菊花树；否则，如果轮换长度都是$2$的倍数且存在长度为$2$的轮换$(x,y)$，那么把每个轮换中奇数位置与$x$相连，偶数位置与$y$相连，再把$x$与$y$相连。否则无解。证明的话考虑重心/双重心。

【576C】你听说过莫队算法么(雾)。把点按照$\lfloor \frac{x}{1000}\rfloor$分块，每一块从下往上/从上往下连就行了。

【578A】有公式。

【578B】显然乘法用到同一个数上去，枚举是哪个数就好。

【578C】三分。注意这题卡精度。

【578D】dp套dp，小dp的状态是LCS状态(只需要记$f_{i,i-1},f_{i,i},f_{i,i+1}$，只有8种还是5种情况)。

【578E】一个人走的路一定是先走一个子序列再往回再走一个子序列再往回等等。如果把序列分成一些子序列的并，每个子序列都是LRLR交错的形式，且子序列的数目尽可能少，那么一定可以把这些子序列拼起来形成一个完整的序列。怎么划分呢，就相当于一个二分图左边是L右边是R，一个R在一个L右边那么连一条边，求最大匹配(可以贪心)，就得到了所有L后面的R(没有被匹配的就是子序列的结尾)。同理可以得到所有R后面的L。即我们得到了所有forward steps。用贪心方法把它们接起来即可。

【578F】生成树计数，不知道为什么一直wa。

【582A】用堆(set)维护输入数。每次找一个最大的，它一定在原数组中，然后把它和已知原数组中其他数的gcd从堆中删掉。说这么多还不如看代码(推荐cubelover神犇的)

【582B】把$n$个这样的序列拼起来，设这个大序列为$A$。LIS一定长这样：$A$中以某个数$x$结尾的LIS、一堆$x$、$A$中以$x$开头的LIS。

【582C】枚举$d=\gcd(n,l)$，把序列分成$n/d$段，一个数$a_i$可以被选当且仅当$a_i=\min_{d|(j-i)}a_j$，一个区间合法当且仅当其中每个数都可以被选。枚举区间起点，变成小于等于$L$的数中与$n$的gcd为$d$的数的个数就可以瞎搞搞了。

【582E】说了只写水题嘛。构出表达式树，树中每个节点$x$记录$f_{x,i}$表示等于函数$i$的填法数量。$i$用16个bit来表示，记录$A,B,C,D$的每一个取值对应的函数取值。转移太慢，用FWT加速一下就好。

【584C】三个变量相等/不等有五种可能，枚举每种可能的个数即可。

【584D】平均$O(\log p)$个数中有一个质数。怎么暴力怎么搞。

【585A】纯模拟，上图不说话。

【585B】dp，Phillip走到一个点的时候我们完全可以推算出每个火车的位置以及这个点有没有火车。

【585C】考虑这个东西。原问题变成：求$\frac{1}{1}$到给定分数的一条路径。扩欧直接算。

【585D】很明显的meet-in-the-middle，先搜前$\frac{n}{2}$个task的方案再搜后$\frac{n}{2}$个。

【585E】$f_i$表示gcd为$i$的集合数，$g_i$表示与$i$互质的数的个数，$c_i$表示$i$的倍数个数。各种奇奇怪怪的dp就可以做出这个题了，时间复杂度是$O(a\log a)$的。踩TL过真是感动。

【585F】把$s$的所有长为$\lfloor\frac{d}{2}\rfloor$的子串放进一个AC自动机。$dp_{i,j}$表示从点$i$出发走$j$步，不许经过代表串结尾(即，Trie中深度为$\lfloor\frac{d}{2}\rfloor$)的节点，总共的方案数。接下来就是数位dp的事了。把问题转化为求$\le r$的数中有多少个不是half-occurrences，枚举这个数与$r$的LCP即可。

【587A】答案就是所有重量的总和的二进制表示中1的个数。

【587B】枚举长度$x$然后dp。

【587C】这不就是无修改QTREE吗只是要记录前十小值而已>_>

【587F】把所有串用奇怪的分隔符连接，构出后缀数组，每个后缀只要不是奇怪的分隔符开头都会属于一个串。记$t_i$为$sa_i$属于哪个串。对每个串可以求出一个区间$I_i=[l_i,r_i]$，表示包含它的所有后缀所在的区间。一次询问$l,r,k$即求编号在$[l,r]$内的区间中，$k$出现的次数的和。对区间分块，$f_{i,j}$表示第$i$块的所有区间中$j$的出现次数，可以$O(n\sqrt{n})$预处理，询问也可以做到$O(\sqrt{n})$。(这是口胡)

【589A】队友做的。。哈希乱搞吧，反正是口胡。orz ymdragon

【589B】$a,b\leftarrow \min(a,b),\max(a,b)$。然后枚举一维排个序枚举另一维。

【589C】可持久化AVL！直接碾压就好。。

【589D】转化为判断两个人是否相交，推式子+讨论就好。

【589FGH】队友做的。。队友简直太神辣。。尤其是那个叫z123z123d的。所以我并不准备做了

【589I】出现次数大于$n/k$的，把出现次数减去$n/k$，求个和。

【589J】记忆搜。

【590A】如果$a_i=a_{i+1}$，在$i,i+1$处剪断序列。。答案就是每个子序列的最大值，以及它们的最后模样。。子序列形如0101010..或1010101..所以答案可以直接算。。

【590B】显然有二分性，没了。

【590E】转化为偏序集最长反链问题，见我在uoj上的博客(包括记方案)。考虑建图，即判断一个串是不是另一个串的子串，用阿狸的打字机做法可以做?(这是口胡)

UPD

谁会猜到窝2017年9月会诈尸来更这篇文章→_→

【815A】假设$n\le m$，那么显然优先搞行操作(为了使操作次数尽量少)。一行的操作次数是这行的最小值，然后可以求出一列的操作次数，check一下就好。

【815B】求出每一项的系数就好。这个可以打表找规律，根据$n\pmod 4$不一样规律也不一样。

【815C】树P。用$dp[i][j]$表示子树$i$中买$j$个东西至少花多少钱

【815D】枚举那张卡片的$p$，发现可能的$(q,r)$的范围是某种面积，且可以用线段树维护。

【814C】枚举字符$c$，枚举区间$[l,r]$，用$r-l+1$更新询问$a,c$的答案，其中$a\ge$($[l,r]$中不是$c$的字符个数)。

【814D】圆组成一棵树，$f[a][b][c]$表示$a$的子树，上半夜奇偶性为$b$，下半夜奇偶性为$c$的最大值。

【848A】要求的就是$\sum_{i='a'}^{'z'} \binom{A_i}{2}$恰好等于$k$，其中$A_i$为$i$的出现次数。贪心一下就好(每次找最大的三角形数减掉)

【848C】每个$i$求出$nxt_i$表示其后面$a$值相等的第一个下标，然后一次询问就是求所有的$\sum(nxt_i-i)$，其中$l\le i\le nxt_i\le r$。转化为动态的二维数点问题，我用的是树状数组套平衡树，复杂度两个log。