\(\text{[AGC034C] Tests}\)

很容想到二分答案和 \(c_i\) 比较固定的选取方法
然后就不会了。。。
接下来就是要发现性质的时候
固定答案时，若此时已有了一组 \(a\)，考虑对于 \(0<a_i,a_j<X\) 的 \(a_i,a_j\) 加减 \(1\)
发现给 \(c\) 值大的 \(+1\)，小的 \(-1\)，新方案必然不劣
于是可以得到 \(a_i\) 是一堆 \(0,X\) 和一个 \(r(0<r<X)\)，这个 \(r\) 的位置可以枚举
那么按 \(calc(i,X)-calc(i,0)\) 排序后就可以二分 \(O(n) \text{ check}\) 了
提交记录

\(\text{[AGC001C] Shorten Diameter}\)

从最终状态考虑，找到最终状态的中心
那么从中心出发路径长度不超过 \(\frac k 2\)
直接枚举中心，\(dfs\) 把多余的删去即可，注意分 \(k\) 的奇偶

\(\text{[AGC003D] Anticube}\)

每个数改为对其质因数分解后的指数模 \(3\)之后的数，那么一个数只能与另一个可确定的数相乘为完全立方数
于是讨论每对数即可
注意到分解后大于等于 \(\sqrt[3]{x}\) 的因数最多有两个，所以分解时只需枚举到 \(\sqrt[3]{x}\)

\(\text{P2714}\) 四元组统计

不得不说莫反反傻了，容斥即可
记 \(g(i)\) 为四元组 \(\gcd\) 为 \(i\) 的倍数的方案数，\(f(i)\) 则是恰好为 \(i\) 的方案数
那么 \(f(i)=g(i)-\sum_{i|j}f(j)\)，于是从大到小算 \(f\) 即可

\(\text{CF853C Boredom}\)

矩阵有交比较难处理，那么容斥
发现就是要算八处而已，上下左右可以直接算，四个角落二维数点即可
为简化代码，可以四次翻转矩形

\(\text{[AGC003C] BBuBBBlesort!}\)

发现使用操作二可以对奇数位和偶数位免费排序，但不能改变一个数所在位置的奇偶
所以离散化后等价于求用操作一将奇数放到奇数位，偶数放到偶数位的最小次数
一次明智的操作一显然是让两个不在正确奇偶位的奇偶数归位
那么统计每个数与当前位置奇偶性不同的数量除以二即可

\(\text{[AGC010C] Cleaning}\)

想象乱七八糟的路径情况。。。
先找个度数大于一的为根
那么考虑一个非叶子结点 \(x\)，经过它的路径为子树中取两个叶子结点形成的路径和从它向祖先延伸出去的路径
考虑最终 \(a_x\) 要为 \(0\)
记从它向祖先延伸出去的路径个数为 \(f_x\)，则经过它的总路径为 \(s_x=\sum_{v\in son_x} f_v\)
那么要有 \(a_x=\frac{s_x-f_x}2+f_x\)， \(s_x-f_x\) 表示由子树内两个叶子结点形成路径
可以得到 \(f_x=2a_x-s_x\)，也就是说要延伸出去的路径数量一定
那判断是否可行则是要求 \(0\le f_x\le a_x\)
结束了！！！？
注意到过 \(x\) 且在 \(x\) 子树内的路径是要两两匹配的，从一个儿子出来的路径要配上从另一个儿子出来的路径
这个不一定可行

先考虑这样一个问题

若干个数，每次可取两个大于 0 的数，令它们同时减 1，问能否将所有数变为 0

结论：能的充要条件为所有数的总和为偶数且最大值不超过总和的一半
方案数是每次取出最大的两个数减 \(1\)

回到这题，我们有 \(f_x\) 次机会先让一些数减 \(1\)，然后满足结论：\(\forall v\in son_x ,f_v \le \frac{s_x-f_x}2=s_x-a_x\)
算出把 \(f_v\) 变得满足结论的最少次数与 \(f_x\) 比较即可
提交记录

\(\text{[AGC010B] Boxes}\)

区间操作不难想到差分，然后问题转化为一次操作给一个数加 \(n-1\)，其余均 \(-1\)，问能否全变为 \(0\)
注意到操作总次数一定，对每个数设 \(x_i\) 表示加 \(x_i\) 次 \(n-1\) 解方程即可
提交记录

\(\text{[AGC010D] Decrementing}\)

首先考虑一些比较简单的情况，如：不除以 \(\gcd\)
此时先手必胜的充要条件为：有奇数个偶数
那么考虑要除以 \(\gcd\) 时有奇数个偶数是否仍然是必胜状态
答案是肯定的
注意到初始数列 \(\gcd = 1\)，每次操作后都除以 \(\gcd\)，所以每个时刻都有 \(\gcd = 1\)
所以当有奇数个偶数时，必然至少还有一个奇数
先手操作一个偶数后，至少有两个奇数，\(\gcd\) 必为奇数，每个数除以奇数后奇偶性不变
所以留给后手的局面必然是偶数个偶数和至少两个奇数，此时后手无论怎样操作留给先手的局面都是奇数个偶数
又终止状态是全是 \(1\)，即偶数个（0）偶数，所以后手必败
于是我们明确了必败态和必胜态

必胜态：奇数个偶数
必败态：偶数个偶数且至少有两个奇数

发现只剩下有偶数个偶数且只有一个奇数的情况了
那么此时先手肯定不能操作偶数，因为操作后是必败态，所以必然操作奇数
而后 \(\gcd\) 是偶数，除掉后奇偶性未知，胜负未知，那么就视为一个新的游戏，重复上述过程
注意到至多有 \(\log V\) 次游戏，那么复杂度正确
提交记录

\(\text{[AGC010F] Tree Game}\)

感觉这题更简单（比 \(D\) 好想），一会就切了
或许是先做了 \(D\)，思路清晰多了
先找到必败点：若 \(a_u\) 能移到的点都大于等于它，\(u\) 为必败点
于是又发现必然决策：下一步走到比当前点小的点
注意到之后必然不会再返回（因为不优），所以就可 \(O(n)\) 判一个点的胜败状况了，总的就是 \(O(n^2)\)
怎么做到 \(O(n)\) 呢
既然一个点再也不会走回来时点，那么无论是判断哪个点时走到这个点，这个点面对的局面都是一样
记忆化一下就好了
提交记录

\(\text{[AGC010E] Rearranging}\)

这题真高思维。。。
开始的思路和官方题解一样，先考虑后手能干啥
发现他挺厉害的，唯独不能改变两个 \(\gcd > 1\) 的数的先后顺序
那么我们把两个 \(\gcd > 1\) 的数连边，发现是一些连通块
先手可以给每个连通块的每条边定向形成若干个 \(\text{DAG}\)，然后后手相当于找到一个字典序最大拓扑序
那我们的任务就明确了：给这些连通的边定向，使得字典序最大的拓扑序最小
独立的连通块单独考虑，显然希望最小的数是唯一入度为 \(0\) 的点，于是后手别无选择
那么 \(dfs\) 每次都从小到大访问能走到的数，尽量让小的在前面，尽可能让小的限制大的（感性理解
提交记录

\(\text{[AGC012C] Tautonym Puzzle}\)

神一样的构造题，明白正解只需要一步
将构造的序列分为两节，后一节为 \((1,2,3,...,100)\)
那么前一节构造一个长度为 \(x\) 的排列，于是合法的子序列数量即为前一节的上升子序列数量
要使得这个数量等于 \(n\)
考虑从小到大填数弄出这个排列，若当前数填到最后，则上升子序列数量乘 \(2+1\)；填最前，则 \(+1\)
那么 \(n\) 是从 \(0\) 开始不断乘 \(2+1\) 或者 \(+1\) 变成的
考虑怎么变成 \(n\)，从 \(0\) 开始显然不好知道接下来是乘 \(2+1\) 还是 \(+1\)
那么从 \(n\) 开始，如果 \(n\) 的最低位为 \(0\)，那么最后的操作必然是 \(+1\)，否则是乘 \(2+1\)
对应的变到 \(\text{n=n-1}\) 或者 \(\text{n/=2}\) 的问题解决即可
可以发现前一节的长度是 \(O(2\log n)\) （尽管这样的记法不严谨
提交记录

\(\text{[AGC012D] Colorful Balls}\)

或许是做了上面几道构造和博弈的题，猜结论越来越大胆了
第一条颜色相同的交换，使得我们可以把每种颜色单独提出来，满足重量之和不超过 \(X\) 的球成了这个颜色内的自由者
而不同颜色间的交换，只要看最小的球间能否交换，若能，手模一下发现这两种颜色内的自由者可以通过最小球进行交换
也就是说相对都自由了，然后推广到多种颜色，同样只要通过异色颜色的最小球便可跨颜色交换
这些颜色的答案就是多重排列个数了
要注意一种颜色的自由者可以通过与异色球的交换扩充（不得不说手动模拟加大胆猜结论使这题轻松 \(\text{AC}\)
提交记录

\(\text{UVA1521 GCD Guessing Game}\)

若回答为 \(t\)，那么选数的规模就降到 \(\lfloor \frac n t \rfloor\)
当 \(t=1\) 时必然是最劣的情况，而如果要猜的数是 \(1\)，那么回答就一直是 \(1\)
可以证明这是最劣情况，所以只需要考虑猜出 \(1\) 的最少步数即可
如何猜 \(1\) ？它是没有质因子的，所以把范围内的质数问一遍就好了
但质数可以“打包”起来问一次，若一些数乘起来 \(\le n\)，那就一起问，所以贪心双指针即可

\(\text{[NEERC2013] Hack Protection}\)

挖掘下 \(\text{AND}\) 的性质，发现与 \(\text{GCD}\) 是相似的
在区间左端点固定的情况，\(\text{AND}\) 值只有 \(\log V\) 个且单调不增
那么 ST table 加二分即可找到这 \(\log V\) 个右端点区间
\(\text{XOR}\) 限制用 vector 对每个前缀异或和的值记录存下位置再二分计数就行
做题备注：\(\text{GCD AND OR}\) 在区间扩展时的变化都是 \(\log V\) 次的

\(\text{[CERC2013]Rubik's Rectangle}\)

首先手模可以发现总是四个对称的位置在换，所以我们将矩阵分成若干四元组考虑
继续手模发现更换总是四元组的一个不动，其它三个旋转，且操作偶数次不改变矩阵其它位置
所以独立复原每个四元组，且操作的每行每列都要偶数次
那么先把最小的数归位到左上角，其它三个旋转即可

\(\text{[AGC012E] Camel and Oases}\)

比较好想的题，很容易转化到 \(\log V\) 层，每层选一条线段，问能否覆盖 \([1,n]\)，每次指定第 \(0\) 层选的线段
考虑指定了第 \(0\) 层的一条线段 \([l,r]\)，接下来要使选的线段覆盖 \([1,l-1]\) 和 \([r+1,n]\)
一开始想贪心，发现是假的，那么就状压 \(dp\)，从第 \(1\) 层开始
记 \(f_s\) 为当前各层选没选的状态为 \(s\)，从左往右最远覆盖到的点。\(g_s\) 则是从右往左
判断的话只要枚举 \(s\)，看 \(f_s,g_{\complement s}\) 是否覆盖了 \([1,l-1]\) 和 \([r+1,n]\)
转移时，线段选取顺序不一定按层递进，考虑这个状态的每个 \(1\) 作为最后一步走的层时的最远点
提交记录

\(\text{[AGC012F] Prefix Median}\)

神题。。。表示不太会
首先发现性质

\(a_i \le b_i \le a_{2n-i}\)
不存在 \(i,j(i<j)\) 使得 \(b_j < b_i < b_{j+1}\) 且 \(b_j > b_i > b_{j+1}\)

然后这是序列 \(b\) 存在的充要条件（
倒着 \(\text{DP}\)，考虑每次删除两个数后当前中位数位置的变化
设 \(f_{i,j,k}\) 表示当前第 \(i\) 位，中位数可选区间（即 \(a_i\) 到 \(a_{2n-i}\)）左边有 \(j\) 个数，右边有 \(k\) 的答案。考虑到一些位置在之前被删了，所以转移分别枚举向左或向右跳跃到哪里
提交记录

\(\text{[AGC006B] Median Pyramid Easy}\)

表示没有这种特殊情况观察的意识。。。
直接考虑过程中出现中间和左一位都为 \(x\) 的情况，那么接下来这两个位置一直到顶都是 \(x\)
于是依此构造即可

\(\text{[AGC006D] Median Pyramid Hard}\)

不好想
虽然中位数二分配合的套路题见过，但仍然没想到二分
那就考虑二分之后，将 \(a\) 改为：小于 \(mid\) 为 \(0\)，否则为 \(1\)
结合 \(B\) 的观察结果可以发现顶部答案取决于底部最靠近中间的 \(00\) 或 \(11\) 对
再特判没有 \(00\) 或 \(11\) 对的情况即可
回头想想为何二分答案是有单调性的，因为答案越大，原先底部最靠近中间的 \(11\) 就越难保持
所以一定是 \(11..10..00\) 的，临界点的 \(1\) 就是答案
提交记录

\(\text{[AGC006C] Rabbit Exercise}\)

考虑一只兔子一次跳跃期望位置的变化，发现是 \(a_{x+1}+a_{x-1}-a_x\)
这种序列操作变换就要考虑差分数组的变化，发现是交换 \(d_x,d_{x+1}\)
那么我们便得到一轮后的置换
然后要做 \(K\) 轮，自然的想法是找环 \(O(n+m)\)
不过学到了置换的快速幂，类似整数，\(O(n\log K)\)
提交记录1
提交记录2

\(\text{[AGC007B] Construct Sequences}\)

上个类似这样的构造也是 \(\text{AGC}\) 的题
首先考虑构造出 \(a_{p_i}+b_{p_i} = a_{p_{i+1}} + b_{p_{i+1}}\)，再调整
不难发现 \(a_i = i,b_i = {n-i}\) 满足
然后调整就给 \(b_{p_i}\) 加上 \(i\)，发现无法满足 \(b_i\) 降序
原因是原先 \(b_i\) 只差 \(1\)，调整空间太小，那么考虑放大差值，给 \(b_i\) 都成个大数再调整

\(\text{[AGC006F] Blackout}\)

好妙题
首先考虑把 \(x \longrightarrow y\) 连单向边，然后对于 \(x \rightarrow y \rightarrow z\) 就可以产生新边 \(z \rightarrow x\)
我们要统计可能产生的新边与旧边的数量
考虑对弱连通图 \(0\rightarrow 1\rightarrow 2\) 交替染色，那么有结论

染色成功，且三种颜色均出现，则这个弱连通图的贡献为 \(cnt_0cnt_1+cnt_1cnt_2+cnt_2cnt_0\)
染色成功，但三种颜色未全出现，则不能产生新边，贡献为旧边数
染色失败，则贡献为联通块点数的平方，即任意两点均可产生新边

第一条可以通过 \(x\rightarrow y\rightarrow z\) 构造归纳证明，考虑新加入一条边产生的新边
第三条考虑先证明 \(\{x\}\rightarrow \{x\},x\in \{0,1,2\}\)

对于弱连通图，可以把单向边变为双向边，然后对应使染色规则仍正确即可
提交记录

\(\text{[AGC007C] Pushing Balls}\)

期望神题
球受到顺序影响，球滚动距离的期望不好算
那么考虑算线段的贡献，每次移动一个球，问题规模缩小为 \(n-1\)
然后讨论线段 \(i\) 被球滚过，线段 \(i+1\) 被球滚过使这第 \(i\) 段长度的期望变化
然后算死人了。。。
其实可以把直线反过来对应线段相加把线段长度变为定值，然后再如上面讨论，答案除以 \(2\) 即可
提交记录

\(\text{[ARC120F] Wine Thief}\)

一个很显然的想法是考虑强制选 \(i\) 时的贡献，那就是序列剩下的选出 \(k-1\) 个数的方案数
先考虑长度为 \(i\) 的序列选出 \(j\) 个不相邻的数的方案数，由隔板法可得 \(f(i,j)=\binom{i+j-1}{j}\)
那么对于位置 \(i\) 而言，它的贡献是 \(\sum_{k1+k2=k-1}f(i-2,k1)\cdot f(n-i-1,k2)\cdot a_i\)
这是不方便计算的
可以做到 \(O(n)\)
考虑把除去三个后的序列从起点和终点拼起来，那么钦定所有位置 \(i\) 后的方案数均为 \(f(n-3,k-1)\)
但拼接处可以同时选，贡献要补回，于是记 \(S(l,r,k)\) 表示序列 \([l,r]\) 选出 \(k\) 个数的答案

后两部分为补回的贡献
第二部分表示强制选回两个端点，这两个端点的贡献
第三部分表示强制选回两个端点，两个端点以外的贡献
提交记录

\(\text{[ARC149D] Simultaneous Sugoroku}\)

自然的想法是考虑图像的变化，然后发现一条线段分为三部分，\(y=0\) 的点不动，\(y<0\) 加，\(y>0\) 减
这使得图变得乱七八糟
我们考虑简化，需要发现一条性质：
若两点的 \(y\) 互为相反数，那么它们之后的 \(y\) 也一直互为相反数。
于是将线段简化，只保留 \(x\) 轴上下更长的部分，短的部分可以对应到长的部分的答案，这个可以带权并查集维护
提交记录

\(\text{SP3377 A Bug's Life}\)

发现自己不怎么会带权并查集，所以做了道模板题
注意事项：
1.维护的是当前点到根的路径信息，每次路径压缩时要更新
2.合并时关系要通过两个根传递，也就是通过修改一个成为儿子的根的路径信息使合并的两点 \(x,y\) 符合要求
提交记录

\(\text{[NOI2001]}\) 食物链

没想到小学不想做的题现在补。。。
考虑关系形成的三元环，依次染色，颜色相同的表示同类
然后一条边就表示两端点的关系，合并时同样通过修改一个成为儿子的根的路径信息使合并的两点 \(x,y\) 符合要求
例如此题，记 \(x\) 吃 \(y\) 满足 \(d_x\equiv d_y+1 \pmod 3\)，那么合并 \(x,y\) 时，\(fa[rt_x]=rt_y\)
新边信息设为 \(z\)，则 \(d_x+z\equiv d_y+1 \pmod 3\)，有 \(z\equiv d_y+1-d_x \pmod 3\)
提交记录

\(\text{CF1500A Going Home}\)

一看先想暴力枚举，发现枚举两个就够了
但 \(O(n^2)\) 不行
再想了会，发现值域和 \(O(n^2)\) 完全不是一个级别
根据抽屉原理，很快就能找到另一对数，所以暴力是对的
大概就是 \(O(\min\{n^2,n+V\})\) 的吧
提交记录

\(\text{[ABC277G] Random Walk to Millionaire}\)

加深了对期望的理解：\(\text{solution}\)
在图上的游走，由于起点确定，终点不确定，所以正推 \(dp\)，且要算出从起点到某个状态的概率，这是我做过与以往所不同的地方（实际上之前的概率往往是 \(1\)，所以没有注意）。
另注意：\(E((X+1)^2)=E(x^2)+2E(x)+1,E(x^2) \not ={E^2(x)}\)
提交记录

\(\text{CF715C Digit Tree}\)

较复杂的树上路径计数问题
首先考虑点分治和树上启发式合并
发现一条有向路径可以通过预处理根到点，点到根的信息表示
那就树上启发式合并，接上来就很套路了，但路径的表达式挺复杂的，最后要让它模 \(M\) 余 \(0\)
那么需要统计的 \(y \longrightarrow x\) 的路径需要满足整理得

\(f_x\) 表示根到 \(x\) 的路径，\(g_x\) 则相反，\(z=lca(x,y)\)
注意 \(x \longrightarrow y\) 的路径是不一样的，也要统计，式子就是把上式的 \(x,y\) 交换
当然，为了方便统计，必然是要把 \(x\) 分离出来的，这些都是基操了
提交记录

\(\text{CF1322B Present}\)

位运算当然拆位分别算，可这里有个加法，可能导致进位，于是情况比较复杂
那就只考虑当前位 \(k\) 的贡献，包括进到这位的 \(1\)
发现要考虑两数低 \(k\) 位才可以确定两数和在第 \(k\) 位的情况
可以算出只有两数低 \(k\) 位和在 \([2^k+1,2^{k+1}-1]\) 或 \([2^{k+1}+2^k,2^{k+2}-1]\) 时第 \(k\) 位才为 \(1\)
这个可以排序后双指针统计，\(O(n\log n\log V)\)
(不怎么会写，WA了好多次，注意位数上限开大点不会死
提交记录

\(\text{P3760 [TJOI2017]}\) 异或和

做了上面那道题后，再次回顾这道题，发现思路是一样的
做前缀和后，不考虑借位到哪，只考虑第 \(k\) 位的贡献
两数作差，分别考虑第 \(k\) 位为 \(0/1\) 的 \(4\) 种情况，发现需要考虑低 \(k-1\) 位才能确定第 \(k\) 位
于是分类讨论，树状数组统计，\(O(n\log^2 V)\)
提交记录

对于这题，之前还学了一种 \(nb\) 数据结构做法
考虑能否做这样的东西：有一堆数，支持每次给这堆数加 \(1\)，维护这堆数的异或和
从低位往高位建 \(Tire\)，\(Trie\) 结点维护子树内异或和，那么就可以模拟加 \(1\) 操作，遍历 \(Trie\) 的右子树，交换当前结点的左右子树实现加法
提交记录

\(\text{CF1271D Portals}\)

显然的贪心是在某个城堡的最晚控制时间控制这个城堡，然后考虑最大化 \(c_i\)
\(n\) 和士兵数量这么小，直接 \(dp\) 把信息记进状态里，\(O(n^2)\)
不过这并不好，考虑按 \(c_i\) 从大到小贪心，因为一个城堡只需 \(1\) 个士兵就可以控制，那么控制了大的城堡，以后至多使一个小的城堡不能选，这是优秀的，\(O(n \log n)\)
再考虑反悔贪心，在某个城堡的最晚控制时间控制这个城堡，可能导致后面打不动，那就在后面打不动的时候再反悔。因为控制代价都是 \(1\)，显然反悔 \(c_i\) 小的优，\(O(n\log n)\)

\(\text{CF707D Persistent Bookcase}\)

操作 \(4\) 是不好维护的，这个一般想到可持久化数据结构
但这是打不动的了
看了题解，明白了另一个显然而又很容易被忽略的东西：操作树
离线后，把操作树建出来，在上面跑操作，就没了 \(4\) 操作，且方便回溯，\(O(q)\)
提交记录

\(\text{CF1311F Moving Points}\)

讨论一下贡献即可，发现是二维偏序，然后就没了

\(\text{CF1151E Number of Components}\)

直接算不好算，考虑容斥，假设每个 \(f\) 连通块数量都是 \(n\)
然后考虑合并连通块，通过边来容斥是极好的，考虑一条边什么时候会把两端点并起来
最后考虑点会消失的情况，总的减去这些即可
提交记录

\(\text{CF1288E Messenger Simulator}\)

最靠上的位置判一下是否会是 \(1\) 即可
最靠下的位置有两种情况会贡献
1.在 \(x\) 提到 \(1\) 前比 \(x\) 大的数提到了 \(1\)，统计这样的数的种类
2.在 \(x\) 提到 \(1\) 后且在 \(x\) 下次再提到 \(1\) 前提到了 \(1\) 的数，统计这样的数的种类
以上正反扫一下用线段树便可很好地维护
\(\text{warning: }\) 注意线段树维护的区间范围，尤其是在重复用而实际维护信息范围不一样时！
提交记录

\(\text{CF1158C Permutation recovery}\)

显然的思路是确定大小关系，通过连边拓扑排序就可以构造一组解了
那么 \(nxt_i\) 给的限制就是 \(p[i]<p[nxt_i]\) 且 \(\forall j \in [i+1,nxt_i-1],p[j]<p[i]\)
那这样就是 \(n^2\) 的建边了
考虑优化，无脑线段树建图是无脑的，考虑去掉一些重复的限制
“且”字后面的限制就是给 \(j\) 找左边比它大的位置 \(i\)，由大小的传递性可知只要找到最右的比 \(j\) 大的 \(i\) 即可
处理出这个即可。这个过程类似染色覆盖，考虑倒着扫并查集维护，\(O(n\alpha)\)
提交记录

\(\text{CF677D Vanya and Treasure}\)

对每个格子按数字分层后考虑 \(dp\)，暴力转移是 \(O(n^2m^2)\) 的
大力拆绝对值树状数组维护并不优美，考虑根号分治
当两层 \(w_{i-1}w_i \le nm\) 时暴力转移，否则用上一层的点在原图中 \(spfa\) 出其到每个点的最小值来转移
后者显然是 \(O(nm\sqrt{nm})\)，前者用柯西不等式也可证明是这个复杂度的

\(\text{CF1039D You Are Given a Tree}\)

对于一个具体的 \(k\)，可以 \(O(n)\) 贪心解决，然后？
发现答案不超过 \(\frac n k\)，只有 \(O(\sqrt n)\) 种了
只要做 \(O(\sqrt n)\) 次贪心就行了。由答案单调性知可二分确定那些 \(k\) 的答案和当前答案一样
这样是 \(O(n \sqrt n \log n)\) 的，恐怕不行
考虑根号分治，再平衡复杂度：
当 \(k\le B\) 时，直接贪心，省去 \(\log\)，\(O(n\sqrt n)\)
当 \(k > B\)，时，用上面做法，\(O(\frac {n^2} B \sqrt n \log n)\)
取等可知 \(B=\sqrt{n\log n}\) 时最优，\(O(n\sqrt{n\log n})\)
提交记录

\(\text{CF662B Graph Coloring}\)

挺好想到的，一条边最后是什么颜色取决于两端点翻转的奇偶，最优则每个点要么翻一次，要么不翻
分别计算都染成 \(R\) 或 \(B\) 的答案
很容易想到黑白染色，选择 \(0/1\) 少的作为翻转点，然后就没了
\(\text{warning:}\) 图不一定连通！
提交记录

\(\text{CF1540B Tree Array}\)

模拟这个过程很困难，无法设计出状态，每步概率受制太多，无法算期望
钦定每个点为根，然后从根开始扩展
考虑拆开贡献。\(n\) 很小，直接枚举产生贡献的点对 \((i,j),i>j\)，计算 \(i\) 被扩展到的时间早于 \(j\) 的概率
那么扩展过程一定是从根到 \(LCA\) 再分叉，先到 \(i\) 再到 \(j\)
这只与它们距最近已被扩展点的距离有关，记 \(f_{x,y}\) 表示距 \(i\) 距离为 \(x\)，\(j\) 为 \(y\)，先到 \(i\) 的概率
当最近已被扩展点在 \(LCA\) 以上时，有 \(f_{x,y}=pf_{x-1,y-1}+(1-p)f_{x,y}\)，解得 \(f_{x,y}=f_{x-1,y-1}\)
这启示我们只需考虑从 \(LCA\) 开始的距离即可
此时有 \(f_{x,y}=p(f_{x-1,y}+f_{x,y-1})+(1-2p)f_{x,y}\)，解得 \(f_{x,y}=\frac 1 2 (f_{x-1,y}+f_{x,y-1})\)，\(O(n^2)\) 预处理即可
然后就是定根枚举点对统计答案了，\(O(n^3)\)
提交记录

\(\text{CF1406D Three Sequences}\)

大致画出 \(b,c\) 的曲线，发现让它们最高点最接近最优。这是总能做到的，一条整体加另一条减即可。
于是 \(|b_n-c_1|\le 1\)。
怎么让 \(b,c\) 满足限制呢？对 \(a\) 差分一下，分成两部分，一部分均大于等于 \(0\)，一部分均小于等于 \(0\) 即可
然后分法总是有一个是 \(0\)，这个可以尝试加减后发现均不优，于是有了结论就可以解方程组了
\(\text{warning:}\) 正数和负数向上取整要注意。以前正数向上取整我总是 \(+1\) 后用直接除以，然而这不适用于负数！且 c++ 的除法是向 \(0\) 取整。
提交记录

\(\text{CF662C Binary Table}\)

考虑将列压成一个二进制数后枚举行翻不翻，则有

\(H_s\) 表示原来列中有多少等于 \(s\)，\(C_s\) 表示 \(s\) 进过翻转后最少的 \(1\) 的数量
直接 \(\text{FWT}\) 就好了
提交记录
（怎么那么慢啊！！！

\(\text{CF889E Mod Mod Mod}\)

\(dp\) 状态的优化有点神奇。。。
首先发现最优的 \(x\) 必然存在某次模 \(a_i\) 后变成 \(a_i-1\)
若不然，将 \(x\) 加至 \(a_i - 1\) 更优
于是 \(O(n^2)\) 就很好想了
考虑 \(f_{i,j}\) 表示做到位置 \(i\)，当前余 \(j\) 的最优答案
把贡献的图画出来发现答案可以写成 \(kx+b\) 的形式，那 \(dp\) 维护最大的 \(b\) 即可
两种转移：直接模下一个 \(a\)；整体向下平移，使得模下一个 \(a\) 后是 \(a-1\)
提交记录

\(\text{[ABC254F] Rectangle GCD}\)

被绿题干碎了。。。
虽然莫名想到差分却不知道有什么用，其实应注意到一件事：\(\gcd(a_i+a_j,a_i+a_{j+1})=\gcd(a_i+a_j,a_{j+1}-a_j)\)，更相减损法就把后数的 \(a_i\) 消去了
考虑一行 \(\gcd(a_i+a_j,a_i+a_{j+1},a_{i}+a_{j+2}...)=\gcd(a_i+a_j,a_{j+1}-a_j,a_{j+2}-a_{j+1},...)\)，那么就只要求差分数组和左端点的 \(\gcd(a_i+a_j,d_h)\)
考虑每行，则有 \(\gcd(a_i+a_j,d_h,a_{i+1}+a_j,d_h,...)=\gcd(a_i+a_j,d_h,d_l)\)，这个就很好维护了

\(\text{[ARC150B] Make Divisible}\)

简单数学题
\(k=\frac{B+Y}{A+X}\Rightarrow kA+kX=B+Y\Rightarrow X \ge \max(0,\lfloor \frac{B-1}k\rfloor+1-A)\)
这是由 \(X,Y\ge 0\) 得到的条件
又 \(kA+(k+1)X-B=X+Y\Rightarrow X=\max(0,\lfloor \frac{B-1}k\rfloor+1-A)\)
这是在 \(k\) 固定时最优的 \(X\)，数论分块即可
提交记录

\(\text{[ABC254Ex] Multiply or Divide by 2}\)

很容易想到 \(x\leftrightarrow \frac x 2,x\leftrightarrow 2x\) 这样的建图，贪心匹配即可
然后直接乱写一通，\(7\) 发才过
因为这样的建图点编号值域很大，重编号需要用 \(map\) 之类的东西，这样就是 \(O(nlog^2V)\) 的
精细实现才过得了
提交记录
官方题解给了个优美的建图方式，数字转换成字符串，利用 Trie 来完成
这个 Trie 不需要高位补齐，这样就可以符合除以 \(2\) 少一位的需求了
提交记录

\(\text{[AGC003E] Sequential operations on Sequence}\)

看着非常简单的题，知道有很多重复，那怎么记录呢
首先可以单调栈留下对答案有用的操作 \(Q_i\)
考虑倒推出 \(f_i\) 表示 \(Q_i\) 在最终状态的重复次数
处理余数，发现这个问题是类似的，找到最后一个小于等于 \(Q_i\) 的 \(Q_j\)，继续处理新的余数
递归处理即可
提交记录

\(\text{P8863 KDOI-03}\) 构造数组

记 \(\frac{\sum b_i} 2\) 为 \(tot\)，那么就是在 \(tot\) 个二元操作组上填数，满足同组 \(\text{first < second}\)
考虑 \(n\) 个数组位置顺序插入操作组，那么就只要记录有多少二元组已经被填满，有多少只填了一个，有多少还没填
知道有多少二元组已经被填满后，另两个信息可以算出来
且对于当前要填的数组位置，并不关心已经填了的二元组具体的位置，只要知道多少即可
所以设 \(f_{i,j}\) 表示考虑完前 \(i\) 个数组位置，操作组中已有 \(j\) 个二元组被填满的方案数，转移枚举 \(a_i\) 有多少配填了一个的二元组，剩下的放没填的二元组的第一个位置即可。\(O((\sum b_i)^2)\)
提交记录

\(\text{CF1720E Misha and Paintings}\)

记矩阵中不同数的种类为 \(cnt\)
那么当 \(cnt \le K\) 时答案为 \(K-cnt\)，否则为 \(1\) 或 \(2\)
构造方式是容易的，判断是否是 \(1\) 需要知道一个子矩阵内完全包含的颜色的种类数，进而推出外面有多少种颜色
考虑每种颜色被哪些左上角的矩阵完全包含，发现需要先知道矩阵大小。
而知道矩阵大小后，发现这样的矩阵的左上角在一个矩阵中，二维前缀和即可
提交记录

上面利用二维前缀和解决的问题是一个子矩阵内完全包含的颜色的种类数，也即一个子矩阵外面的颜色种类数
\(O(n^2)\)，限制是要知道子矩阵的大小
之前有道 \(\text{ABC278E}\)，可以直接枚举每种颜色再判是否被完全包含，优点是无所谓子矩阵的大小

而在 \(\text{P5953 [POI2018]Różnorodność}\) 中则需要解决知道子矩阵大小，子矩阵内部的颜色种类数这个的问题
思路仍然是考虑颜色的贡献，扫描线一行行扫维护当前行每一列为左上角的答案
扫下去时删去一行加上一列，考虑变化的颜色对目前维护的矩阵左上角答案的影响，是连续的一段，用平衡树等数据结构可以找到，然后差分修改。问题相似 （迥乎不同），于是一起写了。

\(\text{P3676}\) 小清新数据结构题

问题好唬人
仔细思考，发现不知道维护什么东西，那就考虑换根计算答案需要什么
首先明确绝对是要以固定的根算换根后的答案的
记 \(s_i\) 为 \(i\) 的子树点权和，已经知道以 \(1\) 为根时的答案
那么换根就是考虑增量，写一下贡献发现只要维护 \(x \rightarrow 1\) 路径的点权和
而修改就明确了，同样要考虑以 \(1\) 为根答案的增量以便维护
提交记录

\(\text{P8860}\) 动态图连通性

问题好唬人 \(\times 2\)
感性的想法是找到一条 \(1\) 到 \(n\) 的路径使它的边在询问中出现尽量晚或没有出现过
于是考虑给每条边加权，使得一条路径只要有一条边删得早就比另一边路径劣
所以给每条询问中出现的边权设为 \(2^t\)，\(t\) 是倒着的时间戳，然后跑最短路，主席树维护 \(dis\)，线段树上二分比较大小，哈希判断 \(LCP\) 是否相同。
\(\text{Warning}\)：\(\text{dijkstra}\) 使用优先队列时点的权值要写进结构体里！注意到懒惰删除的影响，当一个点被松弛重新加入队列中，它要与之前的它在权值上有所区分，这样才能利用堆的结构正确更新优先队列。
提交记录

\(\text{CF1322C Instant Noodles}\)

自然的想法是考虑左部点怎样产生贡献，然而并没有用。
考虑右部点 \(u\) 的贡献，此时要考虑它如何出现的答案的 \(\gcd\) 式子中，记连接它的左部点点集为 \(R(u)\)
当 \(R(u)=\emptyset\)，它没有贡献
然后不好考虑了。那么连着 \(v\) 一同考虑
当 \(R(v)=R(u)\) 时两者的和做贡献，且只有两者的和做贡献，即 \(u,v\) 可并作一点
当 \(R(v)\not = R(u)\) 时，取二者交集贡献为二者之和，否则二者都有可能分别做贡献
此时考虑这样一件事情 \(\gcd(a,b,a+b)=\gcd(a,b)\)，所以等价于二者分别做贡献
于是哈希判断是否相等即可
提交记录

\(\text{CF1446C Xor Tree}\)

多数异或不难想到 Trie
发现异或值最小的两数连边使得它们是在同一棵子树内的两个点连边，除非本子树只有一个数才会连到另一棵子树
不难发现两左右子树只能完全保留一棵，另一棵为 \(1\)，所以树形 \(dp\) 一下即可
提交记录

\(\text{CF1579G Minimal Coverage}\)

模一下样例发现贪心是错的，那就 \(dp\)。发现状态只关心已覆盖长度与当前起点距端点距离，然后简单转移即可
提交记录

\(\text{CF1444C Team-Building}\)

自然的想法是取出两组黑白染色判是否是二分图
但注意到取出两组边数总和很少，所以先对边按组排序，直接枚举边统计答案，\(O(m)\)
但若两组无边，组内又是二分图，它们组合同样可以产生贡献
所以容斥，不合法的要么是组内不合法，要么两组有边推出不合法
判断不合法用扩展域并查集，切换组的配对时撤销即可
注意不要算重！！！
提交记录

\(\text{CF1401F Reverse and Swap}\)

先观察 \(reverse\) 和 \(swap\) 的联系
一看是想把 \(swap\) 转成 \(reverse\)，结果 \(WA\) 了，发现是标记没处理好
其实把 \(reverse\) 转成 \(swap\) 更直观好写，注意到线段树上 \(reverse\) 的操作毕竟是不断 \(swap\) 左右子树
提交记录

\(\text{CF1415E New Game Plus!}\)

开始觉得一眼看出的贪心很对，结果样例 \(3\) 过不了
然后想到每次清零都是一个新的开始，于是把过程分成 \(k+1\) 段一同考虑
然后发现全是负数就很好做了，倒着填即可。
刚开始让正数加部分负数占一段特殊处理，剩余负数填进 \(k\) 段里，结果 \(WA\)。
其实仍旧可以充分利用 \(k+1\) 段，把正数恰好变成负数之后的那个负数（与剩余负数想比一定最大）与剩余负数一同考虑，这样就可以利用 \(k+1\) 段了
提交记录
还有更好的贪心：同样是利用 \(k+1\)，注意到正序每次将一个数 \(x\) 填入第 \(i\) 段，有变化：\(ans+=sum_i,sum_i+=x\)，发现每次取最大的 \(sum_i\) 即可

\(\text{CF1415D XOR-gun}\)

思路正确，不过想法复杂，以为要枚举断点再枚举位，预处理一些东西快速找最优的 \(l,r\)
其实观察到若三个相邻的数最高位相同，那么答案为 \(1\)。
数列递增，根据抽屉原理，最坏情况下只有两个相邻的数最高位相同，那么 \(n > 60\) 时答案就为 \(1\)
剩下暴力 \(O(n^3)\) 做就好了

\(\text{[AGC027C] ABland Yard}\)

想要走出所有的字符串必然需要从一个点出发可以走到 \(A\) 和 \(B\)，接着仍然可以走到 \(A\) 和 \(B\)
也就是说找一个子图满足从每个点出去都有 \(A\) 和 \(B\)