NOIP2021游记

· · 个人记录

坐标BJ，考场北师大实验（就是这学校有个cspj组抄程序的导致扣省队名额……然而事实比这还糟糕……）

10.19

晚上八点半就睡觉了，可能是十几年来最早的一回

10.20

8:05 进考场，发现原本就非常小的桌子上摆满了临时的隔板，稍微碰一下就倒了，桌面极其拥挤，无法同时摆下草稿纸和键盘……

开电脑，打开vscode，发现c++拓展包无法下载……

8:20 开题，T1应该就是什么玄学筛一下然后打个表，看T2，没太看懂，但是应该是个dp。T3，模拟退火应该能骗不少分，再看T4，第一感觉就是儒略日秽土转生，也没太看懂，但是貌似有不少暴力分，肯定得留时间做一下。

8:30 开始写T1，怕朴素埃氏筛被卡，所以就想了个常数更小的筛法，具体来说就是先筛掉 [7\times10^6,8\times10^6)，再筛 [n\times10^6+7\times10^5,n\times10^6+8\times10^5)，之后是 [n\times10^5+7\times10^4,n\times10^5+8\times10^4)，以此类推。考完之后发现自己是真的有病，对于一个数直接判断末尾是否为 7，以及除以 10 之后的数里面是否有 7 就行了，严格 O(n)。

当时想的一个方法是在筛掉的区间两端赋 1，最后算前缀异或和，但是有一个问题是 [7.7e6,7.8e6) 这样的区间会重复标 1，然后就加了一堆判断。写了一会，发现样例 3 挂了……想了一下没想出来，于是决定上厕所。一出考场门就想明白了，我不是闲的么，筛的时候我干嘛赋 1，赋一个权值不就解决了。

因为上次csp的事情，现在上厕所要一个一个排队，进了厕所发现还要被人监视有没有做可能有关作弊的事情，上完了厕所还要记名字、考场和时间……（cheater我衷心问候你家人）

还有，由于疫情的缘故，监考老师会一直要求你戴口罩，但是我的位置不管离窗户还是门都是最远的，闷得要死，戴口罩完全无法好好做题……最终我发现了诀窍，只要在监考老师接近的时候拿起杯子喝水，她就不会管你了（逃

回到考场，稍微改了改就过大样例了，改成 freopen，结果…… RE？第一感觉就是取消流同步的 cin 出了问题，换成 cstdio，终于过了，一看时间，9:34……

就这么一道破签到题我花了一个小时

9:35 又看了一遍T2，差不多看懂了，但是只会 m\le12 的状压，于是决定先写T3的退火。

10:45 弄好了退火，调了一会参数发现始终只能过前两个样例，于是就放弃后面的样例回去做T2了。

10:50 T2看明白了，有一个初步的想法是约定 a_i 单调不降，但是发现需要一个维度开成模数的范围来去重，显然不行。于是又去了一次厕所，然而并没有什么收获，回到考场决定先写50分状压。

11:35 T2暴力状压的50分的搞好了，尝试后面的部分分。先想了一会 k=1，没思路，又发现后面 n=5,m=50 的点貌似暴搜加点优化就能过，写了一会，发现极其恶心不想写了。由于还有个T4的暴力没打，果断决定放弃T2部分分搞T4。

11:55 开T4，读了三遍题，差不多明白了，感觉正解和线段树有很大关系，但由于只剩一个小时所以果断打暴力放弃后面的分。

12:50 第一个样例过了，第二个样例错了一个点，于是先把当前代码交了上去，然后手推，发现是走 3 边并吃子之后忘标记能走到了，改了一下，对了，交上去，还剩五分钟，可以说是相当极限了。

12:56 预估得分 100+50+48+32=230，打开emacs玩俄罗斯方块。

13:00 考完了，上厕所，发现有人崩溃了在厕所里面哭，周围围了一圈人安慰他……同学问我觉得T1难度如何， 我特意回答说挺难的……

下午去看牙，回家交洛谷测，T3退火 9\sim12 炸了，但是 16\sim17 出乎意料过了，比预估少了 4 分；T4 居然得了 44，9\sim11 也过了，民间数据得分 100+50+40+44=234，居然比考场估分高，希望CCF不要卡我。

总体来说考的还行吧，T1有点失误浪费了比较久的时间，导致T2完全没时间想正解，回去的路上听同学讲解法发现和我最开始想的差不多，但是他对进位的处理是我完全没想到的，orz