NOI2022 游记

挂 18pts 送走 Au,rk65 Ag。

现在来写,感觉很多有意义的细节已经忘记的差不多了,只能记得一个大概的框架了,所以游记总是看起来干巴巴的。由于我又没有赛时写游记的习惯,看来以后得先记录一点有意义的事情了。

以 8.23 为 Day 1。

Day -10(8.12)

突然听说要提前 7 天到苏州,吓了一跳,赶忙飞去上海然后高铁到昆山。没住在 CCF 建议的酒店,说找一个安静点的地方。熟悉了一下环境,结果碰上了成外的(

和 CSYZ 一起训练,他们明天才来,所以模拟赛没来,于是可以光明正大的颓,结果被教练评价为“效率怎么这么低下啊”。

条件还行,手机电脑被收后,晚上看点奇怪的电视剧,不知不觉就睡着了。

Day -9(8.13)- Day -3(8.19)

CSYZ 的来了,模拟赛也来了(悲

天天在酒店里颓,但是还是被强制做模拟赛。结果几场模拟赛一次排名比一次低,是不是 NOI 就要垫底了 /ll

地方特别偏,想找一点能吃的菜简直不太可能,就连外卖的 5km 以内都没有几家,一周显然就都吃遍了,然后就没得吃了(

8.14 晚上 AGC 直接自闭,啥题不会,最后在 170 min 的时候终于过了 A /kk,不过排名没变化,还是掉大分。第二天发现自己的 B 和正解一模一样,不知道为什么赛时没过样例呢?当时又把 B 的代码删了,更不知道哪里错了,于是又重码了一遍赛时写的,就过了 /fn

8.16 晚上 CF Div1,A 一直猜贪心,WA 了两发才发现哪里没对,结果是一个 sb DP,做了半个小时。B 没想到有一个唯一分解(其实推式子的过程中证明到了,但是没写)用了一个奇奇怪怪的东西,写了半个小时多,WA 了两发,终于过了。C 一个一眼题,直接维护所有因数的答案即可,突然感觉过不去,把因数换为质因数就好了,又写了半个小时,罚时一车,不过还是上分了。

Day -2(8.20)

进校力!(不过教练因为没报名字上去,进不了 /kk,比较离谱)

发现是一个 nb 学校,感觉非常宽敞,所有建筑都是西式风格的,在我们那地很少见。被分到了一个两人间的宿舍,居然没有上下铺,一人一弹簧床、一个书桌,独立洗手间、洗漱台,感觉是星级酒店而不是一个学校的宿舍欸。不过听说到这里的学费,实在是震惊到了,但是这学费也值啊,天天住宾馆,实在是条件不错 /se

由于不认识几个人,跟着多头去逛了一圈,在签名墙上写下了自己的 id(诶话说这么大个签名墙,写个 id 真有人能看到吗),然后就溜回寝室颓了。

午饭也是全自助,挺好吃的 /se

一直颓颓颓,无事可干捏。由于我们教练进不来 /ll,只好像探监一样把我们叫过去,问一下近期的情况,自然是应付一下,不过确实也不知道自己状态到底如何,只好开摆。

晚上颓。

Day -1(8.21)

早上去领胸牌,结果要去 4 个地方按顺序排队,第二个位置特别慢,导致那个位置的人特别多,其他位置几乎人都没有,让我清楚的认识到了水桶效应(一开始差点由于人多直接排第二个位置了)。我不清楚为啥不在那里多安排几个人呢?看到几个志愿者议论了半天,结果也没人去帮忙。另外为什么不集中到一个地方直接同意统一领呢?表示问号。不过反正排队也是颓,也没太在意。

拿到徽章后和多头换了一个,又去领了背包,感觉良好。遇到了 CSYZ 的几个,换了徽章,然后回寝室了。

据说 ZJ 和 CQ 都在 D4,晚上和 RuSun 去面了 dX 和 feecle6418,结果都只有 1 个徽章了 /kk,不过我们两个还是都给他们了()

晚上斗地主 / 看别人斗地主。

Day 0(8.22)

下午要笔试了,早上只好开始复习,不过看不进去,因为这个笔试有 whk 的感觉。过了几遍感觉差不多就行了,然后开始颓。

下午笔试,先发了一个去年 NOIp 的题目,就写了一下练练手,结果发现 T3 还是不会,T4 还是只会暴力。如果叫我现在去考去年的 NOIp,能不能考到我当时的分数还是问题呢 /kk。随便写了 T1 和 T2,幸运的是没怎么调试就对了,本想开始写 T3 的退火,结果发现 14:58 了,遂弃。

笔试竟然是内网提交答案,和我想象的方式(写成程序提交)不太像,不过这样就不会题号错误,还是不错。结果第五个就不太确定(记不到题目是什么了),中间要好一些,然后 46 47 连着两个全选,47 能不能登陆系统把我给不会了,但是转念一想,不是不能碰键盘吗?不碰键盘怎么登陆?差点就变成 bot 了,哈哈。

据说以前考完就出成绩了,不过今年的系统考完后 15:31 就关了。那多久出成绩呢?表示问号。

本想接着写 NOIp T3 的,但是发现旁边的人走了一大半,于是果断弃掉跑路。

Day 1(8.23)

早上本身没改原来 7:00 的闹钟,但是同宿舍 CDQZ 的 6:40 就起来了,于是我也起来了(

先吃饭,后洗漱,虽然有些奇怪,但是教练要求的,不管了。差不多 7:40 进去的,结果只带了一个士力架,感觉亏大了 /ll。不过还发了一些吃的,于是进场了。

8:00 准时开题,看到 T1 是一个 sb 摩尔投票,因为当时做 CF 好像做到一个,所以记忆比较深刻。感觉 T1 简单,一会来写,又看 T2。T2 的题目很简洁,但是感觉性质很不优美,开始看成了操作一是每次恰好减少两个,发现完全不可做。过了一会发现是至少减少两个,然后发现还是不可做(,于是去看 T3。T3 “这是一道交互题”和 6 页的题面,已经难懂的定义让人想起了 lxl 欸,不过好像是 zx 出的(。看了一圈,大概半个小时才看懂题,发现连 $O(n ^ 2)-O(1)$ 都不会,只会一个链的猫树分治 10pts。不过 T3 一脸不可做,也没人写更多分吧(

回过头去写 T1,发现需要维护原序列以及摩尔投票的结果,开始觉得只需要线段树合并就可以了,于是写了,发现没法删除最后一个,想了半天发现可以平衡树合并维护序列(我怎么没想到启发式呢?),不需要线段树合并,差点把线段树合并删了,不过还是忍住了放在 backup。果然过了一会写完平衡树合并后才发现没法判断一个数是否真的是绝对众数,于是又想起了线段树(,然后复制过来,前前后后 1.5h 过去了,写了 200 行的代码总算过了大样例。这常数能过就离谱了,不过我当时没想到更好的办法,于是跳了。

懒得写对拍,9:45 开 T2,我不相信 3h 拿不下 T2,毕竟每年 D1 队线都是 200+。但赛后看来我的思路就是错的,因为我一直想找到一个比较优美的结论来表示。但事实是这个题需要 DP 刻画合法性。赛时想到了 DP,但是发现每个区间的操作次数复杂度上天,于是弃掉了。其实当时如果认真想还是可做的,只不过我被“有一个优美的结论”的思维禁锢住了,没有仔细思考。

这样前前后后到了 11:40,我连 $k = 0, l_i = r_i$ 都不会做,心里有点慌了,于是写了爆搜 15pts 跳 T3。T3 下发了 grader.o 和 checker.o 是我第一次见识,还是挺 nb 的。能用就是了,主要是没有 checker 源码,不知道为啥错,猫树分治都调了半个多小时,总算调出来了。想了想暴力怎么写,结果搞了很久,想了多个算法,全部假了。

回过头来看 T2,还是一点不会。遂弃掉,慢悠悠的检查了三个题能不能编译通过,于是罚坐 15min,结束了。

出来听说估分 125pts 的人很多,但是 125pts 以上的比较少,只要不挂分,应该还是可以翻盘的。不过盘是什么?我也不知道。

吃了饭睡了午觉过去查成绩,发现没挂,$100 + 15 + 10 = 125$。CSYZ 的似乎都有多多少少的挂分,惨惨。据说队线在 130-140之间,心态稳健,多头 T2 直接场切,我直接 orz。

下午和 XJ 的学生聊,他 D1 130(不过好像 D2 爆炸了,Ag 走人了,惨),他把题看成了操作区间长度 $\geq 2$,这个比原问题 $\geq 3$ 可做一些,但是他写了很久,直到最后一个小时才发现,然后就寄了。不过至少还是会并能写完 $k = 0, l_i = r_i$ 的部分。他讲了一遍 T3 的暴力,可我还是没怎么听懂(

晚上讲课大概听懂了 T2,发现是一个神秘 DP 套 DP,瞎搜一下可达的状态救就可以了,T3 神仙数据结构,暴力都好阴间 /kk。回去斗地主。

Day 2(8.24)

说好的社会活动呢?

好像有一个什么猜谜游戏,不过听说比较专业,就没参加。上午无事可干,想看几道题,结果 ABC 都不会(,心态爆炸,于是不看了,开始颓。

下午开幕式,印象最深的当属 dzd 的讲话和无人机表演。无人机的背景音乐是 AW 的 Hello World,有点寓意阿。

晚上颓。

Day 3(8.25)

其实应该是 D2(

8:00 开题,一眼觉得 T2 是 Itst 出的(赛后发现他出的是 D2T3),部分分比较良心,争取多拿点(总所周知 D2T2 不可做)。T1 树哈希,题面明摆着不会特意卡,那随便搞搞,感觉比较简单。T3 神仙题,显然不会,但不知道爆搜多少分。

T1 想了一会可以直接暴力枚举哈希值不同的如何匹配,复杂度上界是 $O(k! \times n)$,看样子可以过,于是直接开写,细节还行,差不多 9:30 过大样例,然后随便造了几组 Yes 的数据(似乎不好写对拍),发现是对的,于是跑路。

9:45 开 T2,先做 A 发现有一个显然的 $O(n ^ 3)$ DP,想了一想转移方程可以使用单调队列优化到 $O(n ^ 2)$(自始至终没有想过贪心 /kk),先不忙写,又开 B 性质,盲猜一下没填的是不降的,于是又可以 $O(n ^ 2)$ DP,想了一下会证明了,感觉 C 也是这么做的。大概 10:20 开始写,单调队列比较难写,主要是不断平移比较麻烦(赛后发现好像可以记录 0 的个数而不是 1 的个数就不需要平移了 /jy),写了半个多小时才过样例。B 好写一些,发现这个过不了 C,于是摆,然后又胡了个爆搜,应该 56 pts。

11:45 左右开 T3,$k = 3$ 容易贪心选 2 即可,很好做;$k = 4$ 不太会,又写了个爆搜,想尽奇奇怪怪的方法优化,但是 $n = 50$ 根本过不了,于是期望 27 pts 跑路。感觉这么多分 + D1 的 125 应该够队线了吧,就没有继续想其他部分分了(伏笔)。简单的检查了一下就结束了。

一出来就听到有人会 T2,难道 D2T2 比 D1T2 简单?表示问号。不过出来就听到 CSYZ 的教练给我们说马上回去,不是还有两天吗?一查,苏州一个无症状感染者,没必要这么紧张呗。不过还是回去把东西收好了。

下午 2:30 就看到一车人去查分,也去一看,$100 + 48 + 17 = 165$,挂了 18 pts。

先看 T2,发现是暴力挂了 8pts,反倒是 A、B 两个难写的性质都对了。想起了当时我需要在一段区间的右端点判断一段区间的最小值是否是给定的时候,我为了运行效率,把一个右端点的限制按照左端点排序,然后指针扫过去。结果排序的时候把 $n$ 写成 $m$ 了 /kk,然后暴力挂了一半。当时想过要不要这样,因为数据不好检查写对没有,结果一想应该没问题,就略过了,然后就挂了 /ll

然后看 T3,发现 $k = 3$ 的点全挂了,10pts,仔细一看,多测不清空,爆零两行泪。怎么过的 $k = 3$ 的大样例呢?小编也觉得很惊讶,但事实就是这样。

出来几乎没有讨论就出校了,路上和教练讨论了一会。一路上有各种奇奇怪怪的队线,不知道该听谁的。

似乎确实是一个不完整的 NOI 欸。

Day 4(8.26)

出总分和排名了,$100 + 100 + 15 + 10 + 100 + 48 + 17 + 0 = 390$,rk65 Ag。

回收伏笔,确实当时估计的 $100 + 125 + 183 = 408$ 也可以进队的,不过挂分了。不过确实实力不够呗,这直接导致容错的区间太小了,我一旦任何一个地方挂了,都不可能进队。一旦多会 20pts,这样的话,挂一点分还是可接受的。现在确实一点不能挂,但谁能保证总计 10h 的 NOI 一分不挂呢?显然是一件难事啊。

没进队有遗憾啊,不然我写这游记的时候心情也就完全不一样了,就可能是 feecle6418 和 dottle 的心情了。不过好像还是可以参加 CTT/se

接下来的一年,除需要提升实力外,这些挂分我们需要一些总结,比如将可能挂分的方式写在代码里,过完样例后逐一检查。这些问题可能是易避免的,也有可能是难发现的。检查出样例无法检查到的错误可能也是实力的一部分吧!

来年再战!