NOIp2020游记

## 前言 这是本蒟蒻第一次参加 NOIp，并且背负着 CSP-S 儒略日和函数调用两题集体爆炸，因此亚历山大。 ## Day 0 12/4 星期五。晚上有课，九点钟才到家。想要拿一道紫题练练手（Trie 树求最大异或和路径），结果样例过了，整出了满屏 RE…… 被我妈催着睡觉了，导致留了一题没调出来（wtcl），并且没有复习任何的算法。这是这一个礼拜看了看 Trie 和 KMP（然后 @LucasXu80 说不考字符串 ## Day 1 也就这一天，不需要 Day 1了。 来到考场，才发现上海的冬天居然这么冷。机房环境不错。 8：30，监考的解压出错了，晚了五分钟开始考试。这五分钟里自己码了一个 Dijkstra 觉得可能会有图论题。 先看 T1 排水系统。第一眼认为是最短路 / bfs，再看问题觉得可能会推式子。发现“无环”果断使用拓扑，码了 20 分钟，调了一会，也开了 long long。输样例发现全过了，自以为切掉了。经历了 CSP-s，自认为这次估分很正确。  ~~保守派的考场代码~~ T2 看到了字符相同那个部分分，自以为是推式子/排列组合，于是把 KMP 删掉，误入歧途。最后没推出来，直接随机数了。 接下来看 T4，发现部分分还蛮好拿，于是直接暴力 dfs 枚举起始位置，貌似是 $w^k$ 级别的算法。调了好久，终于过了前三个样例。 又回到 T3 拿 $n=2$ 的部分分，结果一个半小时打 dfs 硬生生没码出来，AFOed。 最后估分 100+0+0+30，第一次NOIp还行（毕竟比 CSP 高）。 中间还有几个小插曲： 1. 移球那题的数据范围放了一张样例解释的图（要不是这题浪费我青春我好歹 T2 能有分啊） 2. 还是这题，居然 checker 没人会编译…… 3. 快结束时（真的快结束）发现第一题的文件操作长这样： ```cpp freopen("water1.in","r",stdin); freopen("water1.out","w",stdout); ``` ## Day 2 昨天今天上你谷测试，发现好多人发帖求助 $m$ 是否有用，顿时懵了。好在出题人赛后申明保证入度为零的点一定是前 $m$ 个。于是理论上 $\Theta(n\log n)$ 的拓扑拿了九十，听说要高精。 T2 哈希和 KMP 似乎可以拿最多 $84$ 分，艹. T4 不知为何只有 15，挂了15，并且貌似没有输出 `-1` 的，哈哈哈。 今年就这样了，明年再说把！