退役后做题记录
AGC030E Less than 3
神仙题Orz
首先，如果你修改了一个位置\(i\)，那么\(i-1\),\(i+1\)一定不同，否则一定会出现连续三个一样的
将0和1之间插入一条红线，1和0之间插入一条蓝线。那么红蓝线一定交替出现
修改相当于移动一条线，移动方案相当于一个匹配（位置1以前、位置n以后可以看做有无数条红蓝交替的线）
最妙的是，“不能出现连续三个一样的”限制没有了（因为一定能找到方案）
枚举匹配的方案即可
AGC029B Garbage Collector
首先，取垃圾的代价固定，为\(nX\)，可以无视。
设取了\(K\)次垃圾，放垃圾代价就会是\(KX\)。
考虑一次取垃圾的过程，取了\(x_1<x_2<\ldots<x_s\)处的垃圾。
显然一定会先走到\(x_s\)，然后返回途中收辣鸡。
推一下，代价会是\(5x_s+5x_{s-1}+7x_{s-2}+9x_{s-3}+\ldots+(2s+1)x_1\)。
收了\(K\)次辣鸡，会有\(2K\)个系数\(5\)，\(K\)个系数\(7,9,11,\ldots\)，可以任意乘给\(x\)
显然最大的\(2K\)个拿\(5\)，以此类推，前缀和高高就行了
AGC018C Coins
首先消去\(C\)。所有\(A,B\)变成\(A-C,B-C\)，最后答案加\(\sum C\)，就不需要取\(C\)了，只要取\(x\)个\(A\)，\(y\)个\(B\)。
枚举一条分界线，左右都会从小到大取\(A/B\)，用一个堆维护
LOJ6294 touch
我是傻逼
先考虑\(\sum_{d|x}\mu(d)=[x=1]\)，我们要求\(\sum_{path}\sum_{d|\gcd\{path\}}\mu(d)\)，也就是对所有\(d\)求有多少条路径\(\gcd\)是其倍数
分开求跨过不确定边的路径和剩下的，不确定边把树分成了两棵树。
不跨过不确定边的路径直接求，枚举\(d\)后，只保留权值是\(d\)倍数的边。路径数是\(\sum \binom{siz}2\)，并茶几维护即可
跨过不确定边的路径，\(u,v\)分出了两棵树，搜出两棵树所有点到\(u/v\)的\(\gcd\)。两棵树的\(\gcd\)记为数组\(A,B\)
那么如果不确定的边权为\(w\)，这部分答案是\(\sum_{a\in A,b\in B,d|\gcd(a,b,w)}\mu(d)\)
设\(s_i=\sum_{a\in A,b\in B}[a|i][b|i]\)（注意0要特判）可以发现\(a\in A,b\in B\)会在\(\mathbb{lcm}(A,B)\)的倍数处计算一次。
那么如果\(i|w\)，答案加上\(s_i\mu(i)\)，就只会算一次了
CF1205B Shortest Cycle
记\(c_i\)表示二进制位有\(i\)的数数量，如果有\(c_i\ge 3\)那么答案就是3了，否则\(n\)很小，暴力
CF1205C Palindromic Paths
黑白染色后，对于一种颜色，只要确定了一个数就能确定整个颜色的标号，而且黑色已经确定了
然后怎么知道白色的标号呢？？？？？
暴力枚举，找到一个两种情况不同的询问，询问一下就行了。
CF1205D Almost All
神仙题
首先选一个点作树根，只考虑经过根的路径
那么先考虑一个问题，在一个大小为\(n\)的子树中，让每个点到根的路径长度凑出\(a,2a,\ldots,(n-1)a\)
这个很好构造。先找出所有儿子，分别为\(son_1,\ldots,son_m\)，子树大小为\(siz_1,\ldots,siz_m\)。根到第\(i\)个儿子的边权是\((1+\sum_{j<i}siz_j)a\)，然后对每个儿子递归下去做。
现在假设选了一个根节点\(rt\)，将儿子分为两组\(A,B\)，分别做上面的算法，其中\(A\)权值是\(1,2,\ldots,siz_A\)，\(B\)权值是\(siz_A+1,2(siz_A+1),\ldots,siz_B(siz_A+1)\)
那么从\(A\)到根节点到\(B\)的路径可以凑出来\(1\)到\((siz_A+1)(siz_B+1)-1\)中所有数
考虑怎么将儿子分组，\((siz_A+1)(siz_B+1)-1\)可以到达\(\lfloor\frac{2n^2}{9}\rfloor\)
显然两边尽量接近才能让结果更优
如果\(siz_A,siz_B\)都不小于\(\lceil\frac{n-1}{3}\rceil\)，那么最极端的情况就是\(siz_A=\frac{n-1}{3}\)，结果\(\ge (\frac{n+2}{3})(\frac{2n+1}{3})-1=\frac{2n^2+5n-7}{9}\)
需要的是\(\frac{2n^2}{9}\)。结果在\(n>1\)时正确，\(n=1\)无需考虑。
那么需要选一个根和划分让\(siz_A,siz_B\geq \lceil\frac{n-1}{3}\rceil\)
如果子树数量\(\ge 4\)，一定有两个子树大小之和\(\le \frac n2\)可以不断合并。
如果子树数量\(\ge 3\)，合并最小的两个子树，剩下那个大小一定\(\geq\frac{n-1}{3}\)，那么另一个大小也会\(\leq 2\frac{n-1}{3}\)。
子树数量为\(1\)只可能是\(n=2\)，无需考虑
合并完之后子树数量只可能为\(2\)，这时如果有一个子树大小\(\ge \frac{2}{3}(n-1)\)就不合法。
选重心做根，最大的子树大小小于等于\(\frac{n}{2}\)，就合法了。