目录
F 优秀字符串
签到，速杀。
J 排列与合数
其实也是签到。
全奇数情况的答案样例给了，含偶数的情况把偶数放最后即可。
因为细节挂了两发罚时。
H 随机栈
把所有 \(0 \leq a_i \leq n\) 排序就是唯一的合法取出序列 \(b\)。
然后我们模拟：
-
当 \(0 \leq a_i \leq n\) 时，
cnt[a[i]]++。 -
当 \(a_i=-1\) 时，考虑 \(b\) 中待取那个数的
cnt。为 \(0\) 则答案为 \(0\)；否则答案乘上 \(\frac{cnt}{已取数的个数}\)。
时间复杂度 \(\mathcal{O}(n \log n)\)，桶排并预处理逆元可以 \(\mathcal{O}(n)\)。
M 有效算法
二分合法的 \(k\) 即可，时间复杂度 \(\mathcal{O}(n \log n)\)。
A Once In My Life
构造 \(123456789d \cdots\)，后面预留 digit(n) 位使这个数 \(\equiv 0 \pmod n\) 即可，时间复杂度 \(\mathcal{O}(T \log n)\)。
B 扫雷 1
签到题，对价格取个后缀 \(\min\) 即可，萌萌队友读错题写了半天。
L Toxel 与 PCPC II
诈骗题，因为 \(x^4\) 增长很快，所以每轮清扫的 bug 数至多二十来个，暴力 DP 即可，时间复杂度 \(\mathcal{O}(n\sqrt[4]{n})\)。
K 树上问题
很板的换根 DP，每次换根不合法边数至多改变 \(1\)，不合法边数为 \(0\) 的点就是答案，时间复杂度 \(\mathcal{O}(n)\)。
D 距离之比
容易注意到，两点在坐标系上确定的矩形越正，两点间贡献就越大。
换句话说，两点在坐标系上连线斜率越靠近 \(1/-1\)，贡献越大。
考虑把坐标轴顺/逆时针旋转 \(45\) 度，则横坐标相邻的点对才会产生贡献，两种贡献取 max 就是答案。
简单解几知识：旋转后坐标变为 \(\frac{1}{\sqrt{2}}(x \pm y)\)，故直接对 \(x \pm y\) 排序即可，时间复杂度为 \(\mathcal{O}(\log n)\)。
C 中二病也要打比赛
首先，左右端点数相同的子段最后一定会被推平成同一个数，我们把它看作“一个块”，相互接壤的块可以合并为一个新的块。
记录每个数最后出现的位置，容易实现上面的操作。
考虑每个块，如果把这个块推平成块内有的数，答案是块内不同数个数 \(-1\)，否则就是不同数个数。
为了代价最小，每个块只能推成块内有的数。
反正块连续，不妨把每个块看成一个数，问题就变成：序列每个位置可以填若干种数，求序列最长上升子序列。（一个数只可能出现在一个块内）
然后就是众所周知的导弹拦截了，时间复杂度 \(\mathcal{O}(n \log n)\)。
G 扫雷 2
唯一真史。
我最开始的想法是最外边一圈很复杂，考虑设法把它围起来。
又注意到 \(T\) 字形能非常完美地避免 \(2\) 的出现，于是得到了 \(m \leq 4n-4\) 的构造方案雏形：
标签：Zhengzhou,log,复杂度,CCPC,2024,leq,mathcal From： https://www.cnblogs.com/CrH2/p/18379293