题面https://uoj.ac/problem/72

这个题的传统做法可见：https://vfleaking.blog.uoj.ac/blog/104

我发现了一个新的做法，并已经获得了满分：https://uoj.ac/submission/393501

可以发现这份代码的亮点是我在没有经过任何下意识的压代码长度的情况下，代码长度就是目前（2020年4月18日）所有AC提交中最短的。同时，虽然我没有使用batching加速，但是我的用时依然不算很差，通过调整参数，这份提交https://uoj.ac/submission/393500 的用时更短，但是这份代码的正确率我没法保证。

UPDATE: 加上batch之后变快了一些https://uoj.ac/submission/393507 （这是使用正确率我没法保证的参数的结果）

此外，我觉得我的做法相对传统做法也更容易理解。下面是我的做法：

考虑每个位置是否在$m$个有效信息中存在，那么你可以把这个存在性用一个长度为m的数组表示出来，这个数组可以压位表示成一个m位的二进制数。记第$i$个位置对应的这个二进制数为$s[i]$。

如果我们随机选一个集合，那么这个集合的$s$值的异或和有$2 ^ {-m}$的可能是零。如果一个集合的$s$的异或和是零，这意味着对于任何一个输入$x$，这个$x$的输出值和$x \oplus s$的输出值应该一样，当然，因为噪声所以有大约$2p(\le 0.02)$的概率这两个输出值不一样。

如果异或和不是零，那么一定有一个$x$使得它的输出值和$x \oplus s$的输出值不一样，如果不存在，那么容易发现$h$函数一定可以化简为少于$m$个输入上的函数。同样我们可以证明，随机一个$x$，它的输出值和$x \oplus s$的输出值不同的概率至少为$2 ^ {1 - m}$。在本题的限制下这个概率至少是$\frac{1}{8}$。

$0.02$和$\frac{1}{8}$的差异很大，如果我们随机多次的话，根据Chernoff Bound可以发现我们可以设一个$l$使得如果输出不同的$x$占的比例小于等于$l$，我们可以很确定这个$x$对应一个异或和为0的集合。我最快的代码是测试100次，并设$l = 2$（也就是我前面给出的“用时更短的代码”），但是这样错误率我没法保证，更加安全的参数是测试200次，并设$l = 4$（也就是我前面给出的第一份代码），这样错误率至多0.3%（这是通过Chernoff Bound和Union Bound给出的粗浅的上界）。测试1000次，并设$l = 20$，不batching也可以通过，这个的错误率至多在$10 ^ {-23}$级别（这比现代CPU出现软性错误的概率还低若干个数量级，也就是说你更有可能因为硬件原因出错而不是算法本身）。

这个$l$可以设得保守一些，因为接下来你将看到我们不能承受将错误的$x$判断成正确，但如果我们将正确的$x$误判成错误，我们只会增加一些计算量。

可以发现，任何有效信息的集合$u$一定满足$u \cdot x = 0$，其中$\cdot$表示按位AND之后1的个数的奇偶性，如果是奇数则值为1，否则为0。如果我们有了足够多的$x$，我们可以列出一个线性方程组，根据线性代数的知识可以发现这个线性方程组的秩一定是$n - m$，所以我们可以找到$m$个线性无关的解，这一定对应着$m$个有效信息。

知道有效信息之后计算$h$就很简单了，从线性代数的知识可以知道等概率随机一个$x$，那么$x$对应的$m$个有效信息一定也是等概率随机的，于是多次随机对每个结果取多数即可。

在 UR #19 比赛的过程中，我们 UOJ 管理员突然发现清华集训2012年的楼房重建与C题十分相似。虽然楼房重建这道题只支持修改和全局询问，且对时间复杂度的要求没有本题严格，但是本题的部分分完全可以套用该原题的做法。此外，对楼房重建这题感兴趣的人有可能在比赛前已经想出了满足UR的C题时间复杂度要求的做法。

我们在出题时也从未借鉴这道题，UR的C题做法与这题有一定相似性是意外，也是我们没在比赛前做足够多的调研的结果。我们为因为我们的失误而导致UR的C题的质量的下降，进而导致的整场UR的质量的下降感到抱歉，我以及部分其他UOJ管理员承担UR的C题撞题的责任。

题面

http://uoj.ac/problem/494

做法简要描述

首先，每个字符串后面加一个很大的字符（例如“U”）。

对于每个字符串$s$，找到最短的前缀$x$满足$x ^ \infty < s$，然后将字符串$s$分成$x ^ y + z$， 使得$x$不是$z$的前缀。

那么合并的顺序一定是按照$x^\infty$字典序升序然后相同按照$z+U$字典序降序，注意使用字母U的原因是U比四个字母都要大。

感性的理解就是这样，每次我们希望找个最小的$x$，然后加入尽量多的$x$，但是$x$加完之后我们希望能加的字符尽量小，所以我们把尾巴字典序最小的放后面。

知道顺序之后，倒着枚举前缀的长度贪心就行了。

比如对于输入：

CCACCACCACCATA
CCACCACCACCACCACCCA
CCACCACCACCCAAA
G

那么前三个每个的$x$都是“CCA”，$z$分别是“TA”，“CCCA”和“CCCAAA”，我们把第三个放后面，那么就有

“CCACCACCACCACCACCACCACCACCACCACCACCACCCAAA”

最后再加入“G”。

题面

http://uoj.ac/problem/492

结论

设最优解的倒数第$k$段的开始位置为$i$，那么对于所有的满足段和不递减条件的解，一定有下列条件之一：

1. 该解不存在$k$段。
2. 该解从右到左数第$k$段的开始位置至少为$i$。

这里我们假设最优解的倒数最后一段（也就是第一段）的开始位置是1，所以上述条件蕴含没有任何解的段数比最优解要多。

换句话说，如果你把所有解的断点从大到小写下来，然后剩下的位置补0，那么最优解对应的序列在所有位置都是最大值。

同时容易注意到满足这个结论中条件的解一定唯一，因此最优解释良定义的。

根据结论推出的线性做法

设$p_i$表示以$i$结尾的前缀，最后一段的位置的最大值，那么$p_i$一定是满足

$a[p_j] + \cdots + a[j - 1] \le a[j] + \cdots a[i]$的最大的$j$。

这个非常显然，因为$p_i$对应的是每个位置结尾的前缀最后一段的最小和，如果不存在$k > j$使得上述条件满足，那么$j$一定是最后一段位置的开头的位置的最大值。

通过记录前缀和，这个东西很好用单调队列线性维护。

最后答案就是按照$p$不断往前走。

容易证明到$p$满足不递减性，所以按照$p$不断走得到的解一定是满足结论中条件的解。

结论的证明

对于每个解，我们可以从后往前将每一段的和写出来，然后补无限个零，得到一个对应的序列。

从结论我们容易推出，满足结论中条件的解对应的序列的任何位置的前缀和一定是所有解对应位置的前缀和中最大的。

现在，我们抛弃原序列，只考虑这个和构成的序列，假设满足结论中条件的解对应的序列是$b_i$，我们现在找到另外一个解，它的序列是$c_i$，且满足：

$\forall k, \sum_{i \le k}{b_i} \le \sum_{i \le k}{c_i}$

我们需要证明：

$\sum{b_i^2} \le \sum{c_i^2}$。

我们注意到对于一个单调不递增的序列$x$，如果我们选出两个下标$i < j$，使得$x_i \ge x_j + 2$，并将$x_i$减一，$x_j$加一，那么操作之后$x$依然单调不递增，且么这个操作会使$x$的平方和减少。

证明的思路是，证明可以通过一些合法的移动将$c$变为$b$，且任意时刻$c$的所有位置前缀和仍然大于$b$的对应位置的前缀和。这样就可以证明$c$的平方和一定不会小于$b$的平方和。

我们只要证明对于任意不同于$b$的$c$，可以找到一个合法的，保持前缀和性质的移动，因为一次移动之后可以使平方和变小，证明的剩下部分很好使用按照平方和的数学归纳法解决。

我们找到第一个$c$的前缀和大于$b$的前缀和的位置，因为$c$的前缀和不会小于$b$，如果不存在这样的位置，那么只可能$c$和$b$相同，这与$b$和$c$不同的假设矛盾。

假设这个位置为$u$，我们找到第一个$v > u$使得$v$这个位置两个序列对应的前缀和相等，因为$b$和$c$的总和相等且我们补了零，容易发现这个位置一定能找到。

考虑$c_u$到$c_v$。如果你写下$c_i - b_i$的值，在这个区间内这个值的和为0，且$c_u - b_u > 0$（因为$u$是第一个$c$的前缀和大于$b$的前缀和的位置），那么一定有另一个位置$c_i - b_i < 0$，由于$b_i$单调不递增，肯定有这个位置的$c_i \le c_u - 2$，这意味着这个区间中$c$的权值的跨度至少为2。

那么我们找到最小的$c_x \ne c_u$的$x$，最大的$c_y \ne c_v$的y，设$i = x - 1, j = y + 1$容易发现这是一个合法的移动，且保持了前缀和性质。

于是任何一个解对应的序列都可以通过若干次移动得到满足结论中条件的解对应的解，这就证明了满足结论中条件的解的平方和是最小的，是最优解。

题目链接

HNOI2019 tour的出题人是我。第一天任何一个题都不是我出的，pdf作者写我是一个印刷错误。fish的出题人在这里进行了说明。

（我突然意识到吉司机题面写九条可怜的强大之处了。如果同样的情况发生在他身上，就算pdf出了错一看题面就知道不是他出的）

这个题出了一定的锅，其中我也有一定的责任。我出这个题的时候最开始没有加读入优化，后面加了读入优化意识到标程非常快，于是把$n$开到了5000。我虽然有和命题组的人说我改了数据范围，也发了新的题面，但我并没有强调所以他们可能最后并没有意识到题面的修改(也有可能意识到了但是版本混淆了），所以最后题面还是3000的版本，但是数据却用的是新的。

最后考场上我只好给了3个3000的数据。由于我数据生成器的特殊性，我不太敢保证我能卡掉所有暴力做法或者错误做法（其实我还是比较自信的因为我觉得如果你真有很高端的优化你也差不多会正解了）。

在UOJ上这个题的范围依然是5000，如果你们考场的程序过不去，请把n改成5000。我相信能过3000的程序都能过5000。

下面放简易题解：

30分的DP就是dp[i][j]表示i到j是否存在一条合法的路径，转移就是枚举i的边和j的边。总复杂度是$O(m ^ 2)$。

考虑减少边数。我们把一种标号单独拿出来，只考虑连接同一种标号的两个点的边。 对于一个连通块，如果它是二分图，那么我们仅保留一棵生成树答案也不会变。这是因为我们容易发现这个连通块之内的转移仍然可以实现（只要另一边在两个点内来回走即可）。如果它不是二分图，我们可以加一个自环。

我们考虑连接不同标号的边，只把这些边拿出来我们也可以形成若干个连通块。对于每个连通块， 根据同样的道理我们保留一棵生成树即可（注意这个时候连通块一定都是二分图）。

这样总边数不超过$2n - 2$，用30分DP的思路可以做到$O(n ^ 2)$并且通过本题。

此外，存在一个$O(nm)$的做法能过70分，做法大概就是DP的时候先转移一边再转移另一边。这个做法和正解并没有多大关系而且如果你缩了图之后再用这个做法会比直接dp更慢，所以不再赘述。

吐槽(雾)

"妈妈这个出题人好懒题解写的太简单看不懂怎么办?"

洛谷上有不少其他人写的(很可能更详细好懂的)题解可供参考:

https://www.luogu.org/problemnew/solution/P5292