NOIP 游记

· · 个人记录

今年是我第一次参加 NOIP，在之前的 CSP 中取得了 400/205 的成绩，对于自己的表现都算满意。考试前老师对我们的要求是前两道题，所以整场考试我都是围绕着前两道题展开的。

DAY -1

老师说要在考场门前拍照，作为五年后的回忆。

DAY 1

按照约定的时间到了考场门口，和同学们一起拍了照，然后去各自的考场考试去了。（话说进门的时候有一种我们学校要进校打架的感觉）

考前日常打模板+猜题（还真让我猜对几道），果然考试这东西最紧张的时候永远是马上就要开始和马上就要结束的时候。

T1 结论很显然，用最小序比较最大序，用桶能将 sort 排序的 O(n^{2}\log m) 能优化到 O(26n)，总时间复杂度是 O(n^{2})，加上 O_{2} 直接快到飞起。

T2 要求根据操作构造原序列。看到 n 和 m 范围感人，一开始将视线投向了通过有理有据的推断和不断的重复操作将原序列还原出来，但是被样例卡掉了。接着又想到了建图，但发现建图为了表示出赋值的关系需要建单向边，但赋值的顺序直接影响每个变量最后的取值，而在图上无法展现这一点，于是选到了并查集。并查集的相等与取反在练习并查集的时候练了不下百次，板子很快就打完了，但最后一个样例莫名一场返回，于是一直重构代码，最后终于调出一版满意的代码。

写完两题时间只剩 1h，抓紧码后两题。

T3 看完不会，将所有结果一定的序列特判，剩下的输出随机数。

T4 显然 dp，但考场上完全没有思路，于是揪着一个特殊性质写了一个简短的骗分。

考场出来发现大家 T2 用的是 Tarjan，心有些小慌，还有就是对后两道题骗分的不信任。估分 100+100+5+0=205。（话说我 NOIP 考得怎么和 CSP-S 一样）

UPDATE AT 11/29

其实早就知道自己的成绩了，鸽了好久（应该也没有人等我），总之真实成绩与估分一样，具体的得分也相同，非常开心能拿到这样的成绩，下次更要继续加油。