NOIp2021 游记

可还行吧。

以考试当天(2021-11-20)为 Day 0。

Day -?

记录两次机房的对话。


我:”又在卷网络流!怎么可能考得到嘛。“

机房大佬:”CSP-S 才考了,肯定是在考纲范围内啊。已经是废物了,还不快复习网络流。”

我(表示不信):“怎么可能?才考了,怎么可能还考得到?”


我:“模拟退火都要学!啥分都骗不到,估计和暴力差不多。”

机房大佬:“骗分的东西,还是要多学的。”

我:“骗分的东西,考试的时候又用不到,还学这么高深的算法。这么久都没考了,不可能考啊”。


事实证明,还是不能随便押题啊。模拟退火就考到了……

考前和省外的联测,天天被吊打,怎么办啊……

已经停了 whk 专心搞竞赛了,但是感觉没有很大的提升,倒是身旁的大佬多了起来。不知道更卷的地方是什么样呢,反正已经比我强多了。

Day -1

本身根据机房习俗,应该是 考前 generals 大赛,但是由于之前机房发生过事故(具体什么就略去了),所以不敢参加。

倒是解决了一个遗留问题:(在 CSP-S 当天早上写的 Treap 60 pts 那个)在 NOIP 前一天解决了!简直是 rp ++!

又 A 了一个黑题(CF 的虚高黑题),考前心态还是挺不错的。

晚上同寝室的还比较照顾我,本身应该说话到 11:00 的,很早(10:30 之前)就都睡了。

我却翻来覆去,一直睡不着,不知道明天如果考挂了,自己的前途将会是如何。

但不管怎样,考试还是得来临,我迷迷糊糊之中还是睡着了。

Day 0

早上 8:00 到考场,发现已经挤满了人(本身考点人就不多,基本都在外面)。

赶忙进去,开了虚拟机,开始敲模板,感觉键盘比较拙劣,平均 3 个字符就有一个吃掉了,只要集中在 s,j,( 这些字符,很难打。( 最烦,我又开了 -Wall 的,很容易打掉括号。

几分钟码完了模板,开始呆坐。只能看到标题,也就只是复制了几遍模板,放在那里,命好名,啥也不能干了。

8:22 发了密码,赶忙翻到 T1,但是刚翻到老师就说不准动键盘,于是只能盯着 T1 看。但是旁边的人一直在动鼠标,老师也没有管(大草

8:30:正式开始!

看了遍题,没什么思路(其实是没认真看)。

感觉第一题是一个签到的题目,虽然是 $10^7$,埃式筛法是 $O(n\ln n)$,但是不是每一个数都要筛一遍,所以赶忙码了一个,测速只需要 0.3s,所以 20 min 就做完了签到题。

8:50 左右开第二题。第二题似乎是一个神仙 DP,可以顺序枚举每一个数被取的次数,主要是进位十分烦人。考虑可以用一个状态存下来向前的进位,发现最多只是 $n$ 的级别。

中间算错了几次复杂度,一直算的都是 $O(n^3m)$(因为状态个数就是 $O(n^3m)$),码了一半,发现还需要一个 $n$ 枚举每一个数枚举的次数,复杂度升到 $O(n^4m)$,计算器一算,$3\times10^8$,但一想到有很多状态不存在,直接跳过就好,所以不太关心。

写了 25min 左右,差不多 9:40,调还算顺利,调了一会就出来了,给的样例又不是大样例(觉得是大样例的站出来!),没感觉到什么就对了。

9:55 左右看第三题,感觉是一个神仙题,虽然是方差知道怎么求,$=nS2-S1^2$,但是啥性质都推不出来了。第四题题面又臭又长,但是又不得不看,有些搞心态。

又回来推第三题,想了半个小时才发现可以差分,就是邻项交换。似乎可以暴力枚举的,手写了一个暴力观察性质。

发现了应该单谷,但是想了几个贪心都是错的,不知道怎么回事。后来才发现贪心就是错的。

这时已经 11:30 了,只好放弃 T3,马上去写 T4,发现只有直行的可以维护每一行列的覆盖情况,发现可以倒序变成加点的形式。

但是似乎极其难写,只写了个暴力,30 min 写完跑路。

又倒过来看 T3,已经 12:10 了,感觉可以区间 DP 的样子,但是方差的公式实在用差分的形式太难变形了,只好放弃。

12:30 的时候,突然灵光一闪:我的贪心答案和正确答案差不了多少,可不可以通过随机交换的方式来得到更优解呢?

于是我想到了模拟退火(大草

从来没写过模拟退火,这次在 NOIP 考场上算是第一次写。

我看过书上的解释,但是当时没有给代码,心里还是没底的。

不过模拟退火还好写,10 min 就写完了。

不过死活过不了大样例,答案比最开始的贪心答案还大一倍(这里说一说我的神奇模拟退火(赛后知晓):我中间有判断,如果 time>0.9 就直接退出;但是我有没有全局变量来维护走过的最佳答案),不免极慌。

一阵魔改之后,过掉了样例 3,但样例 4 实在是过不了了,此时已经 12:55 了。

我不知道应该怎样改才是合适的,但是最后时分,我将多次退火改为了一次退火,精度调的极高:for (double t = 1e9; t > 1e-7; t *= 0.9999997),没时间测样例的,我赶忙将文件看了一下,没有多余输出,都有 freopen

检查完后,看到 12:59:30 了,本身想测 T3 大样例的,也只好罢休了。

考试结束,不允许再动键盘鼠标了,迅速离开。

寂寞的走出考场,交流了一下,发现许多人没有写出 T2,但是都写出了 T3 的模拟退火。

哎,要是我学了模拟退火该多好啊!

但是,过去的已经过去了。

机房大佬说,模拟退火应该有 $40\sim56pts$,但是我的假的模拟退火,差不多有个 $16pts$ 差不多了。

仔细算了一下:$100+100+[0\sim 20]+[32\sim48]=[232\sim268]$ 的成绩了吧。

看到去年的一等奖线都是 100+ 不少,想到万一 T2 挂了肯定就上不了一等奖线了。

但是估计在全省大概就是 $rk25\sim40$ 吧,可能又是省队三倍线上不了了吧。

不管了,休息了两天,又要回归 whk 了。

Day 1

还没时间写,不过已经有时间看别人的博客了。

发现大家似乎都是 $200pts$ 左右吧,心态稳了一些。

代码发下来了,但是不敢在 Luogu 上测,就连 xtl 都不敢看。

又浑浑噩噩过了一天。

Day 2

还是看到了 xtl 的成绩,又到 Luogu 上测了一下。

发现 T2 挂了 $15 pts$,T4 由于多组询问全部都清空,直接导致只有 $24 pts$。

不过可喜可贺的是,我的模拟退火竟然写对了,再加上推出了差分单谷的性质,直接得到了 88 pts!

Luogu 评测:$100+85+88+24=297$,xtl $301$。据说可以进 $rk15$。

等 CCF 的成绩吧。

总结

这次考试,主要是策略相对正确,但是有很多细节地方应该注意,比如神仙挂分:T2 现在都不知道怎么挂的(求助,14-16 全 WA),T4 全部清空导致时间复杂度卡满了,只有 $24 pts$。

其实可以 $100+100+88+44=332$ 的,似乎轻松进 $rk10$ 了。

过去的已经过去了,还是向下一站进发吧!

2022 联合省选加油!

upd on 2021-11-29: CCF T3 送了我 96 pts,看到了一些希望。

实际分数:$100+85+96+24=305$。

(另外,看到了 T2 的错误了,我在判断条件的时候,判断本位的时候写错了。