多校第五场

虽然是第五场了，可是这只是我做的第二场。前几场是 xlk 和 jzp 两人做的，他俩太可怕了。

Solutions

1001

没看题。

1002

暴力 BWT 逆变换后直接上后缀自动机就好了。

1003

代码题。

拆点，如果一个点是白色的，那么就在这个点的白点和它父亲的白点间连条边，否则就在这个点的黑点和他父亲的黑点间连条边。查询一个连通块的最大值相当于查询一个点所在子树内的最大值。用 LCT 维护一个点的祖先中，和他连续相同最近的点在哪里，剩下的就用路径来维护就好了。

1004

看了不会。

1005

贪心。每个点的权值为原来的权值加上所有和它相邻的边的权值的一半的和，从大往小贪心即可。

1006

记录个前缀和后直接做。

1007

水题。注意到位与位是独立的就好了。

1008

这个题原来是用来出 CF 的，但是被枪毙了。

考虑最优路径，要么是经过环要么不经过环。如果不经过环的话 \(f_{i, j, k}\) 表示从 \(i\) 到 \(j\) 走 \(k\) 步的最优解。枚举就好了。

经过环的话， \(g_{i, j, k}\) 表示从 \(i\) 到 \(j\) 走 \(2^k\) 最大路径平均值是多少。这个可以倍增处理出来。然后用 \(g_{i, j, T}\) ( \(t\) 是一个比较大的数) 来更新所有能从 \(j\) 到的 \(k\) 的 \(i\) 到 \(k\) 的答案。

1009

整数拆分。

wiki 中有个 五边形数定理 。

用五边形数定理暴力做就好了。

1010

这个题还是比较好玩的。

第一问，可以直接使用 CTSC 2008 D1T1 歌唱王国的结论，答案就是 \(\frac{m^n - 1}{m - 1}\) 对于 \(m - 1\) 需要特判。

第二问，令 \(f_i\) 表示现在已经得到了最后 \(i\) 个元素是不同的了，问期望还要加入有多少个元素才能使最后 \(n\) 个元素不同。

显然 \(f_n = 0\) 。另外还可以得到 \(f\) 的递推式： \[f_i = \frac{1}{m} \sum_{1 \leq j \leq i} f_j + \frac{m-i}{m} f_{i+1} + 1\]

考虑 \(f_i - f_{i+1}\) 。代入上面的式子后可以得到 \(\frac{m}{m-i}(f_{i - 1} - f_{i}) = f_i - f_{i+1}\) 。由于 \(f_0 - f_1 = 1\) 可以直接得到 \(f\) 的表达式。剩下的就是解一个一元一次方程了。

1011

HIT 给题解的人什么心态！！！

其实如果你曾经逛过这里的话会发现这就是道 原题 。

当然如果你逛过 xiaodao 博客的话会发现还有 更简单的做法 。

所以给题解的人是什么心态！！！

1012

其实这还是道原题，详情请见 论文 。

每次求一遍全局最小割，如果全局最小割不小于 \(k\) ，则这个点集就是 \(k\) 边连通的，否则把最小割里面的边全部删去，分成的两个连通块递归做下去即可。

当初做的时候加了一堆常数优化写的我好恶心。

ending

四处都是老二。

罚时太多没办法。

（其实我一直在等 Second Blood ?）