[SNCPC2019] Unrooted Trie
发现不满足题意的情况就是一个节点到多个子节点的边的字母相同，那么合法当且仅当每个节点到子节点的字母互不相同。那么可以统计每个节点连接的字母数量，并运用类似换根 dp 的思路，快速更新这个数量并实时维护符合条件的点的数量即可。时间复杂度 \(O(26n)\)。
Submission
[GDCPC 2023] Base Station Construction
考虑 dp。设 \(f_i\) 表示到位置 \(i\) 所需的最小花费，且第 \(i\) 个位置必选，现在要找上一个决策点 \(j\)，这个点应该要在此前所有区间的左端点的后面，才能保证这些区间能被覆盖（即确保至少一个在之前每个区间内），则 \(j\) 应满足 \(\max_{r_k<i}l_k \le j < i\)，转移方程 \(f_i=\min_{{\max_{r_k<i}l_k} \le j < i}f_j+a_i\)。左边部分将区间按右端点排序后双指针即可，转移使用单调队列即可。
实现时可以令 \(a_{n+1}=0\)，这样 \(f_{n+1}\) 可以直接作为答案输出。时间复杂度 \(O(\sum(n+m\log m))\)。
Submission
[HBCPC2024] Points on the Number Axis A
答案即为 \(\dfrac{\sum_{i=1}^n x_i}{n}\)。以下有两种证明。
证一
由对称性可知每个点被选的概率是一样的，即每个点对答案贡献的权重 \(p_i\) 是一样的。又由于 \(\sum_{i=1}^n p_i=1\)，故 \(p_i=\frac{1}{n}\)，那么答案即为 \(x\) 的平均数。
证二
数学归纳法。设 \(f(n,x)\) 表示长度为 \(n\) 的序列 \(x\) 对应的答案。
- \(n=1\)，则 \(f(n,x)=\dfrac{\sum_{i=1}^n x_i}{n}\) 显然成立。
- 假设 \(n=k,k\ge 1\) 时结论成立，则 \(n=k+1\) 时，有 \(f(k+1,x)=\dfrac{1}{k+1}(\sum_{i=1}^{k+1} \dfrac{f(k,x-x_i)+x_i}{2})=\dfrac{1}{k+1}(\sum_{i=1}^{k+1} \dfrac{\frac{(\sum_{j=1}^{k+1}x_j) -x_i}{k}+x_i}{2})=\dfrac{1}{k+1}(\sum_{i=1}^{k+1} \dfrac{(\sum_{j=1}^{k+1}x_j)+(k-1)x_i}{2k})=\dfrac{1}{k+1}(\sum_{i=1}^{k+1} \dfrac{(k+1+k-1)x_i}{2k})=\dfrac{\sum_{i=1}^{k+1} x_i}{k+1}\) 则 \(n=k+1\) 时也成立。
- 综上，结论成立。
[SNCPC2019] To the Park
考虑从大到小枚举不超过 \(\lfloor \frac{n}{2} \rfloor\) 的质数 \(p\)（因为质数越大越难匹配），并统计其有多少个倍数尚未匹配（包括自身）。如果个数为奇数，那么把 \(2\times p\) 用来留给偶数匹配。如果个数为偶数，直接两两配对即可。这样能够保证含较大质数因子的数也尽可能匹配，实现答案最大化。时间复杂度 \(O(\sum(n\log \log n ))\)（与埃氏筛相同）。
Submission
[SNCPC2019] Escape Plan
正难则反。考虑以 \(k\) 个逃生点为起点，\(1\) 为终点跑最短路，那么就很容易可以得到每个点的前若干小的最短路，最坏情况下显然是将这些堵住，那么取到第一个没被堵住的最短路时再向其它点扩展即可。每个点依旧只会向外扩展一次，因此时间复杂度依旧是 \(O(m\log m)\)。
Submission
[SEERC 2019] Cycle String?
首先如果每个字母出现次数最多不超过 \(n\) 次显然可以让相同的字符放在一起。这样做每个子串一定互不相同（字母完全相同的最多出现一次），因此一定有解。
否则，设出现次数最多的字母为 \(ch\)，则可以先放 \(n\) 个 \(ch\)，然后放一个其它字母，再放剩下的 \(ch\)，最后把剩下的字母按上面的规则放即可。这样做能保证 \(ch\) 不会出现超过 \(n\) 的连续段。无解的情况：
- 只有 \(2\) 种字母，且另一种字母出现不超过 \(2\) 次，则最多构成 \(aa\cdots aba\cdots ab\) 的形式，存在两个 \(aba\cdots a\)，无解。
- 不止 \(2\) 种字母，但其它字母出现次数总和少于 \(2\) 次，则无法将 \(ch\) 分割成 \(2\) 段，无解。
Submission
[GDCPC 2023] Traveling in Cells
显然可达的位置一定是一段连续的区间，那么对于操作 \(2\) 直接使用树状数组维护单点加区间和即可。对于颜色的维护，可以沿用可持久化线段树的思路，在其发生改变（或初始时）建立从该颜色的根到叶子的路径（如果已经有了就直接在上面修改），这样就省去了对每一种颜色建整棵树的大量空间。分别二分左右边界，然后查询区间内每种询问的颜色的出现次数之和（线段树区间和）是否等于区间长度即可。时间复杂度 \(O(n\log^2 n)\)，空间复杂度 \(O((n+q)\log n)\)。
Submission
[NERC 2018] Easy Chess
由于题目保证有解并且只需要找到一组解，因此可以直接爆搜，记录经过的点并判断是否到达终点即可。枚举时先枚举上下移动，再枚举左右移动，可以尽快到达终点，优化复杂度。
Submission
[CERC2019] ABB
转化题意后发现就是要找最长的回文后缀。那么可以直接求出两个方向的哈希，然后枚举对称点即可。亦可以使用 KMP，将 \(s\) 反转为 \(s'\)，构造新字符串 \(s'+一个特殊字符+s\)，根据回文串的特性可知只需找新串的 border 即可。两种时间复杂度均为 \(O(n)\)。
Submission