自闭集训 Day6
杂题选讲
CF round 469 E
发现一个数不可能取两次，因为1,1不如1,2。
发现不可能选一个数的正负，因为1,-1不如1,-2。
hihoCoder挑战赛29 D
设\(f(x)\)表示最后一个数小于等于\(x\)的答案，从左往右加入数并维护\(f(x)\)。
加入\(A\)的时候\(f(x)\)要加上\(|x-A|\)，再对\(f(x-1)\)取min。
显然\(f(x)\)是一个分段函数，而且斜率是连续整数。
于是只需要维护拐点就可以知道函数长什么样。每次就是加入两个拐点，并删掉最右边的一个，用堆维护就没了。
CS Academy #32 G
设\(f_{i,j}\)表示放了\(i\)个数和为\(j\)的方案数，每次转移是多放一个1或是所有数加1。
考虑每个数\(s\)对答案的贡献，贡献次数就是\(\sum_{i=1}^{\infty} [至少i个当前的方案数]\)。
发现这东西刚好就是\(\sum_{i=1}^{\infty} f_{K-i,n-is}\)，于是可以直接求和。
于是做完了……
THUPC 2017 I 小L的游戏
？？？
应该有比老师更优美的做法……
星空 by 杨家奇
首先这题显然是个循环卷积，模数998244353-1有因子17，所以不必担心。
设\(f_S\)表示在\(S\)中随便选的方案数，\(g_S\)表示\(S\)连通的方案数。（\(g_0=0\)）
于是有\(f=e^g,g=\ln f\)。其中乘法为子集卷积。
考虑子集卷积的过程：记录\(f_{i,S}\)，当且仅当\(|S|=i\)的时候\(f_{i,S}\)有值，然后把\(f_i\)看做一个元素，这个元素的乘法定义为或卷积，难么\(f*g\)就可以看做是多项式乘法，只不过乘完之后要把多余的元素清除掉。
把\(f_i\)做莫比乌斯变换，于是元素的乘法就是对应位置相乘。
然后把两维反过来变成\(f'_{S,i}\)，此时枚举\(f'_S\)，就真的变成多项式乘法了，于是\(\exp\)也就可以定义了。
于是\(\ln\)也可以定义出来了，于是就做完了。
SRM 702 Finding Friends
二分答案，每个点记录\(l_i,r_i\)表示左右最近的满足条件的点。
然后一个区间\([L,R]\)合法当且仅当每个点都有\(l_i\ge L\)或\(r_i\le R\)。
然后记录\(solve(L,R)\)表示\([L,R]\)里面是否有满足条件的区间。
从两边往中间扫，如果发现了必然不满足条件的点就删掉然后往两边递归。
惊奇地发现复杂度是对的，就做完了。
SRM 713 Coins Query
注意体积很小，可以只记最后100个状态，然后矩阵乘法。
注意转移矩阵相同，所以就\(O(n^3\log m)\)了。
VK Cup 2017 Round 3 F
考虑倍增，设\(f_{n,p}\)表示在\([1,n]\)里面选数，最大的奇偶性为\(p\)的生成函数。
倍增，随便转移。
我怎么永远都想不到倍增
SRM 715 Pre In Post
设\(f_{x,y,a,b,i}\)表示第一个序列\([a,a+i)\)，第二个\([b,b+i)\)，遍历方法是\(x,y\)，是否可能。
如果遍历方法相同那么直接判是否全部相等。
如果不同，那么我们肯定可以知道根是什么。
如果有一个是中序遍历，那么变成了子问题。
否则，枚举分界点在哪里。
复杂度莫名其妙地就对了？？
Codechef SNCKEL17
题目相当于动态修改边权，问最小生成树里面的最大边权。
可以LCT+线段树分治，\(O(n\log^2 n)\)。
R-C算法：
- Reduction。把修改涉及的边设成\(\infty\)，跑最小生成树，不在其中的边肯定废了。
Contraction。把修改涉及的边设成\(-\infty\)，~~~，在里面的边肯定在里面，直接缩起来。
然后分治两边，同样可以证明\(O(n\log^2 n)\)，然而不会证……
THUPC 2017 D
先随机一个初始解，然后调整。
找到一个挂了的点，调成一个似乎是ok的颜色（但可能调完之后某个邻居又挂了），用队列模拟这个过程。
每次调完之后两端颜色相同的边数减一，所以复杂度\(O(m)\)。
