NOIP2020 游记
希望能带来好运!
2026.11.15 upd:优化了一下排版,也小改了一些内容。
CSP2020 翻过一次车了,预感 NOIP2020 不会翻车。
Day 0
这次撑到了政治课结束,16:20 才从校门口溜出来。18:00 左右抵达 “速 8 酒店”,这次车速好快啊。
辣鸡酒店,为什么给我定的是一个双人间,还有一个床留着给寂寞睡吗?
然后出去打印了一些证件。
顺便吃了个饭。
老板:饭店里没有饭了,只有意大利面了。
我:???
我:那就意大利面吧。
买了一杯名叫 “陌上花开” 的奶茶,感到恐慌。
回到酒店的时候已经快 20:00 了。
然后颓 LOL,喔唷,赛季结算了?郊区的「铂金 3」还行,领到了一个卢仙的皮肤,好帅!然后一直颓,颓到了 22:00 左右。
看了一会《算法竞赛进阶指南》,然后就去睡觉了。这次睡的好早啊,23:30 左右就睡了。
祝大家 NOIP2020 rp++!!!
Day 1
woc,为什么睡到 7:00 才起床,我的叫醒服务呢?辣鸡酒店。
又双叒叕在时代中学考试。
由于时代中学工作人员效率太高了(迫真),8:36 才进考场,比赛也延时了 6min。
开了一手 T1,好像没什么难度的样子,直接 topsort 传递一下就行了。
但是好像认真卡的话要爆 long long,阿算了不管了,直接码上。
今天手感火热,大概 8:50 就写完了,测了一下大样例,嗯,很稳。
接着开 T2,看起来非常可做的亚子。
枚举 T = (AB),那这样相当于枚举一个前缀。再枚举一个 i,这时候 C 是确定的。
预处理前后缀的奇数字符出现次数,然后用树状数组维护一下 T 里有多少个 A 满足 F(A) \leq F(C),然后就可以直接统计了。
这样做的话时间复杂度是一个调和级数的形式,单组数据应该是 \mathcal{O}(n \log n + n \log |\sum|) 的。
嘶,好像很悬的亚子,姑且就先码上吧,大概 9:11 就写完了,测了一下大样例,感觉很棒。
吸取了 julian 的教训,打了个对拍,把 T1T2 都拍了一下。嗯,真的很稳。
这时候已经 9:37 了,稍微看了看 T3T4 的题面,T3 好像非常棘手的样子,就先开了 T4。
草,怎么这么难,想了一会儿,实在是想不到怎么从整体分析。
看了看部分分,只会写 1 \sim 8 这些测试点了。于是码码码,大概 10:30 才写完,手玩了几组数据,感觉很稳,就去看 T3。
T3 好像有点麻烦,但是应该还是可以做的。
可以一个颜色一个颜色来考虑,强制一下第 i 根柱子的颜色为 i。
对于第 j 根柱子,可以用 \mathcal{O}(m) 的次数把第 j 根柱子里面所有颜色为 i 的球都移动到第 j 个柱子的最上方。
然后再将所有颜色为 i 的球统一移动到一根柱子上。
这样做的话操作数大概是 \mathcal{O}(n^2m),由于借用了第 n + 1 根柱子做手脚,可能还要乘上一个 2 的常数。
判掉一些不合法的操作,也许不会到达复杂度上界。
P.S. 事后计算了一下,该算法的严格操作量不超过 m(n - 1)(n + 4)。
考场思路非常混乱,也想不出什么比较强的高论,且打且看吧。有好多代码实现上的细节,一直码一直码,中途上了好几次厕所,终于是在 12:27 的时候过掉了大样例,操作数才 20w 多一点点。手玩了好多组数据,正确性应该是没什么问题。按 CCF 的数据强度,信仰告诉我可以过。
玩了一会儿扫雷,然后就到了 13:06 分,出了考场。
理想得分:100 + 100 + 100 + 40 = 340。喔唷,看起来非常牛逼。与巨佬们交流了一下,感觉是在大众分之上的,很棒。
接着大家一起去聚餐,没错还是那家“农家小乐”。
接着就是坐车回长乐了。回到家,拿到了全省的代码。
woc,我 T3 忘记交上去了?!真气人,怎么会在这种时候掉链子。
测了一下 T1、T2、T4。
不会吧不会吧 T1 还真的有人会去卡 long long 阿,于是成功被卡掉 10 分,希望 CCF 能够做个人。
ohhhhhh T2 卡过去了,真不错。据说有 \mathcal{O}(n) 的「Z 函数」高论,感到恐慌。
T4 也没挂,很不错。
晚上不断回忆考场上的 T3 代码细节,还原了一下。测出来是 70 …,没有过掉极限数据。但是,70 分就这么白给了。
T3 没交上去真是一个败笔,难受了,分数直线下降。害,记个教训吧,下次肯定不会犯了。
2020.12.08
挂分挂的太厉害了,以至于我分数从 294 急速下滑到 179,难受。
挂分原因:
- T1:求 \text{lcm} 是“先乘再除”而不是“先除再乘”,以及分母为 1 时只输出分子(90 \to 50)。
- T2:是理想分数,但是也许实现的比较优秀的话可以卡过去(84 \to 84)。
- T3:没交上去(70 \to 0)。
- T4:比理想分数要高一点,应该是特判 -1 导致我加了 5 分(40 \to 45)。
(删掉了一些比较自负的话)
初三是一个实力增长期,希望今年能够完成蜕变。我一定要成为一个绝对的强者,我一定要赢下所有!