题面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

作为出题人我发现这个题的数据一不小心造弱了，我以为一张任意图加上一条不是二分图的边可以卡掉大部分错误的判二分图算法。结果没想到连最简单的错误算法都卡不掉，现加了若干组200个点200条边的数据。希望大家做题愉快。

第一次给HNOI出题（其实也是第一次给NOI赛事出题）。

题目链接

稍微了解一点MIT的人（比如知道Infinite Corridor不是真的无限长)可能看完题就知道出题人是谁了（然而好像因为奇怪的原因不能把学校名写在题目里，不过大家看到“某大学”，而不是“T大”或者“P大”可能也知道是怎么回事了？）。

简易题解：

如果第i个数之前的运算符是and，则这一位设为1，否则为0，得到的二进制数记为$x$。

对每一位分别考虑，对于第i位，如果第j个数是1，那么这一位设为1，否则为0，得到的二进制数记为$b_i$。

以左边为最低位，按前缀归纳容易证明，第i位的结果为1，当且仅当$x < b_i$。

我们将b从大到小排序，结果设为c，那么答案不为零仅当在c的顺序下，r中没有任何0在1的前面。找到r中第一个0的位置，假设是k，那么解x要满足$c_k \le x < c_{k – 1}$，于是答案是$c_{k – 1} – c_k$。

题外话：

当时出题的时候很紧张，是真的紧张，因为觉得实在是太水了。我当时的70分做法是猜结论，大概就是猜到有用的DP状态有$O(nm)$个再bitset。然后觉得这实在太好猜了，其实根本不用猜，只要你注意到DP状态可能不满这个事实，然后直接记录有用状态就行了。

我当时很怕结果出来十几个AC，全场70。然后就再也没人找我出题了。

当时就不停的想HNOI有什么水题，是不是比我这个更水来安慰自己。

后面想想给大家送送分也好，至少这个题不是原题或者错题，能让自己成为大众喜闻乐见的出题人也不错。

结果分数分布大家都懂的。我至今不知道拿50分的是怎么回事（$n$只开了$500$？拿50分的人能不能在下面评论区说一下怎么拿的）。于是我的顾虑成了多余的。

不过这也不错，一来我的题终于不是HNOI最水的题了，二来我的题很可能送人进队（比如你A了或者高分暴力），不太可能送人退役（最多就是你30分暴力分挂成10分或者0分）。Still，如果有人因为我的题暴力写错退役我只能抱歉了，对不起我给了30分暴力分。

至于重测，那是因为我在Windows下造的数据，然后由于跨操作系统，换行符出了点问题-.-

考场上被各种倒推做法虐了。

其实倒推本质就是动态维护字典序。我很高兴大家因为我的题发明了一种新的排序算法。我可以把这个题改成每次模一个不同的数，然而似乎还是有基于倒推的奇技淫巧可以做。我也可以出成二进制高精度什么的，但是感觉它们还是可以过，也就是说在不懂正解只会倒推的（也就是大多数）人眼里，我把这个题目弄得更毒瘤而不是更神了。

说起来$O(\frac{nmq}{w})$可能是能过的（UOJ上能过TAT），解决方法大概是把$q$弄大，比如$10,000$。但是读入就很tricky了，可以压字符读入但是这样也很毒瘤。

所以大概这个题也只能放了吧，虽然不得不说我不是很喜欢这种倒推的做法，太直接了，个人感觉和标算没法比。但是也没办法，就像一个优美的题，结论就是输出a+b，也会有不明真相的群众写出一种和按位模拟加法等价的做法，你还没什么办法卡。

首先你得看了题和题解至少算法二之前的部分。

题解地址：http://vfleaking.blog.uoj.ac/blog/2292

我们把每个询问转化为总和减去大于等于最大权值的部分的后缀和。

接着我们按w从大到小加入点，考虑维护每个点的子树中的最小深度。

这个怎么维护呢，考虑一个点肯定是更新它到根的路径，所以我们用类似LCT的access的方法更新，我们可以保证随时每个链的最小深度都相同，如果当前的链的最小深度小于用来更新的值就直接退出，否则的话我们就更新，最后再把这些更新了的链连起来。

复杂度显然是$O((n + m)\log{n})$的，用类似证明LCT复杂度的方法证明即可。

答案也很好算，记录一个后缀和即可，你会发现更新的时候也很好打标记，询问也很好处理。

怎样，是不是只要有模板就好写又好调？而且时间效率还不错呢。

代码：http://uoj.ac/submission/123579

短路

By matthew99

算法一

直接暴力 dfs，复杂度指数级，期望得分 10 分。

算法二

用最短路算法，复杂度 $O(n ^ 2 \log n)$，根据实现情况可以获得 10 至 30 分。

算法三

猜想只能往右或者往下走，然后做一个 $O(n ^ 2)$ 的 DP，可以获得 30 分。正确性证明参见算法五。

算法四

在算法三的基础上进行对称性优化或者使用滚动数组，可以获得 50 分。

算法五

我们考虑假设我们要从左上角走到从外到内第 $i$ 层任意一个中继器上，那么我们最少需要多少代价呢？显然我们一共最少走 $2i - 2$ 步走到 $(i, i)$ 上。其中，第 $1$ 层到第 $i - 1$ 层每层都必须经过至少一个中继器，除了这 $i - 1$ 步，还要再走恰好 $i - 1$ 步。

我们发现剩下来的 $i - 1$ 步至少要走的是 $1$ 到 $i - 1$ 层的前缀最小值之和，为什么呢？考虑一条走到第 $x$ 层某个给定位置且只到过前 $x$ 层的最短路径，那么该路径的最后一步要么是从第 $x - 1$ 层走下来，要么是在第 $x$ 层又逗留了一次。如果是后者，我们总是可以把这最后一步挪到前面去走，相当于对于某个 $k$ 在第 $k$ 层先走了这一步，然后把这一步之后的路径平移一下而不影响平移的这段路径的总时间，这样代价变化就是第 $x$ 层的 $a$ 与第 $k$ 层的 $a$ 的差值。这样我们就推出，如果第 $x$ 层的 $a$ 不是前缀最小值，那么肯定不是最短路径。因此，最短路径肯定不会在不是前缀最小值的层停留超过 $1$ 次，于是这条最短路就是把所有的前缀最小值所在的层的最左上角的点用 L 型的曲线连起来的路径。

那么假设我们走到的最深的一层是第 $x$ 层，首先第 $x$ 层不是前缀最小值的话那么一定不是最短的。如果是前缀最小值，那么最短路径就是先走到第 $x$ 层左上角，再绕一圈绕到第 $x$ 层右下角，再走出去（代价和走过来是一样的）。

这样，我们暴力枚举 $x$，走到第 $x$ 层的代价可以在线计算，然后每次更新答案即可。

时间复杂度 $O(n)$，期望得分 100 分。

同样的我们也证明了算法三的正确性。

怎样，是不是一个超级送分大水题呢？

天路

By zhj, vfleaking，题解 By vfleaking

什么鬼？

嘿嘿嘿……vfk 又来出题玩玩了。事情是这样的，我和 zhj 发现了一个好玩的 idea，然而我并不知道怎么套个优雅的模型。这时 zhj 拯救了世界，于是就出出来了。

哎说实在的过去的一年给 CCF 出题有点心累，在自家 UOJ 上出题各方面还是爽多了2333……

依稀记得 NOI2016 讲题时我兀自地讲讲讲，台下纠结分数线的梦想们并没有多少热情听。后来当我看到分数线公布以及签约的现场有点百感交集，感觉给 CCF 出一次题的事情多，责任也好重……在 UOJ 上自己随便出出出题至少不会直接影响选手痛失金牌。

但愿我出的萌萌哒题目们都能让大家有所启发吧。

谜之声：怎么近似算法都出到 OI 里啊？这真 NOIP 难度？

咳咳客官别急，往下看。敢承诺这个近似算法非常 NOIP 向，并不是那种数学大不等式乱搞证 bound 型。

算法一

对于 1 号测试点，$n \le 100, a_i \le 100$。

大暴力！

你会使用 for 循环吗？

时间复杂度 $O(nV^2)$，可以获得 10 分。（其中 $V$ 为权值范围）

算法二

对于 1,2,3 号测试点，$n \le 100$。

权值范围好大啊……

不要慌，你可以先枚举 $k$，然后枚举 Nokia1050 是在哪一段时间连续拦截了 $k$ 次攻击嘛……该区间中高度的最小值和最大值作为高度区间。

你会使用 for 循环吗？

时间复杂度 $O(n^3)$，可以获得 30 分。

算法三

对于 4,5 号测试点，$n \le 1000$。

在算法二基础上，把每次扫一遍求最小值最大值改为 for 的时候乱维护维护就行了……

（而且 $O(n^3)$ 常数好就过了呢）

（感觉在 CCF 系列比赛这样送分会被选手喷的……hhh）

时间复杂度 $O(n^2)$，可以获得 50 分。

算法四

对于 6,7 号测试点，$n \le 10^5$。

诶数据随机？

同学们你想到了什么！随机数据的前缀最小值只会变化 $O(\log n)$ 次对吧！

所以当我们固定左端点移动右端点时，区间内最大值与最小值至多只会变化 $O(\log n)$ 次。

拿个单调栈维护一下……每次给对应的长度区间更新答案。

脑抽选手可以使用线段树，但其实由于答案单调，所以可以变成给一个长度的后缀更新更新，于是就能 $O(n \log n)$ 的复杂度了。

可以获得 70 分。

算法五

还是数据随机的情况，观察数据我们注意到如果区间长度够长，那么答案就非常接近$10 ^ 6$。

所以我们设一个几百左右的值 $l$，然后处理小于 $l$ 时的答案，剩下来的输出 $10 ^ 6$ 即可。

同样可以获得 70 分。

算法六

好了好了所以之前的部分分跟近似算法都没什么关系……

这题应该怎么近似呢？你想，要是直接把权值除以一个大常数，做完之后再乘回来，看上去好像很近似！但是冷静冷静就会发现这样做出来是个绝对误差的，如果碰到 \begin{equation} 233333 - 233332 = 1 \end{equation} 这种就 GG 了。

所以……相对误差，看上去很没头绪。

来来来先把近似算法扔进垃圾桶，来想想如果要你求出准确解，你可以怎么做。

一个思路是，我们应该是枚举一个 $k$ 然后某种方式维护一下，但这个看上去就很没办法改造为近似算法。

诶，那如果告诉你一个常数 $c$，我们来把答案 $c_k$ 划一划范围好像很兹瓷啊……那 $c_k \ge c$ 可做吗？

……好像是可做的诶，因为最终的答案肯定是单调递增的，所以范围肯定是一段连续的 $k$。我们可以两个指针再开两个栈乱扫扫，左端点往后挪一挪，右端点也往后挪一挪……就能把 $k$ 的范围求出来了。

嗯很好，于是我们就可以每次找找 $c$，划分 $k$ 的范围。当范围足够小的时候，就可以把这一段的 $k$ 都用同一个数近似了。

事实上，你只需要取： \begin{equation} 1.05^0, 1.05^1, 1.05^2, 1.05^3, \dots \end{equation} 就可以啦！每一段里面随便找个数当答案一定不会超过相对误差的容许范围。

现在还差一个想题时的直觉 —— 就是需要划分的段很少……只要注意到其实段数是 $O(\log V)$ 级别的……23333333……别看人家 $1.05$ 小，但人家也是个指数函数。

中间找到 $k$ 的范围只需要 $O(n)$ 时间乱扫，所以总时间复杂度是 $O(n \log V)$。如果把 $5\%$ 当做变量 $\epsilon$，那么时间复杂度就可以写为 \begin{equation} O(n \log_{1+\epsilon} V) = O(n \log V / \log(1 + \epsilon)) = O(\epsilon^{-1} n \log V). \end{equation}

这个算法其实说明，所有 $f(i)$ 随 $i$ 递增且有个算法告诉我 $f(i) \ge k$ 的第一个 $i$ 在哪里的话，都可以套这个近似算法！（然并卵）

噔噔！这题就做完了！相信比赛时很多选手都轻松 AC 啦～

（为什么一道水题的题解我能写这么长）

套路

By matthew99

算法一

枚举区间，再枚举区间内两个数统计这个区间的答案，再求出整个问题的答案。时间复杂度 $O(n ^ 4)$，期望得分 7 分。

算法二

用 $\mathrm{ans}[l, r]$ 表示区间 $[l, r]$ 的答案，很容易发现 $\mathrm{ans}$ 可以由如下递推式算出： \begin{equation} \mathrm{ans}[l, r] = \begin{cases} |a_l - a_{l + 1}| & \qquad r - l = 1, \\ \min\{\lvert a_l - a_r \rvert, \mathrm{ans}[l + 1, r]\,, \mathrm{ans}[l, r - 1]\} & \qquad r - l > 1. \end{cases} \end{equation}

时间复杂度降为$O(n ^ 2)$，期望得分20分。

算法三：

注意到如果 $m \le 1000$，那么根据鸽巢原理，长度超过 $m$ 的区间肯定有两个相同特征值相同的跳蚤，因此答案是 $0$，所以我们处理长度小于 $m$ 的区间即可。

时间复杂度为 $O(nm)$，期望得分 27 分，结合算法二可以获得 40 分。

算法四：

使用任何一种时间复杂度为 $O(n \sqrt{m + n} (\log m + \log n))$ 的算法（请注意大O符号的意思），即可获得至少 $70$ 分。由于这些算法过于复杂且与标算没有太大关系（或者是标算强行多写了一个 $\log$），故不再赘述。

算法五：

我们考虑如果区间长度是 $x$，那么最小差不超过 $\frac{m}{x - 1}$。

设一个常数 $S$。

如果 $x \le S$，则用类似算法三的方法，可以做到 $O(nS)$。

如果 $x > S$，那么最小差不会超过 $\frac{m}{S - 1}$。我们扫描一遍序列，考虑当前位置作为右端点，用 $r_x$ 表示权值为 $x$ 的数最后出现的位置，然后每次新加入一个数 $z$ 之后，对于所有 $\lvert z - y \rvert \le \frac{m}{S - 1}$，利用 $r_y$ 进行计算更新答案，然后 $r_z$ 即可。时间复杂度为 $O(n\frac{m}{S})$。

设 $S = O(\sqrt{m})$，则总时间复杂度为 $O(n\sqrt{m})$，可以获得 100 分。

这是不是 UOJ 历史上最水的C呢，相信大家 AK 得非常的爽，作为出题人之一看到大家 AK 我也感到非常荣幸。

UPD：好像打脸了。

退役前最后一次NOI，如果不写点什么感觉太遗憾了。

明天是湖南省队集训的第一天，地点是师大附中。基本上是上午8点到下午1点考试，下午2:30到5:00讲题改题。

记录一下每天干的事情吧。

随之而来的15号凌晨有一场CF，19号晚上有一场SRM。我当然希望能打好，但是我也知道这往往可遇不可求。UPD：19号新增一场CF紧接着SRM UPD：决定还是不打CF了

2016年7月11日

省队集训第一天。

早上去报到，接下来去机房开始考试。

这一场前两题都非常简单，第三题是一个稍有难度的数据结构题，我在考场上很快写完了前两题，第三题却做了很久，而且做法也过于复杂。

中午发盒饭在机房吃。

下午发现包括我以内的很多人都挂了第一题。

第一题的题意是这样：

定义一个置换的平方为对1~n的序列做两次该置换得到的序列。已知一个置换的平方，并且这个结果是一个排列，求该置换。

输入第一行一个数n表示排列长度，接下来一行n个数描述排列。

有解则输出一行n个数表示原排列。否则输出一行一个-1。

这个题，几乎绝大部分同学都写了一个checker检查。

大概流程是这样：

1. 读入排列a。

2. 用某种途径得到输出b。

3. 检查是否有对所有i有b[b[i]] = a[i]。

这样的检查方式以及检查通过的程序都是有问题的，你们能看出为什么吗？此外，你们能否不利用a只通过对b进行简单处理使得这个checker正确？

祝贺ppfish前两题都没有挂，第三题打满了暴力并成功获得了第一名。

此外今天才知道，g++在不开O2的情况下，开了-pg选项会变慢很多。

晚上看了一些黑(xiao)科(chang)技(shi)。

7月12日

省队集训第二天。

上午考试，去的时候发现每天中午的盒饭20元，感觉可以和火车上买饭的价格比比了。三道题做法都不难，但是我却在后两题都卡了一阵子。三题都有大样例，虽然第三题大样例过了之后我依然发现我犯了一个非常厉害的错误（虽然听说数据强度和样例差不多）。

最后没挂分。然后发现第三题暴力可以过85分，因为不仅树都是随机的，而且每个点的父亲编号都小于它自己的编号= =b

共价大爷第三题被卡常数了，7s时限，链的点全部TLE了，不是链的点零点几秒，虽然为什么会这样上面已经解释了233

今天早上把公交卡塞进了手机上，考完之后才发现来的时候手机掉在了车上，但是幸亏早上坐是我们家的车而不是公交车23333。

今天的第二题是，给定$n$个点，每个点的度数都有一定的限制，现在要你选择一些点构成一棵树并满足度数限制，问你总共有多少种方法构成大小分别为$1$到$n$的树。$n \le 100$。

这道题目需要一些计数能力，你们会做吗？

下午带着自己电脑过来到隔壁机房蹭网，开了一下SRM639的hard，然后发现自己最不擅长做的就是这种类型的数学题，需要分一些情况并且要考虑的很多，我发现仔细想出了很多贪心算法却一个也不会hack，后来只好看杜爷代码发现却很简单，然后发现过不了样例，接着便沦为了人眼diff选手，一阵子之后发现居然五点了！我要和tty他们一起坐车回去，赶快收好东西到原来的机房去却发现他们早就走了，感人肺腑。

晚上做了SRM640的hard。

看到几篇和本日志风格类似的日志：

http://wronganswer.blog.uoj.ac/blog/1831

http://yjqqqaq.blog.uoj.ac/blog/1827

我写这个日志，意义在哪里呢？大概也想体验一下写日记的感觉吧。而且如果NOI出现不可理喻的低级失误，这大概就是OI生涯最后一段训练和除了NOIP之外最后一场比赛，不留下点文字太遗憾了。假如进队了，那也是最后一次作为正式选手参加NOI。

关于昨天的第一题，坑点就在于题目中给出的是一个排列。

置换对排列的作用就是交换这些数的位置，也就是说比如置换的第1个数是3，那么就将第一个数换到第三个数的位置上，而不是将排列的每个值变化成另一个值，比如说把值是1的数变成值是3的数。

所以在读入排列a之后，结果是排列a的置换应该是排列a对应的置换的逆。只需要一开始对a取逆就可以了。

那么如何不利用a只通过对b进行简单处理使得这个checker正确呢？我们可以不对a先取逆，而是得到输出b之后再对b取逆，两者对应的答案是一样的，正确性留给读者思考。

7月13日

省队集训第三天。

上午看三道题，发现第二道题居然是三年前省队集训考过的题，另外两题也不难。

开始的时候做第三题，一开始一直想用单调队列+multiset但是没注意到单调性，然后想写线段树，后来才发现居然是有单调性的，于是顺利开始写了个multiset，每次取最小值并支持插入删除。

考完之后德霸哥提醒我，我突然感觉发现了世界的奥秘。

你 大 爷 ， 这 他 妈 就 是 个 堆 啊

由于这是一道考察stl基础应用的好题，一开始用专业卡stl的cena测搞得我虚的要死，后来发现改成lemon了，不虚不虚。

第一题我复杂度比标算优，不过这套题年代久远，在当时标算的复杂度就已经很不错了。

听noname说HNOI也出现过同一道题出现两次的现象。省选重题，省队集训重题，接下来是什么了？现在终于知道为什么去年老师要我们把历年的NOI题都做一次了23333。

下午看到成绩，第一题数据有问题，但是实测如果数据正确应该能AC，另外两题都AC了。

第一题题意是，给定一张点数$n$不超过10000，边数$m$不超过200000的图。每条边有一个权值和长度，每种长度的边都不超过30，求最小生成树的边权和的期望（注意权值和长度不是同一个东西）。

一个经典的思路是，考虑相同权值的边，将权值比它小的边缩起来，然后考虑这种权值的边连成的每个连通块，于是问题转换成生成树计数。

用$s$表示相同权值的边的数目的最大值。考虑用矩阵树定理计算出不包括每条边的生成树个数和总的生成树个数，复杂度是每次$O(s ^ 4)$，但是考虑到如果当前图中有$x$个点，那么必有$x - 1$个点被缩起来，因此很容易证明复杂度实际上是$O(ns ^ 3)$。此外，为了避免精度误差，可以找一个大于$2 ^ s$的质数（如1073741827）并在模意义下做。

由于常数小实际上上述算法已经可以AC了，但是你们能不能做到$O(ns ^ 2)$呢？

晚上颓了很久QAQAQAQAQ，最后做了个SRM642hard，是个傻逼800分，然后网络不好，交题交了很久。交题花的时间比做题长，颓的时间比交题长，令人感动。

昨天晚上做了个噩梦，梦见我打游戏被老师抓个正着，结果就醒过来了。我现实中却很久没被抓，结果果然看别人打游戏还被老师抓了。我最近整个就没效率啊。还号称可能是最后一场OI比赛，我却用这点时间在颓，表里不一不是我想要的啊。知道自己不应该颓却像戒毒一样难以停下来，简直感觉身体被掏空。

CTSC之后去准备水考，准备好好认真搞搞文化看能不能恢复到班上前几名，却也落得个半颓半学习的下场，最后成绩也不太尽人意。平时不注意就一直颓，曾经自诩“我的下午从五点开始”，颓的时间还有一辈子，搞OI的时间却只有这么一点，还是希望明天开始能少颓一点。

想起来我做过的梦，一半准一半不准，去年HNOI之前梦见自己滚大粗但是还是踩线进队，结果果然滚大粗但还是踩线进队，CTSC之前梦中进了两次队，结果梦里把两年的队进完了，NOI之前觉得NOI滚粗了也没多大事，结果就做了个梦，梦见自己NOI 500分都没上，最后被金牌线卡（当时还是认为金牌线是集训队线），希望这是把粗在梦里滚完了吧233。

我曾经天真的想在NOI之前刷完500以后所有SRM（因为从670左右的地方开始后面的场我都做过），现在看来不太现实了，要是NOI真的滚粗了，感觉整个人还是会浑身难受啊，虽然保送了我也觉得不管怎么样也还是要继续搞算法竞赛，但是那时候再做SRM心境也不同了吧。

明天晚上（准确来说是后天凌晨，但是我还是习惯说明天晚上）有一场CF，我知道只要涨rating就能LGM，但是涨rating也不是见容易事，大概不打出一个能过WC的名次还是很危险的吧。但是如果我今年（或者今年和明年）的OI想要走的更远，就应该做到每一场比赛都打好，毕竟想想最近也没打过什么比较差的名次。如果明天真的滚大粗就会成为我NOI也可能滚粗的信号弹，所以除非出现不可理喻的低级错误我绝对不会滚粗。因此还是希望我能把最近CF名次至少都不差的现状持续下去或者争取做得更好。当然光说不做假把戏，明天至少要记住我心态不要崩盘，题目看清想清再下手，争取一遍过。总之祝我好运吧！

昨天的第二题做法是，我们容易用prüfer序列证明每个点度数分别是$d_1, d_2, \cdots, d_n$的树的个数是$\frac{(n - 2)!}{\prod{(d_i - 1)!}}$，因此，我们考虑枚举每个点选不选和每个点的度数，用$\mathrm{dp}[i][j][k]$表示前i个点，选了j个点，度数减一的和为k的所有方案的$\frac{1}{\prod{(d_i - 1)!}}$之和，容易实现转移，特判大小为1的情况（答案就是点数$n$）之后最后答案就是$\mathrm{dp}[n][\mathrm{size}][\mathrm{size} - 2] \times (\mathrm{size} - 1)!$，复杂度是$O(n ^ 4)$，常数较小可以通过。

此外可以用FFT优化，但是这仅限于理论复杂度的优化，实际上速度尚不及直接暴力。另外APIO2016的第一题也可以用FFT优化，同样暴力也可以通过，只是暴力速度不如FFT优化。

7月14日

省队集训第四天。

上午三题都挺简单。第一题强行三个subtask，前两个n是$10 ^ 6$，最后一个$k$是$10 ^ 9$而$n$只有2000。第二题KMP傻逼题我不会KMP只好强行用hash上。

接着发现我、共价大爷、owaski都能AK。

最后成绩出来我们三个都喜闻乐见的自爆了。我第一题第一个subtask一个地方没取模爆了int。共价大爷第三题答案是0就会错，owaski第一题没看到$n$有$10 ^ 6$。于是挂成了295,280,260，令人感动。

我怎么又爆int了？再爆int我真的不能忍了，为什么一个取模我就是做不到。还有读入优化快速幂也是每天错一次，简直不知道在干嘛。

所以怎么避免呢，认真写当然是最好的，我最近写程序都极为不认真，这样什么错都容易犯。

还有一些人可能会想出建一个类或者加数之后取模的函数什么的办法，让程序自动取模，但是首先这样太麻烦，其次你怎么知道你哪天就忘记用类或者是函数呢？再者这也是一个治标不治本的方法，解决了这个错还有那个错，错是犯不完的。我曾经天真的觉得错误就那么多，最后每次一到大考却出现了新的错误，改完一个又一个，时间一久老的错误又卷土重来，最后什么都解决不了。

昨天我提到过第一题存在复杂度为$O(ns ^ 2)$的做法，怎么做呢？

考虑如何快速求删掉一条边的生成树个数。我们发现删掉一条边，要求行列式的那个矩阵中最多只有两行发生了变化。

那么我们可以参考策爷去年的集训队互测题《最大异或和》的做法，考虑维护消元之后每一行是由原来的矩阵的哪几行分别乘上多少组成的，假如我们要修改某一行，我们就看看这一行对消元之后的矩阵的哪几行有贡献，找到有贡献的最后一行，让后用它消去所有行，注意这样不会导致主元发生变化。

接下来对这一行做对应的改变之后，再对这一行消一次元即可。这样每次的时间复杂度降为$O(s ^ 3)$，因此省去了一个$s$，复杂度变为$O(ns ^ 2)$。

另外要注意改变其中一行之后可能不满秩，改变另一行之后却满秩的特殊情况，以及行列式交换两行值要取反，这些都比较容易处理所以不再赘述。

晚上就是CF了，一定要沉住气啊。而且明天考我的题，上午太困也没关系咯23333

7月15日

马上就开始CF了。听说19号还一场那么这一场其实只要不暴跌，问题也不大？重点是这种比赛我本来就不应该有太大的压力。

如果LGM了，终究下一场还是不太想打了，毕竟马上NOI了真的不太想最后又把这个LGM丢了，虽然我知道我很看重rating......但是还是不太放得下。毕竟自己还是有以LGM身份参加NOI的梦想，还是不希望他在自己手上这样破灭。

即使我滚粗了，只要不太厉害下一场也完全有翻回来的机会。已经没有什么好怕的了。

虽然你们可能说我立了很多flag，以及压线从来没人涨过这种奇怪的debuff，但是看看欧洲杯这次最后两场，以前某两队之间的比赛基本都是某一边赢，这次偏偏成了另一边，一切皆有可能。

考完了，不FST是可以上LGM的。F题状态不好只会三方log，最后没敢写。

考前觉得自己A不能一遍过，很认真的写完，很晚才交结果一次过pp了，觉得果然自己的感觉不一定对。

结果快下考的时候，A被hack了= =b

不过估计这场FST的人很多，我估计也有可能FST，甚至FST多题，成事在天。

A不太可能再挂了。B挂了应该还是能LGM，C挂了不知道，D和E挂了肯定不太行了。不过还是挺充裕的，但是真的虚的很啊，这场pretest太弱了。

最后没有FST，rank4，顺利LGM。难得的国家队名次，我已经拿了不知道多少次rank5了23333。claris也拿到了面试名次，rank6。（CTSC英文面试那这个如果真的有面试是不是中文面试呢？歪果仁不会说中文岂不是大家都稳了啊）

这次上LGM，喜悦当然是有，然而我也再一次知道，所谓flag都是假的。

AC五道题rank5一定会FST吗？不一定，我最近多次证明了这一点。

压线一定会暴跌吗，不一定。

对拍过的题一定会FST吗，不一定，这次我的E题对拍了也没有FST。虽然之前的对拍过的题都FST了= =b

想起了不久之前的CF345，当时我2775的rating，第一次在div1 pretest AK，心想终于要LGM了，却没想到刚下考就被人指出B是错的，我便想估计2800+还是有的。

最后的结果令人吃惊，FST了三道题，目前我听说别人CF上FST的最多几次的也就只有某一次有人FST四道题以及某几次有人FST三道题，掉了一百多的rating，那一次之后我还是收到了不少打击。

之后的VK cup，我再一次FST了一道题，从大约四十多名变成了一百多名（也就是从集训队变成了前一百的约都拿不到23333）。

上IGM之后我的rating跌宕起伏，虽然一直没有掉下过2600，但是也足够让人胆战心惊。大概人生也可能就是这样吧。

省队集训第五天，考的是我的题。

我出的模拟题，没有一套不出事故的，这一次也做好了出事故的准备，主要还是怎样应对。上次我应对得很不好——题面出现与数据不合的地方，应当改数据而不是题面，因为改数据只要我知道就行，改题面要重新通知所有人。

23333333果然出事故了。

上午他们在考试，我在这边造数据，结果发现卡了A算法卡不掉B算法，卡了B算法A算法又轻松AC了，十分感动，最后决定大赦天下各送一半分，感觉我这么良心的出题人很难见啊。

最后还是被水过去了，肝败吓疯。

讲题的时候听说我的提答题是addition chain的特殊情况，并不是NPH的，身败名裂......

下午外面风雨大作、电闪雷鸣。

7月16日

省队集训第六天。

今天的题不太可能全部考场上写完，然而我第二题被卡常数，第一题写错，第三题暴力骗了50分。

今天的题原来是给省选模拟赛准备的，仔细想想要是真的是省选模拟赛应该还是非常贴近真正的满是瘠薄题的HNOI啊（雾）

第二题是一个裸轮廓线DP，我因为被卡常数鏼了三个小时无果，因为我没有预处理转移，仔细想想这类题目，能预处理就先预处理，因为预处理不仅复杂度是稳定的，而且即使要矩阵乘法加速也很容易，可移植性强。

第一题是一个数论七合一，虽然都没什么难度，我却犯了一个傻逼错误，我以为无根树计数双重心不用处理，结果就错了，主要是当时第二题卡了三个小时没时间太急了，唉。

第三题是一个大字符串，标算代码量差不多是我前两题的代码长度的总和（也是昨天模拟赛我标程的代码长度总和的几倍233333），由于事先知道一点信息所以果断知道要跳过把题目留给另外两题了。

不得不说第二题写错真是败笔，第一题其实也很容易多过一些点的。

今天第一题的一个子问题是，求n个点的带标号二分图个数，原题$n$是1000但是实际上可以做到$O(n \log n)$，你们会做吗？

7月17日

省队集训第七天。

今天的第二题很简单，第三题是一个送分送的和水考差不多的提答题。第一题较难得分，我最后一个多小时一直在鏼第一题，写了8K代码成功拿到0分，感人肺腑。

第二题大概是一个障碍多边形在绕着地球公转，本身在自转，自转是绕着重心，太阳是一个点地球是一个圆，求某个时刻太阳照射到地球上的弧长。

有一种的做法是，算出自转角度和公转角度，将每个点绕着重心将算出的旋转角度代入旋转矩阵算出自转后的位置，接着将每个点绕着太阳将算出的旋转角度代入旋转矩阵算出公转后的位置。这个算法对吗？

第一题题意大概是要我们维护一个亲戚关系，考场上时间不够导致写代码BUG很多所以零分是必然的了，其中一个BUG特别有趣。

父亲的因为是father，母亲的英语是mother，我用fa表示父亲，mo表示母亲，写着写着就成了ma了，然后我就发现，怎么一堆的mo啊，mo不是模数的意思吗，惨啊赶快都改成ma，然后喜闻乐见，mother我判断前两个字符是否分别是m和a而不是m和o，于是我的程序重男轻女，只认父不认母。顿时感觉自己多年的英语白学了2333333

下午听说第二题没过样例都能AC，论做UR特判样例的重要性，多拿三分啊233333，事实是第二题好像，不管障碍多边形就AC咯，结果这样都没多少人AC，人没有梦想就是咸鱼咯。

以及这么多个人连重心都不会求是怎么回事啊！感觉这不是，计算几何基础知识么，应该和求面积一起学的（雾）。论看完黑书白书的重要性。

祝贺共价大爷采取了直接不做第一题的正确策略，在第二题AC之后把时间全部留给提答题，最后成功获得第一名。

昨天我提到了$n$个点的带标号二分图个数怎的统计问题。这个问题怎么做呢。我们先看看$O(n ^ 2)$的做法吧。

对于一个图，考虑它的黑白染色方案数，那么当它不是二分图时，个数是0，是二分图时，个数是二的连通块数目次幂。

考虑对所有图求方案数之和。可以考虑枚举黑点个数，那么容易得到公式$g_n = \sum_{k = 0}^{n}{\binom{n}{k}2^{k(n - k)}}$。

接着，我们用容斥求出连通图的贡献，也就是枚举一号点所在的连通块的大小。于是有公式$f_n = g_n - \sum_{k = 1}^{n - 1}{\binom{n - 1}{k - 1}f_kg_{n - k}}$。

最后考虑求非连通图，无非也是枚举一号点所在连通块的大小。于是有公式$\mathrm{ans}_i = \sum_{k = 1}^{n}{\binom{n - 1}{k - 1}\frac{f_k}{2}\mathrm{ans}_{n - k}}$。

接着考虑如何做到更优。

首先$g_n = \sum_{k = 0}^{n}{\binom{n}{k}2^{k(n - k)}}$怎么优化呢，考虑参考CZT的思路，$2 ^ {k(n - k)}$容易拆成$-2k ^ 2 + \frac{k ^ 2}{2} + \frac{(n - k) ^ 2}{2}$，于是容易展开成FFT的形式。

接下来的两个公式容易用分治FFT做到$O(n \log ^ 2 n)$。

怎样做到$O(n \log n)$呢，可以参考策爷2015年的集训队论文，一张图是由若干个连通分量组成的，因此任意图的指数生成函数可以看做连通图的指数生成函数的$\exp$，相反连通图就是任意图的$\ln$了，所以$f_n$的生成函数就是$g_n$的生成函数的$\ln$，而$\mathrm{ans}_n$的生成函数就是$\frac{f_n}{2}$的生成函数的$\exp$，只需要用多项式$\exp$和$\ln$即可在$O(n \log n)$时间内解决该问题，而二者的做法均可以在该集训队论文中找到。

7月18日

省队集训第八天。

三道傻逼题+挂了10分=爆炸。第二题加了往点数组里加了一个终点但是离散化数组没加，挂成90分。考挂自己弱没什么好说的。

祝贺共价大爷，Cyan，HJWJBSR，Fuxey，ZZD五位AK爷。

明天的CF仔细想想还是不参加了吧。不管是谁都不敢确保自己下场比赛能在2986的rating守住lgm，即使是tourist也有可能失误，一旦下场比赛滚大粗，我怕在现在还是很可能对我整个人的心态产生影响，从而影响NOI。虽然下场比赛有可能打得好，但是我感觉也不能操之过急，如果水平在那里，什么时候涨rating都一样。而且那天晚上还是TC接着CF，两场比赛连着打第二场可能会受影响，再说我也想NOI之前好好休息一下。CF打完11点而且打完CF一般比较兴奋有点难入眠。所以还是NOI之前不打CF了。

明天是省队集训的最后一天，仔细想想这次省队集训大的失误除了第一天一个基本上所有人都犯了的错误之外，还是没有别的错误的，希望这次能够完美收尾吧，不要最后一天滚个大粗。

昨天提到一个求自转公转一定时间后的位置的做法，这个算法是错误的，原因很简单，如果你用旋转公式给整个多边形进行公转，那么同时整个多边形实际上也自转了一定角度，其实理解起来和地球日太阳日的区别差不多。论地理在OI中的重要性。

正确做法很多，最简单的做法之一是先把重心公转后的位置算出来，再按照相对重心的位移恢复其他点，再进行自转即可。

7月19日

省队集训第九天也是最后一天。

今天三道题都比较有意思，第二题很快做完，第三题想了个错误算法然后很快写完，接着很快做完了第一题。然后就开始浪了。

结果喜闻乐见的第三题就挂了。

今天第三题题意是，给你一个带权完全无向图要求把点集分成两部分使得两部分的点之间的边权的最大值之和最大，这是一道原题但是我没做过。

我的做法是，一开始点集只有1号点，接着选一个与当前点集之间的点连边最大值最小的点加入点集，每次将点集和点集的补集的集合内的最大边加起来更新答案。

这个算法你能具体解释一下为什么会错吗？

今天晚上是SRM 695和CF 363，后者已经决定不打了，前者我还是要打的，希望不要考挂。

300慢慢的认真写，写完认真检查了好久。分比别人低很多。

接着看到群里都说500不会做，于是开了800。

800想了一会儿写了一个发现萎掉了，然后就一直以为有然后，然而并没有然后......当时就意识到肯定要滚粗了。还剩20+min的时候灰溜溜的开了500

500不会，800也不会。

500问策爷说考虑前21条边就够了，我为了保险考虑了30条。

结果杜爷说500要考虑31条，成为CTSC rank5和CF 2899之后又一次只差1。

结果challeng环节发现300被hack了。写这么认真+这么久，你还给我错，其他人比我快还对。最后发现我犯的错，简直不能说是错，简直可以说是我没做出来，算法核心部分我都没有实现。

naive的以为学习petr写的时候认真一点交完再认真检查就能对，结果是真正的petr以比我快很多倍的速度写完并且对了，而我还是错了。果然是水平差距太大已经无法模仿了。

hack本来还失败了一次，结果后来hack回去了，hack回去之后知道要只有25分了急了随便hack了一个又失败了。结果最后爆零了。

我还naive的觉得我能一举target，结果居然掉到了2743。这个结果，我真的完全没有想到。

NOI要是这种名次我就铜牌了。

真的很想和鏼老师还有杜老师同台竞技，最后却发现自己实力远远落后于他们，所谓同台竞技，成了不断的喊“救命”和不断的求程序对拍。

不想传播什么负能量了，NOI之前最后一次TC爆零滚粗了，如果NOI再滚粗就可以向最后一场CF、TC和OI比赛都考跪的吉司机致敬然后看吉司机吃*了（逃）

7月20日

省......不，省队集训已经结束了。

早上看了看CF发现策爷CF掉的比我TC掉的还多......同是天涯沦落人咯。杜爷rank3帅气掉rating。petr帅气TC、CF两个一起AK+win+超过tourist。

非常佩服petr啊，两场比赛连续考还能一场不挂而且都是AK+win，换做是我考完第一场第二场一般都太兴奋就挂了。

明天一早就出发了，这次NOI是我最后一场NOI，我的前三场NOI结果都算好的，这次当然希望能考好。不过这次完全没有任何压力了，毕竟已经保送，当然如果滚粗了我肯定还是很伤心啦。

昨天提到一个错误算法，那个算法为什么会错呢，可以这样想，你加入一个新点到点集，可能导致其他点到这个点集的距离都变大了很多，这样就错了。

比如假设图权值只有0和1，且权值为1的是个二分图，那么答案显然是0，但是当且仅当我集合扩展到了图的X部分或者Y部分的时候答案才会是0，而我的算法就等价于——找与当前点集没有任何边相连的顶点扩展，所以很容易就从X部扩展到了Y部，随机一个二分图我的算法就很容易出错，因为一旦扩展到了Y部，基本上就不太可能还能算出正确的答案了（比如我们可以假设Y部的点度数都不为0）。

7月21日

出了些状况......

早上七点出发到成都再转车去绵阳，然后火车路上遇到状况晚点了，于是就没赶上第二趟火车。然后我们在外面转了好久才找到宾馆在火车站附近住下来。蜀道之难，难于上青天！

看了下上场SRM的800，发现我突然一下子怎么就什么题都不会了啊QAQ

成都东站我来过很多次了，比如WC的时候我就来过一次，最早来还是2013年第一次参加NOI的时候，那年是在电子科大。

而我后面还要去百度之星，打算玩几天再从成都出发到北京。

于是乎，不论是这次NOI，还是我参加过的所有NOI，都是从成都开始，到成都结束了。

不管是什么结果，都当做是命运给我的一份礼物吧。

7月22日

报到日。

上午差点又没赶上火车。

开了下上场CF的F，发现我最近debuff好像有点严重。

7月23日

开幕式上看了很多节目，比如变脸，完全不懂京剧那一套理论。

听到了CCF和教育部抗争10年，终于取消了NOIP保送的事。其实讲道理NOIP保送也挺不公平的，首先我们都觉得NOIP一等奖很容易，比直接高考考上那些学习容易很多，其次在NOIP作弊比在高考作弊容易多了，所以我个人还是持支持态度的。

下午笔试，感觉是四年来最水的一次笔试，三分钟提交满分无压力，虽然后面还是检查了一阵子。

明天就是day1了，希望自己能不留遗憾吧。

7月24日

NOI第一天。

看完三个题发现好像都比较可做的样子，第二题一眼以为是转化为八连通之后搞搞，结果发现答案只有四种可能。

感受一下感觉第二题比较恶心，于是就决定先做第一题再做第三题再做第二题。

第一题做到一半发现暴力有95，瞬间感觉自己在做无谓的努力，然后搞到九点多，感觉非常虚，过了样例就不管了。

第三题猜想互质就行了，结果写了个暴力发现大样例跑不出，然后开始加两句优化跑两下，终于加到能跑出的时候发现答案错了，然后写个大暴力好像排上了顿时慌了。接着发现我有个地方爆int了= =b

于是愉快地开始瞎做，做到一半发现我的方法好像有点萎，接着发现好像要用杜教筛，顿时感觉我走上了不归路。思考了一会儿人生发现好像没有什么救只好强上杜教筛了。

接着到了十点半宣布考试过了一半了。我开始刚T2。

结果发现果然T2才是最难刚的，一开始觉得把每个点周围曼哈顿距离不超过2的弄出来求下tarjan是不是行了，后面发现好像要用set或者map，估计不改成hash很虚要超时。

然后开始想别的做法，发现好像可以枚举一个点判断周围八个方向的情况，然后正要开始写的时候发现不会判不连通。然后发现前面那个tarjan的方法好像也不太好做了。

接着发现好像可以扫描线，每个连通块用最下边的最右边的点统计答案就可以了。

于是开始写写写，发现各种错，过了样例发现判八个方向好像没那么容易，然后瞎几把猜了个结论过了1000个数据的对拍。

于是我在1000后面加个零，拍10000组数据，发现WA得七七八八的= =b

于是令人感动的又改了几下，瞬间面目全非，感觉一副AC不了的样子，瞬间想起了WC拍100000组数据怒挂T2的故事，觉得很慌。然后开始狂对拍狂看代码。

后来觉得还是看看另外两题比较好，然后发现第一题好像三个样例拼起来就挂了，接着发现样例里面n递增于是我一个地方没清空没发现，令人感动......

下午过去看好像AK了，非常感动。

最后说下我对题目的看法吧，我觉得这次NOI的题目还算比较科学，部分分也较为合理，送的比较多，基本属于挂分大于没写正解少的分，这也正是ACM、CF、TC这些比赛的情况。没有码农题，有一定思维难度。而且这是NOI第一次引入杜教筛，感觉科技在进步。

我的第二题判断是否有割点的方法是。考虑每个蝈蝈周围8个方向的跳蚤，按顺时针或者逆时针考虑周围八个方向，如果一个对角线（比如上面和右边）都有蝈蝈那么就在右上角加一个蝈蝈，连通性和这两个相同（因为显然这个对角线上的两个蝈蝈属于同一个连通块）。

接着我们发现，如果按逆时针或者顺时针方向，某一个连通块的两个格子中间和外面都有跳蚤，那么这个跳蚤肯定是割点。

这个做法我不会证明或者证伪，如果有人会证明或者会证伪欢迎在博客下面评论。

7月25日

社会活动日，看了核武器以及很多其他炫酷的武器，接着去了一个公园，然后到了一个阁，听tty介绍了一些建筑学知识。

中午吃饭的时候听到有人说：“你怎么一颗原子弹都没偷出来”233333333

下午和大家颓。晚上开了一个CF题，发现自己一个思路完全不会变通，而且几年前学的huffman编码怎么用两个队列维护都想不起来了。

密码条上有我day2滚粗的flag啊。虽然我并不信还是希望第二天不要考挂了。这还守不住集训队我就把脑袋留在南山。

7月26日

NOI第二天。

当了一发咸鱼，第一题写完第二题写个85分第三题写个84分之后发现分好像比day1的第二名高了就开始守，然后发现第二题居然有部分分，然后提到了91分，然后开始不断检查，最后瞎猜了第二题的几个结论发现都是错的，然后就下考了。

下考的时候很慌很怕第二题是个上百人A的傻逼题。

结果发现我周围距离不超过2的地方就有人AC第二题，令人感动。不过反正我也有91分。

下午去看一分没挂，275分。

感觉今天题目分差比较小啊，第一题还算有点意思，two pointers套线段树，第二题结论还是挺有趣的，只是我太咸鱼了就没去猜了，其实好像去猜也猜不到，我本来想给样例打个表，后来构造了一个极端例子觉得好像分段可以很随机应该不会有啥规律就不管了，事实上好像是有规律的，那我考场上肯定想错了QAQ。

第三题拿到84分之后就不敢往下做了，实际上当时还是觉得第二题不会做放不下，放下了可(gu)能(ji)会(ye)高(shi)点(yi)吧(yang)。

晚上和vfk聊了很多关于他在英国的故事，感觉非常有趣啊。比如英国松鼠很常见，街道很干净，污染很小，天空很蓝。人们喜欢说thank you，餐厅里别人来为你服务也会说一句thank you。还有就是由于版权问题网易云音乐用不了233333

7月27日

上午趣味运动会，发现节目比较高能就逃出来了233333

然后下午闭幕式颁奖领到了金杯。节目也非常厉害，健美操四女一男比例有点鬼畜啊。

感觉这篇文章到这里也要结束了，总要说些什么吧。

首先当然是感谢了。这次NOI的成功，我必须感谢我的父母和老师对我的培养，感谢机房里的同学与我的交流以及对我的支持和鼓励，还要感谢CCF以及各位出题人们和南山中学等提供了这样一个平台，当然还要感谢命运女神的眷顾。

这是我第四次拿到NOI金牌了，当然这次还带有金杯，虽然在六块IOI金牌的tourist面前还是不值一提。

不得不说这四年NOI，最好的当然还是今年和2013年。今年就不用说了，13年的时候我水平比现在差很多却混到了金牌，其实最主要还是树的计数拿到了90分以及低的令人感动的金牌线。这两年都是在四川，或许四川是我的福地吧。

当然实际上我也大概知道原因，13年的时候，我什么负担都没有，觉得就是来玩玩，因此心态很好莫名其妙的拿了金牌。14年想13年我拿了金牌，于是当然便冲着金牌去，15年高一当然想进队，这两年都有一定的负担，反而就滚粗了。今年反正保送了，负担比前两年小，所以心态也好一些。所以感觉我还是这些负担比较小的比赛反而考的好啊，所以为什么那么多人（包括我）都经常CF、TC什么的贴线暴跌。

喜悦之余当然也有忧伤，作为退役的季节，不少厉害的人都没进队。共价大爷、稳爷爷、kpm的滚粗完全出于我的意料之外。我们学校的tty也失误了。absi2011也没有进队。noname由于是D类，以集训队分数忧伤的退役了，有时候进队分数都达到过却不在同一年，也是挺悲惨啊（想想我CTSC2015的分数是不是能进队呢？不过仔细想想好像dls也也经历过一样的悲剧？）。而湖南省选的第二名yml和女生A队Cyan都没有进队。

作为UOJ的管理员，以后很难在榜上看到某些人的名字，看到这些人FST而叹息，看到这些人终于有人AC了某道题而欢呼，也不能在CF、TC上看到这些人的名字了。当我看到UNR上wyy怒虐第二名68分的时候，感觉十分佩服他，却在NOI之后惊闻wyy银牌滚粗。NOI之前的那场SRM，爆零之后kpm还特意安慰过我，然而他也无缘集训队，感觉真是十分忧伤。

在闭幕式结束后，lzz和wyy还和CCF的一些人讨论过NOI的出题问题，大概就是暴力和暴力之间分差过大，而暴力和正解之间分差过小。这一点我也深深的感觉到它对某些人命运的作用。共价爷第一天写了第一题正解，第三题由于没时间只写了一个40分的暴力。然而别人第一题不会正解有95分，第三题可以写个84分的暴力。共价爷分固然比他们低，但是他就真的比这些人弱吗？并不是！他们并不会第一题正解少了5分，然而却因为第三题会一个不那么暴力的暴力，就多了整整44分，连用杜教筛优化成正解都只值16分。实际上无论是CF还是TC这些较为权威的国际网赛，都是尽量使得难题分值大，简单题分值小，而NOI似乎是反过来的，这也是共价爷为什么进不了队的原因之一。

怎么说我UR出的Yist什么的题目顿时被D啦，不过UR毕竟不是选拔性质，这样出后果并不大，而且那题做UR的A只能这样，做B又太水。

然而OI比赛，真正应该出成怎样，并不是说大家希望怎样就是对的，也没有什么依据说一定要难题分值大，简单题分值小，相反有时候做好每一件简单事，不是比做好一件大事情要重要吗？OI比赛真正的最佳形式，或许只有历史的行程能告诉我们答案。

总之NOI已经告一段落，无论结果如何，都应该当做上天给自己的礼物，无论是进队或是回去高考，前途都是广阔的，清华北大不必说，就算是北航北邮这些学校，也是许多学生心中遥不可及的目标，希望集训队员能向着国家队前进，没进队的也能通过高考考进心仪的学校。

完结撒花。