口胡集锦。
往年省选泛做
愿意写代码的会单独分裂出文章。
2019
ZJOI
Done.
HNOI
D1T1
Done.
D1T2
Done.
D1T3
Done.
D2T1
高妙图论题。
明天就搬到提高组模拟里。
考虑一个暴力：从长度为 \(1/2\) 的回文串开始跑 DP，时间复杂度 \(O(m^2)\)。
总体基于二分图的优美结构，因为在二分图上任意走动并不改变路径长度的奇偶性。
对于同色连通块，如果其为二分图，则随便保留一棵生成树即可；否则保留一棵生成树后任意连一个自环以改变奇偶性。
对于连接不同色的边，一定为若干二分图的组合，类似地保留一棵生成树即可。
这样边数就降到了 \(O(n)\)，时间复杂度 \(O(n^2)\)。
D2T2
Done.
D2T3
考虑最优解一定是划分成若干个区间，将 \(B\) 的区间内所有数改为 \(A\) 区间内的平均值，在单调的前提下区间长度尽量小。
证明来了。
这是典型的保序回归问题。
引理 1
如果强制要求 \(B\) 的所有数相同，那么这个数一定是 \(A\) 的平均数。
证明
问题即最小化 \(f(x) = \sum\limits_{i=1}^n (A_i - x)^2\)。直接对其求导得 \[ f'(x) = -2 \sum\limits_{i=1}^n (A_i - x) = -2 \left[\sum\limits_{i=1}^n A_i - nx\right] \]
显然当 \(x = \frac1n\sum\limits_{i=1}^n A_i\) 时 \(f'(x)\) 取 \(0\)，且容易验证其为最小值。
引理 2
对于 \(1 \le i < n\)，如果 \(A_i > A_{i+1}\)，那么最优解中一定满足 \(B_i = B_{i+1}\)。
证明
若最优解中 \(B_i < B_{i+1}\)，令 \(\epsilon > 0\) 为一个实数，满足令 \(B'_i = B_i + \epsilon,B'_{i+1} = B_{i+1} - \epsilon\) 后不影响大小关系。那么有 \[ (B'_i - A_i)^2 + (B'_{i+1} - A_{i+1})^2 - (B_i - A_i)^2 + (B_{i+1} - A_{i+1})^2 = -2\epsilon (A_i - A_{i+1}) + 2\epsilon^2 < 0 \]
因此将 \(B_i,B_{i+1}\) 调整到 \(B_i = B_{i+1}\) 时更优。
做法
没有修改时用单调队列维护即可。带修改的话，考虑在数据结构上二分出修改点的前后分界线即可。
时间复杂度 \(O(n \log^2 n)\)。
SNOI
D1T1
简单串题。
明天就搬到普及组模拟里。
考虑如何快速比较串的大小。
对于 \(s_i,s_j\ (i < j)\)，实际上只需要考虑 \(i,i+1\) 的 LCP 即可。
这显然相当平凡。直接求后缀有多少个位置满足其与后一个字符相等即可。
时间复杂度 \(O(n \log n)\)。
D1T2
首先容易把 \(T\) 的范围缩减到 \(10^{12}\) 级别。
根据经典结论，对于 \(E = \{(i,(i + P) \bmod Q) \mid 0 \le i < Q\}\) 的图，可以划分为 \(\gcd(P,Q)\) 个环，大小为 \(\frac Q{\gcd(P,Q)}\)。
然后提前预处理一下每个环上的贡献，再枚举 \(a_i\) 计算对应贡献。
D1T3
巧妙的优化建图题。
暴力 \(O(n^2)\) 的建图费用流就不提了。
优化建图自然考虑分治一类的结构，但是绝对值并不好处理。
考虑经典套路，将权值排序之后利用相邻排名的权值之间的差累计出绝对值。
这样就把边数降到了 \(O(n \log n)\) 级别。
这题要写代码。
（支线任务：一些奇怪的费用流算法。）
D2T1
憨批麻将题。
随便矩乘一下，略。
D2T2
好像是 NB 阴间搜索，爬了。
考虑在空格移动的过程中，容易将这个空格的状态改为目标状态。但是不在空格移动路径上的木块就并没有归位。
因此搜索时主动去寻找周围没有归位的木块即可。
D2T3
显然点数越多越好，于是考虑枚举连通块直径的中点统计答案。
感觉上是个阴间长链剖分 DP，爬了。
（支线任务：长链剖分。）
十二省联考
D1T1
Done.
D1T2
阴间优化建图。
太平凡了就不口胡了。
D1T3
懂的都懂。
D2T1
分别讨论阵营和派系即可，对有限制的学校再另外 DP。
D2T2
Done.
D2T3
……
GXOI/GZOI
D1T1
拆位之后单调栈计算全 \(0/1\) 矩阵个数。
D1T2
Done.
D1T3
由于特技总是在固定的位置发生并被观测到，所以这部分的代价是固定的。并且特技发生的次数也是固定的……所以其实重点并不是最优化问题。
事实上只有两种可以达到最值的策略：交换次数最多和最少。具体哪个是最大值哪个是最小值取决于 \(a,b\) 的大小关系。
交换次数最多只需要全部交换即可，因为交点实际上就是逆序对。
交换次数最少则考虑将初始到最终状态的置换 \(p\) 循环分解，交换次数就是 \(n - c(p)\)，其中 \(c(p)\) 为 \(p\) 的循环个数。
然后计算一下哪些点会被嘉宾观测到。随便算个交点然后转一下坐标，扫描线一下就好了。
D2T1
简单矩乘题。
明天就搬到普及组模拟里。
如果不存在 \(1 \times 1\) 的块，那么显然就是斐波那契数列。
如果存在，考虑若第 \(i\) 列放了一个，那么在 \(1\dots i-2\) 列都可以放，并且这两块之间的列的方案是唯一确定的。
因此有 DP 式 \[
f_i = f_{i-1} + f_{i-2} + 2\sum\limits_{j=0}^{i-3} F_j
\]
其中 \(F_j\) 是斐波那契数列。
矩阵快速幂即可。
D2T2
首先是 naive 的标算。
枚举二进制位将关键点分组，建图跑出点集到点集的最短路即可。
然后是少一个 \(\log\) 的做法。
建图跑出每个点与哪个关键点最近，正反都要跑。然后枚举边计算贡献即可。
可以证明能取到最优解。
懒得胡了（
D2T3
Done.
经典套路题。
SDOI
D1T1
Done.
D1T2
考虑一个垃圾 \(O(nc^2)\) DP。
设 \(f(i,x,y)\) 表示前 \(i\) 列，第 \(i\) 列的两个颜色分别为 \(x,y\) 的方案数。
是不是一点用都没有。
然后考虑优化掉一个 \(c\)。
当第 \(i\) 列有被钦定的颜色时，只需要记另一个颜色即可。
对于没有被钦定的颜色的块，考虑一起转移。
预处理一个转移的系数即可。发现这部分状态数很少，只有 \(5\) 种本质不同的状态。
然后剩下的 \(4\%\)，观察一下我们的 DP 在干什么。
你会发现这和你在 D1T1 里做的事一致，贺过来改几下就行了。
不过没脑子选手上线段树也是很资瓷的。
D1T3
对每个前缀维护 MST 上最左端和最右端的点的虚树，边权为原树上路径最大值。
合并时只需要考虑这些点和新的一列点的 MST。
xjb 乱搞，但我实在写不出来（
复杂度 \(O(n(m+q) \log n)\)。
D2T1
神仙构造！
明天就搬到提高组模拟里。
第 \(i\) 次操作时从图中选择一个度数最小的点 \(a_i\)，将其及相邻的点删去，设这一次操作删掉了共 \(b_i\) 个点。
令 \(t = \arg \max b_i\)，则选取第 \(t\) 次及以后删除的点为热闹的聚会，\(\{a_i\}\) 为尴尬的聚会。
那么有 \(p = b_t - 1\)。并且两个条件都是显然的。
D2T2
发现是阶梯博弈。xjb 拆个位 \(O(nm \log n)\) DP 一下。
不过可以优化到 \(O(m^2 \log n)\) 乃至 \(O(m \log m \log n)\)，咕了（
D2T3
考虑 \(\mathbf{T.M.}\) 的另一种生成方式：从 \(0\) 开始，\(0 \to 01,1 \to 10\)。
考虑反向模拟这个过程，然后以此对答案 xjb 记搜即可（
JSOI
T1
2-SAT。
明天就搬到提高组模拟里。
令 \((i,t)_{0/1}\) 表示 \(i\) 在 \(t\) 时刻是死是活。
那么「难兄难弟」可以表示为 \((x,t)_0 \to (y,t+1)_0\) 和 \((y,t+1)_1 \to (x_t)_1\)，「死神来了」可以表示为 \((x,t)_1 \to (y,t+1)_0\) 和 \((y,t+1)_1 \to (x_t)_0\)。
同时还有任意 \((i,t)_0 \to (i,t+1)_0\) 和 \((i,t+1)_1 \to (i,t)_1\)。
不过这样点数过多，不太行。
对 \(t\) 离散化一下就完事了。
然后会发现它本身就是 DAG，不需要缩点。
然后对所有 \((i,T+1)_1\)，看它能否到达 \((i,T+1)_0\)，如果可以那么 \(i\) 就太悲催了……
否则看它能到达多少 \((j,T+1)_0\)。
然后上 bitset，可惜空间不允许。所以分个块 \(S\)。
时间复杂度 \(O\left(\frac{n(n+m)}{\omega}\right)\)，空间复杂度 \(O\left(\frac{nS}{\omega}\right)\)。
隔壁 w33z 有一个相关的题来着。
T2
Done.
T3
根据 Significant Suffixes 的相关理论，一个串 \(u\) 的 \(\{\arg \min\limits_{v \in {\rm suf}(u)} vw \mid w \in \Sigma^*\}\) 的大小是 \(O(\log n)\) 级别的。
然后暴力维护集合即可（我试图跳过证明看这部分的做法，然后翻了无数篇题解都没有详细说咋维护……），具体方式和以上结论的证明相关。
然后跑出 Z 函数就可以求答案了。
BJOI
D1T1
思博题。
明天就搬到提高组模拟里。
ln exp 一发，然后变成经典分数规划，xjb 二分一下，AC 自动机上 DP 一下，完事。
D1T2
首先乱搞出递推式，然后解出通项，令 \(f_n = A \alpha^n + B \beta^n\) 为 \(n\) 对应的填充方案数。
然后 \[
\begin{aligned}
\sum\limits_{n=l}^r \binom{f_n}k
&= \frac1{k!} \sum\limits_{n=l}^r f_n^{\underline k} \\
&= \frac1{k!} \sum\limits_{n=l}^r \sum\limits_{i=0}^k (-1)^{k-i} {k \brack i} f_n^i \\
&= \frac1{k!} \sum\limits_{n=l}^r \sum\limits_{i=0}^k (-1)^{k-i} {k \brack i} (A\alpha^n + B\beta^n)^i \\
&= \frac1{k!} \sum\limits_{n=l}^r \sum\limits_{i=0}^k (-1)^{k-i} {k \brack i} \sum\limits_{j=0}^i \binom ij (A\alpha^n)^j (B\beta^n)^{i-j} \\
&= \frac1{k!} \sum\limits_{i=0}^k (-1)^{k-i} {k \brack i} \sum\limits_{j=0}^i \binom ij A^j B^{i-j} \sum\limits_{n=l}^r (\alpha^j\beta^{i-j})^n
\end{aligned}
\]
枚举 \(i,j\)，扩域等比数列求个和即可。
D1T3
咕咕咕。
D2T1
Done.
D2T2
咕咕咕。
D2T3
咕咕咕。
膜你赛
2.27
T1
非完美口胡。
首先所有字符串的结尾一定只有两种字符，令它们分别为 \(a,b\)。若有第三种就显然无解。
\(a,b\) 为首尾的方案是对称的，先考虑 \(a\) 为首的情况。
假设有两个字符串 \(p_1 b s_1 a,p_2 a s_2 b\)，那么结果应当形如 \(a s_1 p_1 b,a p_2 s_2 b\)，但其中只有 \(s_1,s_2\) 的结果是确定的，\(p_1,p_2\) 内部的顺序并未确定。
于是同位置总有一部分是确定的，那么对着确定的部分逐一匹配，胡乱处理即可（
（并不会实现……）
T2
非完美口胡。
令给定的集合为 \(S\)，\(a_i\) 为 \(i\) 在 \(S\) 中出现的次数，\(s_i\) 为 \(a_i\) 的前缀和。
考虑 \(35\%\) 的暴力：排序后暴力选择 \(k\) 个位置钦定为 \(1\dots n\) 链上的点，其余部分贪心地赋予父亲。
下称这 \(k\) 个位置为选择点，其余在树中的点为未选择点。
容易知道对于一个树中的点，有解当且仅当 \(s_{i-1} \ge i-1\)。对于一个非选择点，有解当且仅当 \(s_{i-1} \ge i\)（因为在它之前必然有至少一个选择点）。
从而 \(s_{i-1}=i-1\) 的 \(i\) 必然是选择点，于是可判断无解。
其余部分类似地贪心地作为选择点，然后在剩下的位置中贪心选择前 \(k\) 大的边权即可。
T3
非完美口胡。
不妨设 \(n=2^{2k},x=2^k\)。
在测试数据中几乎是这样，不是的 xjb 调整一下就好了（雾
考虑系数模 \(2\) 的多项式 \(a,b,c,d\ (a \ne b,c \ne d)\)，若有 \(a^3-b^3=c^3-d^3\) 且 \(a-b=c-d\)，容易导出 \(ab = cd\)。
由于 \(a+b=c+d\) 且 \(ab=cd\)，可知 \(a,b,c,d\) 均为 \(x^2 - (a+b)x + ab\) 的解。但是由基本代数知识得其至多有两个解。
因此 \(\{a,b\}=\{c,d\}\)。
从而考虑对 \(1 \le i < 2^k\)，拼接 \(i,i^3\) 成为一个数。不过有一个问题就是 \(i^3\) 可能超过范围，但是根据一些近世代数知识，只需要在模一个 \(k\) 次的既约多项式意义下作乘法即可，因为这会形成一个域。
3.6
T1
长剖经典题 & 原题。
略。
T2
令 \(n' = 9n\)，则 \[ \begin{aligned} \sum\limits_{i\ge 2} \left\lfloor\frac{9n}{10^i-1}\right\rfloor &= \sum\limits_{i\ge 2} \left\lfloor\frac{n'}{10^i-1}\right\rfloor \\ &= \sum\limits_{i\ge 2} \left\lfloor\sum\limits_{j\ge 1}\frac{n'}{ 10^{ij} }\right\rfloor \\ &\approx \sum\limits_{i\ge 2} \sum\limits_{j\ge 1}\left\lfloor\frac{n'}{ 10^{ij} }\right\rfloor \\ \end{aligned} \]
这个东西算一下贡献发现是一个差卷积，FFT 或者龟速乘 + 大模数 NTT（答案大概是 \(9l^2\) 级别？）。
然后，然后，然后，出题人说随机情况下误差比较小，大胆毛估估一下保留前【数据删除】位就可以了……然后上一个 long double。
T3
如果把 \(p_i\) 和 \(\arg \min\limits_{1 \le j \le i} a_{p_i} \oplus b_{p_j}\) 连一条边，会得到一棵树。
然后会发现是个最小树形图。
字典序最小？逐位确定。