Day 0

去中关新园报到，见到了zyy，cf，lbt等各路神犇。

去北大机房试机，感觉北大的机子比NOI的机子好用多了。

发现来北京，我需要适应热带沙漠气候和温带季风气候的快速转换，有点难受。

Day 1

上午去考试。先读一遍题面，感觉T1应该是比较好像但是特别繁琐的题，T3是很难的题，T2不知道。仔细地想了想每道题，发现T2转换几步之后，和我见过的另一道题思路是差不多的。而这个T2，只需要在那个题基础上套一个二分答案再套一个后缀自动机 + parent树上dfs + 差分数组。

于是我先写T2去了，实现总用时大概为1h。调调调，终于调过了样例。一交就WA。对拍对拍，调调调，发现我后缀自动机有个变量名写错了（这都能过样例的吗？？？），改了交上去，获得了60分的好成绩。

我开始卡这题的常数，加了些奇怪的剪枝，发现跑了8.8s（时限8s）。然后把后缀自动机的转移边用数组而不是map存储，直接过了？？？开始觉察到这题的毒瘤之处了。

接着开T1，推了好久把T1的树形dp转移式子写出来了。然后开始实现，总用时大概为1.5h。测样例，发现树形dp的状态都有问题了。开始一通狂改，把状态改对了，把转移式子改对了。重新实现，通过了题目所给的两个样例。提交发现WA成0分。

此时离比赛结束还剩15min。我赶快rush了一个T3的3分暴力和T1的8分暴力，发现T1仍然0分，而T3只是多了3分。

我的得分: 0 + 100 + 3
我的排名: rk29

下午听讲题，发现我T1，T2好像都是正解，T3这题需要用到带花树算法，无人AC。

在宾馆里跟南外的xy巨佬调试今天的T1,发现我和他的代码里面好像都犯了一个小错误，导致爆零。哎，IOI赛制都能挂分，还直接挂100分。

Day 2

上午去考试，看到T1,发现这不就是一个DFT的基本运用吗？过了45min，实现 + 调试完毕，一遍AC。

看到T2感觉很迷，先搞T3吧。发现这个题去掉数据结构的话是个树上高消的经典题。所以难道是链修改，维护动态树上高消dp？但是ddp我写不动，就想着再推点式子，找更妙的做法。推着推着，发现竟然可以直接把答案写出来？（使用了一点高中数列求通项常见技巧）。然后发现这题竟然是直接LCA + 前缀和就好了。

吸取昨天的教训，我并没有急着写正解，先提交了个20分暴力验证了一下我结论的正确性，再把正解实现了出来。此时比赛进行了2h，我已经获得了200分。

接着想T2，想着想着，我发现一个惊人的事实：考场竟然变空荡了！又想着想着，发现这题实际上是某道集训队作业的类似题，是k-正则二部图必有边的k染色这个结论的扩展。你只需要随便搞一个网络流，每次求二分图最大匹配即可AC。用余光环顾四周，发现又有几个位置空了出来。赶快实现这个算法，一遍AC！此时离比赛结束还有1个多小时。

过了一会，觉得没事干，提前离场了，此时似乎已经有20个人提前离场了。

本场得分：100 + 100 + 100
目前排名：rk18

下午听讲题，发现这个T3出题人的做法竟然没有我的做法复杂度优秀，感觉有点迷啊。

晚上我和lbt，hzk，xy等人在讨论明后两天有没有交互题，造计算机题之类的题，感觉要是真的出了我就掉出前20了。

Day 3

先看题，看到这场题有一道计算几何，一道奇怪的题（和某IMO题的操作完全一样）和一道交互题，感觉自己要凉了。

T2的题意如下：

给定圆环上的\(n\)个整数\(a_0, a_1, …, a_{n – 1}\)(\(n \ge 3\))。每次选取圆环上的数\(x\)，设与它相邻的两个数为\(y,z\)，那么把\((y, x, z)\)变成\((y + x, -x, z + x)\)，求把圆环上所有数变成非负数的最小操作次数（无法操作时输出-1）。

而那道IMO题是\(n = 5\),\(\sum_{i = 0}^{4} a_i > 0\)时，求证只要是不断对负数操作，总有一刻使得最终所有数全部变非负数。

先想T1，惊奇地发现这题并不是那种我不会的计算几何题。你只要找一个结论，然后很快就写完了。

我在45min左右就搞定了这题，然后开始轮番想T2和T3。挂机了大概2h，想出了T3的一个似乎是正解的东西，需要用到随机化。开始实现T3，交上去发现我的做法被卡成30了。再优化了一点常数，发现变成了55分。

奇怪地是，这份代码过了subtask 1,2,4，却没有过subtask 3。那好，我就多提交几遍，看来它只是rp不好，没有过subtask 3。

结果发现，这份代码有一定概率获得10分（subtask 1），一定概率获得30分（subtask 1,2），一定概率获得50分（subtask 1,2,3），一定概率获得55分（subtask 1,2,4）。

我暂时放弃了这道题的卡常，转而想T2。我先写了一个乱搞：每次找到环上最小的数，对它操作，然后如果过了很多次它还是没有变成全部非负，就输出-1。交上去竟然获得了30分。我猜了一下答案为-1的充要条件，交上去还是30分。我想着用数据结构维护这个贪心，发现根本维护不出来。

此时时间已经不够了，我做了一个决定：反复提交T3的代码，把这道题的最大提交次数用满，以获得75分(subtask 1,2,3,4)。

然而我的rp并没有那么好，它仍然只能获得55分的成绩。

本场得分：100 + 30 + 55
目前排名：rk15

下午听讲题，发觉T2，T3正解都是很妙的东西。晚上我被各路稳进前15的神犇奶了，再加上自己心里的紧张，直接为我明天的爆炸埋下伏笔。

Day 4

上午先看题，发现没有交互和提答。T1是一道计数题，T2是一道奇怪的数学题，T3是一道最优化题。

先想T1，发现这题并不难。在1h之内我通过了T1。

再想T2，自闭了快1h才找到这题的一个真算法（指数级别的暴力）。我实现了它，打了个表。大约15分钟它跑出来了\(n = 2,3,4,5,6,7,8,9,10\)的结果（本题基本上是只输入一个正整数\(n\)(\(n > 1\))的题）。把表交上去，它获得了35分(\(n \leq 10\))的暴力分

开始对着这\(9\)个数疯狂找规律，然而并没有找到通项公式，也没有找到递推公式。

又试图压状态推dp，然而并没有推出来一个多项式做法。

对着这题自闭了很久，我才开始想T3。先实现了这题的一个18分费用流暴力，过了subtask 1,2。再要看题的时候，发现：

网

站

挂

了

又过了大概15min，老师通知全场选手获得一定的加时。这时我才能重新看到题目。对着subtask 4想了一个线段树维护贪心，实现了一下，自己手测了几组数据，似乎能过。

4h 30min左右，老师通知本场比赛有可能变成OI赛制，建议大家对拍。我就开始拿我subtask 4的贪心和费用流做法对拍，结果直接WA了！

我瞬间变得不知所措了起来，疯狂想着这题的其它乱搞贪心。

既然我前面是从左往右贪心，我现在就从右往左贪！

改！改！改！这个线段树维护的东西要再加几个。改pushup函数，加一个询问函数！再在主函数里面写个贪心！

4h45min：subtask4的贪心搞定了，此时大样例下发，本场比赛变为OI赛制。

测试subtask4的样例，一遍通过！

4h48min：subtask 4的贪心可以推广！怎么用数据结构维护？算了别想了，快rush出来！

4h53min：实现完毕，通过小样例，WA了大样例！

4h55min：OJ感人地修好了！提交34分代码。

4h56min：34分到手！

4h57min：变量名打错了，改！测大样例，通过！

4h58min：提交71分代码。要是写挂了就完蛋了！

4h59min – 5h:返回了71分的结果。

总之这场打的真的是惊心动魄。然而，T3的71分挽回不了被卡T2的失误。本场排名为22名。

本场得分：100 + 35 + 71
最终排名：rk19

下午听讲题，发现T2的正解竟然是\(n \leq 10\)打表,\(n \ge 11\)输出0？我离T3的正解的确就差一个数据结构了，然而卡了很久的T2，也没有时间想了。

后记

如果我D1T1调出来了，如果我发现了D4T2的结论，如果我把D3T3卡过去了，我都会挤进前15。然而，我并不能祈求有这么好的运气。在我前面的人都是我所认识的大名鼎鼎的神仙，我完全不敢说：我比他们强。

现在我的最后一战是WC，不求翻进前15，只求我的结果配得上我的付出吧！

UPD: WC和CTS合并了，我可是能参加CTS的人，厉害吧
UPD: 最终CTS和NOI合并了。然后NOI没有太考好，以32名参加选拔选手里面的第18名结束了本赛季。