1. ARC183D Keep Perfectly Matched
思考了一会后，发现答案是存在一个上界的：以重心 \(r\) 定根，一条边至多经过 \(sz_i\) 次。
而这个东西一出来，就知道一定是能顶到的了，因为太典了。我们考虑，当且仅当，每次删除的两个叶子，都属于 \(r\) 的两颗不同子树，符合要求。而一次删除，怎么样才能让剩下的树依旧有完美匹配呢？
首先一棵树若有完美匹配则唯一。考虑删除叶子 \(s,t\)，发现有一种显然的情况：若 \(s\leftrightarrow t\) 的路径长度为偶数，且原先的树中，路径上的第 \(2i\) 个点恰好和第 \(2i+1\) 个点匹配。则我们删除 \((s,t)\) 后，只需要把这条路径的边反转，就能重新找到一组完美匹配。
另一方面，其他情况下很难说明删去 \(s,t\) 后一定存在匹配。于是猜测使用这一种 \((s,t)\) 足够完成目标。
考虑 \(r\) 一定和某一个节点 \(x\) 匹配，则让 \(s\) 是 \(x\) 子树内的某个叶子；随意选择另一个 \(r\) 的儿子 \(y\)，然后 \(t\) 是 \(y\) 子树内的某个叶子。
如何寻找 \(s,t\)？我们分别从 \(x/y\) 开始：如果它的儿子里有一个点和它匹配，就走到这个儿子；否则随意走一个儿子。最后走到的两个叶子分别作为 \(s,t\) 就是符合题设的。
这使得第一次删除成立。为了让 \(r\) 依旧是重心，我们应该选取一个大小最大的 \(y\)。于是我们证明了一定能顶到上界，并且根据上面的方法容易写出 \(O(n^2)\) 的程序，瓶颈在于每一轮都需要重新寻找 \(r\) 的某个子树内的一个合法叶子。
观察上面的寻找过程，发现对于一个子树，按照上述过程跑 dfs 遍历（也就是说如果儿子是匹配点就优先遍历这个点），提取出后序 dfs 序，得到的就是对这个子树每次找叶子的结果。
因此在 \(O(n\log n)\) 的时间内解决了本题。瓶颈在于每次选择 \(sz\) 最大的作为 \(y\) 需要一些 STL 维护。
2. ARC183E Ascendant Descendant
作出初步观察：为每个 \(a_i\) 向左右两侧拓展得到区间 \([l_i,r_i]\)，直到 \(b_{l_i-1}\) 和 \(b_{r_i+1}\) 都不在 \(a_i\) 的子树内位置。很显然，\(a_i\) 最后去到的范围一定在 \([l_i,r_i]\) 内。
但是这个不充分啊，万一我想从 \(x\) 换到 \(y\)，然后 \(x\sim y\) 中间有个不能动的咋办？
那这样的话，发现这个位置的活动范围一定比我们当前算的这个人小。因此我们如果能按照范围的偏序关系，算出每一个人的真实活动范围就好了。
需要观察到原始区间是没有包含且不相交这种关系的，所以建出树形结构后从下往上计算会很方便。按照从小到大的关系进行收缩就行了。什么时候需要收缩？当且仅当一个点的子树内的区间数和它代表的区间长度相同，那外界的数就进不来了，于是这些点被标记。收缩的时候就是说，从 \(i\) 向两边第一次碰到收缩的位置就应该停下来了。
这样的话得出了每个位置真正能放置的区间，同样满足树形结构。方案数就好算了，需要注意的是相同 \(a_i\) 的去重：这里需要注意到不可能有祖先后代关系的相同的 \(a_i\)。
3. qoj9220 Bus Analysis
不知道为啥这个题做的还挺快。
就是，对于一个固定的情况，好像不是很能设计一个很简明的贪心或者其他算法来求答案，还是得 dp？所以说就考虑用 dp 套 dp 来维护了。那么如何维护内层的 DFA 呢？
先把题目中的代价都除以 \(2\)。然后有性质：若当前车站不取上个车站的最优解，所花费的代价也至多多出 \(2\) 而已（因为在上一个车站的最优解基础上，在这个车站添加一个代价为 \(3\) 的车票就能让保护时间到达 \(75min\) 的最大值。
所以维护一个三元组 \((x,y,z)\) 表示最优解/最优解+1/最优解+2时的最小延迟时间，作为 DFA 的节点状态描述。可以搜出来减少状态数。然后做完了。
4. AGC003E Sequential operations on Sequence
这个题还是挺急转弯的我觉得。首先如果 \(q_i\ge q_{i+1}\) 那这个操作就没用。然后我们把 \(q_i\) 看成升序的。
想知道时刻 \(i\) 的序列的前 \(x\) 个信息，等价于知道时刻 \(i-1\) 的序列的前 \(q_{i-1}\) 个信息和前 \(x\bmod q_{i-1}\) 个信息。所以我们倒推：一开始我们想知道时刻 \(m\) 的序列的第 \(q_m\) 个信息记作 \((m,q_m)\)，他就会分裂成 \((m-1,q_{m-1})\) 和 \((m-1,q_{m}\bmod q_{m-1})\) 两个信息，重复这个过程。发现可以把相同的二元组合并统一处理。那么从 \(q_i\rightarrow q_{i-1}\) 的时候，可以认为至多新增一个信息（因为每次分裂，分裂出来的第一个一定都是 \((i-1,q_{i-1})\)，可以把它们合并成一个），而原有的每个信息会做一次取模。可以发现一个数最多进行 \(O(\log)\) 次有效取模，所以复杂度可以保证。
5. ARC129D -1+2-1
算是一道曾经困扰了我一段时间的题吧，偶然想起来后解决了。
显然整个操作过程中不改变 \(\sum a\)，因此若 \(\sum a\neq 0\) 无解。
观察操作，会发现体现在前缀和视角上的话，就是 \(s_{i-1}\) 减去 \(1\)，\(s_{i}\) 减去 \(1\)。
但是对于 \(i=1/n\) 的情况则不然。观察其对 \(s\) 序列的影响：
-
\(i=1\)：我们会把 \(s_1\) 加上 \(2\)，然后把 \(s_{2}\sim s_{n-1}\) 加上 \(1\)。
-
\(i=n\)：我们会把 \(s_n-1\) 减去 \(2\)，然后把 \(s_{1}\sim s_{n-2}\) 减去 \(1\)。
发现：若 \(\sum s\) 不为 \(n\) 的倍数则无解。否则先通过两种特殊操作调整令 \(\sum s=0\)。
接下来使用一般操作将 \(s_{1}\sim s_{n-1}\) 变为 \(0\)，我们的操作就是把前面一个数减一，后面一个数加一。所以整个过程中，\(s\) 的前缀和数组（\(t\)）应该始终非负。
如果为负了呢？这就是样例 4 的情况，发现我们上面忽略了一步：两种特殊操作可以做任意多次，只要他们的差是一个定值即可。而同时做一次两个特殊操作会怎么样？观察发现恰好令 \(s_1\) 加上了 \(1\)，\(s_{n-1}\) 减去了 \(1\)。所以再使用一些步数使得前缀和非负即可。
时间复杂度 \(O(n)\)。
6. AGC004F Namori
这个题真的特别牛啊？
考虑树的部分分：这个操作比较眼熟，在曾经的 open cup 某题也有出现。套路是二分图染色，把一部分点的颜色翻转。这样操作就相当于交换两个点的颜色：目标是让每个点的颜色取反。所以黑白颜色的点数需要始终保持相同。
再算最小步数，依旧考虑算贡献：对每条边算子树内黑白颜色点数之差即可，绝对值求和即为答案。
再考虑上环：奇环的话不是二分图了等会考虑，先考虑偶环。环外子树相同方法算，现在就是变成环上每个点有一个数，每次操作可以让一个位置给一个邻居传递一个 \(1\)，问最少步数让所有点都变成 \(0\)。这不是我们糖果传递吗？
再考虑奇环，我们就考虑多出来的那条边：还是在黑白点的意义下考虑，那就相当于是消掉两个黑点/白点。所以我们知道这条边到底操作了多少次，假设操作了 \(k\) 次，如果是白点少，就在两端点处都放上 \(k\) 个白点，否则都放上 \(k\) 个黑点。接下来变成树的 case 去做。这个转化正确性是因为，两边多的白点移动到黑点的过程，倒过来看，其实是两个黑点移动过来然后被删除成为白点的过程啊。
时间复杂度 \(O(n)\)。
7. ARC182C Sum of Number of Divisors of Product
令 \(k\) 是 \(\le m\) 的质数个数，这个做法至少可以做到 \(O(k3^k)\)。
先算 \(n\) 固定的答案。
对于一个序列 \(a\)，设 \(\alpha_{i,j}\) 是 \(a_j\) 中含有质因子 \(p_i\) 的数目，则我们所求即为：
\[\sum_{a}\prod_{i=1}^{k}(\sum_{j=1}^{n}\alpha_{i,j}+1) \]考虑将括号拆开，提取每一个 \(k\) 个数相乘得到的项，并且求它在所有序列里的贡献。
也就是，指定一个长度为 \(k\) 的序列 \(d_1,d_2,...,d_k\)，其中 \(d_i\in [0,n]\)，然后求所有序列里 \(\prod_{i=1}^{k}\alpha_{i,d_i}\) 的和（令 \(\alpha_{i,0}=1\)）。
注意到：\(n\) 很大而 \(k\) 很小。所以本质不同的 \(d\) 序列并不是很多，最多也只有 \(Bell(k+1)\) 种。
因此先暴力枚举一个 \(d\) 序列，再去算答案。假设 \(d\) 序列的值域恰好为 \([1,c]\)，则它其实对应了 \(A_{n}^{c}\) 个 \(d\) 序列，还要考虑剩下的 \(n-c\) 个位置任意取值，方案数贡献 \(m^{n-c}\)。而对于一个 \(d\) 序列而言，考虑第 \(1\sim c\) 个变量的取值是互相独立的。因此对于每一个变量，算出它取 \(1\sim m\) 时的贡献，求和，然后 \(c\) 个变量相乘，就是 \(d\) 序列的贡献。
这个过程显然可以用一个状压 dp 维护，\(f(i,S)\) 表示 \(i\) 个变量占据了 \(S\) 位置内的质因子即可。
现在发现要算 \(\le n\) 的，其实难点反而在外面：我们对于每个 \(i\le k\)，要去算：\(\sum_{x\le n}\dbinom{x}{i}m^x\) 这种东西。设 \(S(v)\) 是 \(i=v\) 时的和，则错位相减后从 \(S(v)\) 推到 \(S(v+1)\) 是容易的。
8. ARC182D Increment Decrement Again
Ad-hoc 不阴我吃。
我的思考：样例没有给无解猜测必定有解。发现 \(a_1\) 总可以自由变成一个 \(a_2\) 以外的位置，那么 \(a_1\) 就可以删去了（如果他和 \(a_2\) 冲突，就可以换到一个不冲突的位置）。但发现 \(m=2\) 的时候是有无解的情况的。思考一下发现也有道理，因为 \(m=2\) 的时候并没有给 \(a_1\) 留出这个空位。
当 \(m=2\) 时若序列不相等显然无解。现在考虑 \(m\ge 3\)。
把这个取模操作干掉，限制变成 \(a_i\neq a_{i+1}\) 且 \(|a_i-a_{i+1}|\lt m\)，这我哪想得到呀。
设最后序列变成了 \(A\)，显然 \(m\mid (A_i-b_i)\)。
设 \(A_1=b_1+km\)，可以发现整个 \(A\) 会被唯一推定：其中 \(A_i\) 可以写成 \(b_i+(k+c_i)m\) 的形式。
发现变量仅有 \(km\)，是一个类似最小化绝对值之和的状物。如果取值是连续的显然找中位数，不连续但间隔相等也差不多做就行了。我的做法比较无脑是直接三分（因为凸壳每隔一段定距离打一个点得到的还是凸壳）。
9. NWWRC2015 Graph
这个题很精妙，感觉状态好才做了出来。
因为是字典序最小的拓扑序最大，所以说考虑贪心。先考虑第一个点：我们提出所有无入度点。如果 \(k=0\)，显然 \(p_1\) 是最小的那个，如果 \(k=1\)，我们可以给最小的那个无入度点加一条入边，这样的话次小的无入度点就会作为 \(p_1\)（除非仅有一个无入度点），\(k\ge 2\) 以此类推。这样我们可以确定 \(p_1\)。但我们发现后续的决策会很困难，我们不知道那些比较小的无入度点，怎么去给它们加边。
但我们发现：我们不急着给这些点连边，当它确定位于 \(p_i\) 的时候，如果它需要连一条入边，就连 \(p_{i-1}\rightarrow p_{i}\) 即可！
准确地描述一下过程：维护两个当前无入度点的集合 \(S,T\)。其中 \(S\) 内的点表示有一条入边给他连，但是没有确定。\(T\) 内的点表示这些点当前没有入边。如果 \(k=0\)，我们会优先选择 \(T\) 中的最小值作为 \(p_i\)，如果 \(T\) 为空就去选择 \(S\) 的最大值。当 \(k\gt 0\) 时，我们就可以取出 \(T\) 的最小值，给他加一条入边，然后放进 \(S\)。注意到如果 \(T\) 的最大值比 \(S\) 的最大值大，那么把他放进 \(S\) 是无意义的，会浪费一步操作。
当我们确定了 \(p_i\) 的人选时，连接 \(p_{i-1}\rightarrow p_{i}\)（如果 \(p_i\) 是在 \(T\) 中的）即可，然后一些新的点会加进 \(T\)。
10. CF536D Tavas in Kansas
直接令 \(f(x,y,0/1)\) 是选中了距离 \(s\) 不超过 \(x\) 的，距离 \(t\) 不超过 \(y\) 的点。当前轮到先手/后手操作，最后的结果。这个状态数目可以离散化到 \(O(n^2)\)。
朴素地转移，就枚举当前这一边的参数，这样是 \(O(n)\) 的转移。注意到我们可以一点一点扩大，所以就优化到了 \(O(1)\) 转移。
11. AT_ddcc2017_final_d なめらかな木
这个题很神秘。原题是 \(n\le 50\)，但我真的听不懂 gzy 加强到 \(10^5\) 的做法。。
先去做 \(n\) 小的部分分：发现我们需要状压哪些节点被填过数，然后只关心上两个节点分别是谁。这样是 \(O(2^nn^3)\) 的一个做法。
有一个很显然的事情：每个点的度数需要不超过 \(4\)，然后观察假设我们知道上两个点是 \((x,y)\)，它们最多把剩余部分划分为 \(7\) 个连通块。而且这些连通块，每一个要么全部填了要么全部不填，所以可能的 mask 不超过 \(2^7\) 种。这样就得到一个 \(n^32^7\) 的做法，而且常数很小，甚至能过 \(n\le 200\)。
12. CF1876E Ball-Stackable
这个题好牛逼啊。
先考虑一个部分分：所有边都未定向。发现有且仅有一种定向方式能达到 \(n-1\) 的最大值：以某个点为根形成一颗外向树。
再考虑另一个部分分：所有边都定向。随便以一个点为根，把外向的边看成 \(1\)，内向的边看成 \(-1\)。如果 \(rt\) 到任何一个点的路径带权长度都 \(\ge 0\)（也就是说到任何一个点的路径都是合法栈路径），则容易发现内向边的颜色是必须和某条外向边相同的。因此所有外向边都赋一个颜色就是上界。但可能出现某条路径的带权长度是 \(\lt 0\) 的：发现这种情况可以把 \(rt\) 调整到这个路径的另一端点。
因此，我们如果选择一个点，使得以它为根的时候内向边最少。它一定满足：\(rt\) 到任何一个点的路径都是合法栈路径。
同上地，给每一条外向边都去赋一个颜色即可，这依旧是颜色数的一个上界。很惊喜的消息是很容易验证这是一个合法解。。。
13. ARC114F Permutation Division
这个题十分地好啊！
一些基本的观察：最后的答案一定大于等于原排列，且 \(k\) 越大答案就会越大。如果我们确定了分段方式，只需要把每一段按照开头元素作为关键字，降序排列就能得到结果排列。
设 \(p\) 为初始排列，\(q\) 为结果排列。考虑最小化 \(q_1\)：贪心地我们肯定会尽可能选取比较小的元素作为段开头。但是 \(p_1\) 比较特殊，它无论如何都会作为一个段的开头。因此：
-
当 \(p_1\le k\) 时，我们可以做到让 \(1\sim k\) 作为所属段的开头，这样分段方式确定，结果排列确定。
-
当 \(p_1\gt k\) 时，无论怎么分段 \(q_1\) 都不小于 \(p_1\)。需要更进一步的讨论。
思考弱一点的问题，如何判断 \(q\) 能否等于 \(p\)？发现这等价于我们分出的 \(k\) 段段首元素就是递降的，进一步地等价于存在一个以 \(p_1\) 开头的长度 \(=k\) 的下降子序列。可以判掉。
因为最后的答案一定大于等于原排列，考虑最大化 \(p\) 和 \(q\) 的 LCP 长度：我们假设一直到前 \(r\lt k\) 段是和 \(p\) 完全相同的。则相当于选出一个 \(p_1\) 开头的长度 \(=r\) 的下降子序列。假设这个下降子序列的结尾位于 \(p_x\)：考虑剩下的 \(k-r\) 个开头都需要小于 \(p_x\)，但我们不关心它们之间的相对顺序。由于要最大化 LCP，一定是选择最靠后的 \(k-r\) 个元素作为段头。这样，对于每个 \(p_x\)，都可以唯一得到一个最优的 \(q\)。如何比较优劣？显然 LCP 不同的话选 LCP 长的就行。如果 LCP 相同，发现在一个方案里，剩余的段开头选取的一定是 LCP 后面，\(\le y\) 的所有 \(p\)。因此我们比较 \(\max y\) 即可。并且容易发现，若 LCP 长度和 \(\max y\) 均相等，两个 \(q\) 就是完全一致的。
按照从小到大的顺序加入 \(p_x\)，使用 BIT 上二分的技术就可以做到 \(O(n\log n)\)。
14. FARIO 2023 T1 Bifrost
注意到一个路径如果发生了一次折返，则一定形如 \(SS'S\) 的一个字串出现了。
我们声称不断重复这样一个过程：对一个串随便地去找 \(SS'S\) 的结果并且删去 \(S'S\)，比较两个串最后是否相同即可。
这样就有一个 \(O(n^3)\) 的做法：至多删除 \(n\) 次，每次可以 \(O(n^2)\) 查找答案。
考虑我们相当于枚举一个 \([i,i+3len)\) 的区间是否是 \(SS'S\)。倒序枚举 \(i\)。如果枚举到 \([i,i+3len)\) 合法，那就把下一次检查的 \(i\) 跳回到 \(i+len-1\)。否则就还是把 \(i\) 跳到 \(i-1\)。可以证明左端点的移动量在整个过程中还是 \(O(n)\) 的（因为 \(\sum len=O(n)\)）所以复杂度 \(O(n^2)\)。
15. WYR-Leveling Ground
这题也很厉害啊！
先考虑差分数组 \(d\)。则我们操作相当于选两个不同位置，然后一个加一个减，量是 \(A/B\)。
则有一些显然的工作：首先 \(\sum d\) 应该为 \(0\)。其次每一个 \(d\) 都应该是 \(\gcd(A,B)\) 的倍数。不妨都全部除以 \(d\)，变成 \(\gcd(A,B)=1\) 的情况。
但是因为我们一次操作选定两个元素，并且还不是独立的，一个加一个减就非常难受。考虑弱化问题：对每个 \(d\) 求出 \(|x|+|y|\) 最小的一组 \(Ax+By=d\)，这个求法是容易的：可以证明最优解里必定有一个元素取到最小非负解/最大非正解，可以 \(O(\log V)\) 求出。
假设此时 \(\sum (|x|+|y|)\) 为 \(S\)，那么答案的一个下界肯定就是 \(\frac{|S|}{2}\)。考虑为什么我们不一定能取到这个？因为我们的操作要求 \(\sum x\) 和 \(\sum y\) 之和都应该为 \(0\)（这样就对应了一次操作动两个位置且一加一减）。容易看出 \(\sum x\) 为 \(0\) 的时候 \(\sum y\) 也一定为 \(0\)，所以仅考虑满足前者。
不妨考虑 \(S_x\gt 0\) 的情况。这个方程的解的调整形式是 \(x\) 这里加减 \(B\)，\(y\) 对应的加减 \(A\)。所以 \(S_x\) 的变化一定是 \(B\) 的整数倍。也就是我们要调成 \(cnt=\frac{|S_x|}{B}\) 次。调整就是选一个位置，让 \(x\) 减去 \(B\)，\(y\) 加上 \(A\)。对于一个位置，容易观察得到：其调整一次的代价发生改变，只有 \(O(1)\) 次（有人变号了），且这个代价始终在增大。
因此用堆维护每个位置的调整代价来贪心调整即可。\(S_x\lt 0\) 同理。时间复杂度 \(O(n\log V)\)。
16. 北京市赛2023 三染色
这个题太牛逼了，到底如何才能想到这样的题啊？
我认为比较合理的切入点是给每个位置重新赋一个权 \(b\)，使得相邻位置的 \(b\) 之差不超过 \(1\)，且模 \(3\) 意义下和 \(a_{i,j}\) 相等。考虑证明总是能做到这一点？那我们就一列一列填就行了。每一列也从上往下填，优先满足左边那个格子的限制。那么当我们填 \((i,j)\) 的时候出现矛盾了：讨论一下 \((i-1,j-1)\) 和 \((i,j-1)\) 相等 or 差为 \(1\) 的情况。然后可以发现一定是出现了这样一个 \(2\times 2\) 的矩形：\(0/1/2\) 都出现了，并且有一行/一列的两个数相同。
考察这样一个子矩形本身就一定会无限循环下去。而没有这样的子矩形我们就一定能标号，通过这个标号就能证明一定能在有限轮里进行下去：一个格子如果四周有一个标号是它自身减一的，它这一轮的标号就也会减一。
这样这个题就被转化干净了！！第一问很简单，我们直接搞一个轮廓线 dp 即可，是 \(3^{n+1}\times nm\) 的状态数。
第二问还得想想：相当于是 \((1,1)\) 到曼哈顿距离最近的一个最小标号位置的距离。要记录的东西似乎有点多呀？
好像也不是那么简单：第一个想法，我们轮廓线的过程中，记录当前遇见过的最小标号，以及当前这一列第一个位置的标号，还有遇见过的最小标号的最近距离。这都多出来三个 \(m\) 了哥们。
第一个优化：我们记录最近的距离是因为我们后面可能碰到一个更近的，但是这个矩阵的行数是特别少的：你假设有一个 \((i,j)\) 的最小标号，那你到了 \(j+n\) 列以后的任何格子，曼哈顿距离都会比 \((i,j)\) 大，这个时候就不关心那个距离到底是多少了。更严谨一点的：当我们扫到第 \(i\) 列的时候，只需要记录一个 \(O(n)\) 的变量 \(x\)，表示说如果这一列出了一个行数 \(\le x\) 的最小标号格子我们才能更新，否则不更新。这样多出来的就是 \(O(nm^2)\)，好像还是不太给力啊。
欸，我们不妨记录一下最小标号和这一列第一个格子的标号的差。那如果已经比当前最小的标号小了总不能给负数吧？我们可以变通一下：在 \((1,1)\) 处直接钦定一下全局的最小标号，然后直接把这个值作为此时的差就行。这样就只多了 \(nm\)，甚至能跑 \(n=6\)。
标签：标号,2024.8,sum,一个,序列,考虑,我们 From： https://www.cnblogs.com/Cry-For-theMoon/p/18397336