笔记 2023.12.12：杂题选讲
ARC132E
首先发现最终状态形如：中间两个洞夹着的没人动过，它的左边全是 <，右边全是 >，考律左边全是 < 的方案数。然后若给每个洞被选时间标号，则定向方案数是 \(2^{n-\text{后缀最大值}}\)。考虑从后往前 dp，将这个系数直接记在 dp 值里，然后就能算了，考虑每次插进去一个数插在哪里。\(f_i=f_{i-1}\times 2(i-1)+f_{i-1}\)。
CF1610H
无解显见。将链分类为直链（有祖先关系）和弯链，显见选一个根节点可以解决所有弯链。如果树本身是一条链，那么是经典贪心问题。类似的，对于一个合法方案，我们可以尝试将选的点向上跳，在不影响自己子树的情况下不劣。考虑 dp，\(f_u\) 表示考虑所有在子树内的关键点对应了链，关键点定义为链深度较浅的向下跳。\(f_u\) 至少是所有儿子的和，考虑关键点，如果有两个子树有 dp 值，那么全部合法，否则向有 dp 值的地方尝试跳，直到跳到某条链链底，事实上因为讨论过多，不妨认为直接就是 \(f_u=\max_{(x, y)\text{是直链},fa_u=x}(f_y+1)\)。
对于最终答案，为了判断根节点选不选，不妨将 \(f_1\) 与 \(\max_{(x, y)\text{是弯链}}\{f_x+f_y+1\}\) 取最大值，这是考虑 \((x, y)\) 上面到底有没有选到点，如果最终方案上面取到一个点，那么这个 \(\max\) 取不到。
*CF704C
将限制的两个变量连边，因为度不超过二，所以就强行 dp。
%CF839E
CF1253F
以充电中心为端点，建一张完全图，边权是两个充电中心的原图最短路，要求这张完全图上的路径最大值最小。一眼最小瓶颈生成树，重构树一下，问题变成求最小生成树。
其实是假的。
考虑树。考虑按照树上路径走，每走一步都试试充电。\(dis_x\)，表示离 \(x\) 最近的充电站到 \(x\) 的距离，显然可以魔改 dijkstra。然后发现每一步能充电就必然想要充电，我们可以写一个限制形如：
表示我走完 \(x\to y\) 后必须想要充电。如果这一次没充上，下一步其实放宽限制，甚至可能寄了，所以声称路径上所有边满足这个限制是必要条件。
那么对于图就求 Kruskal 重构树。
CF1446D2
注意到全局众数 \(a\) 一定出现，否则扩张区间。枚举另一个众数是 \(x\)，不妨钦定 \(x, a\) 就是区间众数（否则扩张），那么我们只需要要一个区间使得 \(a, x\) 的出现次数相等，一眼将 \(a\) 设为 \(1\)，\(x\) 设为 \(-1\)，找和为 \(0\) 的连续段。进一步的发现有一些 \(a\) 是没有必要每次都拉出来的，例如 aaaaaaaaaaaaaaaaaaxxxaaxaaaaaaaaaaaa 就只需要中间 \(x\) 左右两边的 \(a\)。进一步的我们就是只关心那些 \(x\) 向左向右一旦他只剩下一堆 \(a\) 就不要继续向下，这样复杂度就均摊掉了。
*CF1718D
笛卡尔树同构。根据已知信息推断每个未知数的合法区间，满足合法区间后，如果有不合法的直接 swap 一下。
然后做点和区间的匹配，正着贪心失配的区间和反着贪心失配的区间（注意是区间匹配点）的并，声称是合法的 \(d\) 的范围。
*ARC141C
逮捕
CF1603E
完美，等价于排序后每个前缀合法。
枚举最小值，记录填了几个数，目前到谁，总和，然后转移枚举填几个数字进去，是 \(O(n^6)\)。
当 \(a_n=n\) 时，因为 \(a_1n\geq \sum a_i\implies 0\geq \sum (a_i-a_1)\geq 0\)，由此整个序列都是 \(n\)。
当 \(a_n=n+1\) 时，因为 \(a_1(n+1)\geq \sum a_i\implies a_1\geq \sum (a_i-a_1)\)，记录右边那个东西以判断，这样记下的总和是 \(O(n)\) 的，而且不仅是这个序列，每个前缀都适用。
现在 \(O(n^5)\)。
观察到枚举 \(a_1\) 之后每个数字填进去的个数，由于总和限制，是调和级数。
\(O(n^4\log n)\)。
\(a_1a_k\geq \sum_{i\leq k}a_i\implies a_k\geq \sum_{i\leq k}a_i/a_1\implies a_k\geq k\)。
结论是 \(a_1+\sqrt n\leq n\)，因为考虑就是拿 \(y=a_1\) 和 \(y=x\) 切，切到后面那一段，因为刚刚说了 \(a_i\geq i\)，所以后面那一段，考虑 \(\sum(a_i-a_1)=O(n)\)，后面一段的长度为 \(O(\sqrt n)\)。
\(O(n^3\sqrt n\log n)\)。
*CF1208H
不急
*ARC154E
*ARC135D
整个矩阵经过显然的手法可以将 \(A[1...n-1][1...m-1]\) 全部置零，求出来大概是什么交替和需要是常量，然后操作不影响交替和。就我是说每一行 \(A[i][1]-A[i][2]+A[i][3]-A[i][4]\cdots\) 是常数，每一列也如此。然后乘 \((-1)^{i+j}\) 变成和不变。
然后考虑怎么构造一个新的矩阵使得它的和限制不变，这样就一定能变换过去，由刚才的置零。
逮捕