NOIP2023 游记

日期:
標籤: journal

人生中第一次参加 NOIP。

2023-11-17

NOIP 前一天。上午教练发了一套模拟赛,说是选做,所以当然没做。但是好像大家都在做,而且爆杀了???感觉自己太颓废了。上午主要是在打板子,打了 kmp,manacher,高斯消元和最大流。然后在写最大流的时候突然发现自己用了不知道多久的最大流板子是错的, 见 icpc-snippet 的 commit,而且用这个板子还过了很多题???主要原因在于模拟赛写的题涉及到 flow 的大部分是二分图匹配,二分图匹配流量最大是 1,然后这个板子莫名其妙就对了?

下午 VP 了一场 ARC,感觉很没有竞技状态啊,一边水一边打比赛,C 到最后十几分钟突然会了,然后没写出来。我很喜欢 AtCoder,比赛时间不长,题面很形式化,而且 kenkoooo 的 AtCoder Problems 这个网站很给人成就感。

本来打算再打一下 Tarjan 和 Treap 的,但是回家后 Hypixel 太好玩了,和 FOE 一起赢了一把双排起床,所以就没有打板子。

晚上睡觉睡得不太好,好久都没睡着。

2023-11-18

正赛

考前还是看了一眼 Tarjan,还是不懂怎么求割点的,但是感觉考到也不会用。

感觉今年七中机子很怪,鼠标移速非常快,而且字体渲染非常奇怪,不过我用虚拟机,虚拟机下字体渲染还是正常的。打开虚拟机之后,Nautilus 没法在共享文件夹内操作,不知道是为什么。索性就在建了一个 workspace 文件夹,不在共享文件夹内写代码了。不过现在想想风险还是挺大的,万一电脑死机了,虚拟机是要被还原的。

题目输入带测试点编号好评。

T1 挺简单的,二十分钟左右就调出来了,感觉时间挺充裕。

然后开 T2,感觉不好做。画了画感觉可以用扩展域并查集做,每个变量的每个版本作为一个并查集的节点,然后维护各个变量的关系。写了大概四五十分钟,过了第一个样例,然而第二个样例就挂掉了。手玩了一下感觉自己答案挺对啊,查了十多分钟才发现自己样例给出的语句少看了两行。结果就是发现自己做法假了,然后又打补丁,发现还是过不了样例。决定写个对拍找小的错误数据。造数据时不知道怎么保证答案一定存在,但是感觉就是一定有解的样子。最后发现是自环的时候挂了,改对后过大样例,开始对拍,拍了近三万组没问题,稳了。

接下来是 T3 和 T4,感觉都不太会,但是部分分挺充裕,所以就全部打暴力了。T3 令 f(i,j)f(i, j) 表示让 xix_{i}yjy_{j} 是否可行,然后可以做到 O(n2)O(n^2),但是好像很难优化。

T4 的话令 f(i,j)f(i, j) 表示第 ii 天结尾打卡 jj 天的最大能量值,可以 O((n+m)k)O((n+m)k)。在写 T4 暴力时,过不了第二个样例,而且样例也非常不友好,n 和 m 是 100,完全没法调试。查了半天才发现自己后缀加全部加到了一个位置上。然后注意到对 dp 数组的操作只有后缀加,全局平移,区间求最值,然后改成用线段树维护这个,对于区间平移就下标平移一下,复杂度 O[(n+m)log(n+k)]O[(n+m)\log(n+k)],最后又把特殊性质 B 写了。

估分 100+100+35+64=299。好像这局大众分都有 250+ 啊。今年从初赛到 NOIP 整体都比去年简单。

哎,迷茫。

打 ABC329,人生中打得最好的一次,29:11 写完 A-F,不过题目确实简单。

晚上云斗出了成绩,发现给我 T4 算的 0 分,检查出来我 std::numeric_limits#include <limits>,GCC 9.3 特性。不慌。

感觉省选挺没戏啊,好多 300+ 的。

2023-11-24

299。