NOIP2024游记

· · 生活·游记

进考场后静坐 40 min，要开始了发现别人都有草稿纸我怎么没有，问监考老师，老师说你是不是晚来的？？？

开 T1，发现怎么不会做，大胆猜测可以直接贪（不然我就彻底不会了，总不能 T1 放优化 dp 吧），于是写了一下，直接过样例了然后就再也没改过也没拍过，至今不知道是不是正确的。T2 看了一眼发现是简单题，写写改改就过了，看了眼数据范围发现既没有 m=0 又没有什么奇奇怪怪的边界，良心出题人。

大概过了 1h，开 T3，想了 15min 没有任何头猪，感觉不可做啊！急了，看 T4，这个形式很优美啊，一眼可做于是开始磕，想了一会以为可以分治，于是简单写了写，大概 45min 发现假了，复杂度就是错的，k=1 就会卡成 n^2。很急啊，草稿纸上画了下，发现分治后如果预处理出每个分治区间内选长度为 k 连续段的答案，那么复杂度就是正确的，刚想写发现不对啊这不就是线段树？欸还真没考离线算法。

最开始写的是 O(n\log^2 n)，写完之后发现一个二分是没用的，可以直接丢掉，就变成了 O(n\log n)，但是时间从 5.5 s\rightarrow 4.5s，我直接一个问号。卡常，最后卡进了 3.5 s，只能先放着了。

还剩 1.5h，但 T3 还是没有头猪。想了好久才转化完题意，但没时间了，k\le 2 打了下播（半小时前还想打两个特殊性质的，结果打完 k\le 2 之后忘了）。

最后改成 -std=c++14 -O2 把所有程序都测了一遍，哦草我 T4 怎么卡常的时候没开 O2，浪费 30min。

预计得分 [0,100]+[0,100]+[0,40]+[0,100]=[0,340]。赛后其实很快就会 T3 了，不过就算考场上会了想必也是打不完的。

哎希望别挂，不是很有把握（T1,2 都没拍）。

反向挂了 4 分。