NOIP2020 游记

    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)T = (AB),那这样相当于枚举一个前缀。再枚举一个 ii,这时候 CC 是确定的。

    预处理前后缀的奇数字符出现次数,然后用树状数组维护一下 TT 里有多少个 AA 满足 F(A)≤F(C)F(A) \leq F(C),然后就可以直接统计了。

    这样做的话时间复杂度是一个调和级数的形式,单组数据应该是 O(nlog⁡n+nlog⁡∣∑∣)\mathcal{O}(n \log n + n \log |\sum|) 的。

    嘶,好像很悬的亚子,姑且就先码上吧,大概 9:11 就写完了,测了一下大样例,感觉很棒。

    吸取了 julian 的教训,打了个对拍,把 T1T2 都拍了一下。嗯,真的很稳。

    这时候已经 9:37 了,稍微看了看 T3T4 的题面,T3 好像非常棘手的样子,就先开了 T4。

    草,怎么这么难,想了一会儿,实在是想不到怎么从整体分析。

    看了看部分分,只会写 1∼81 \sim 8 这些测试点了。于是码码码,大概 10:30 才写完,手玩了几组数据,感觉很稳,就去看 T3。

    T3 好像有点麻烦,但是应该还是可以做的。

    可以一个颜色一个颜色来考虑,强制一下第 ii 根柱子的颜色为 ii。

    对于第 jj 根柱子,可以用 O(m)\mathcal{O}(m) 的次数把第 jj 根柱子里面所有颜色为 ii 的球都移动到第 jj 个柱子的最上方。

    然后再将所有颜色为 ii 的球统一移动到一根柱子上。

    这样做的话操作数大概是 O(n2m)\mathcal{O}(n^2m),由于借用了第 n+1n + 1 根柱子做手脚,可能还要乘上一个 22 的常数。

    判掉一些不合法的操作,也许不会到达复杂度上界。

    P.S. 事后计算了一下,该算法的严格操作量不超过 m(n−1)(n+4)m(n - 1)(n + 4)。

    考场思路非常混乱,也想不出什么比较强的高论,且打且看吧。有好多代码实现上的细节,一直码一直码,中途上了好几次厕所,终于是在 12:27 的时候过掉了大样例,操作数才 20w 多一点点。手玩了好多组数据,正确性应该是没什么问题。按 CCF 的数据强度,信仰告诉我可以过。

    玩了一会儿扫雷,然后就到了 13:06 分,出了考场。

    理想得分:100+100+100+40=340100 + 100 + 100 + 40 = 340。喔唷,看起来非常牛逼。与巨佬们交流了一下,感觉是在大众分之上的,很棒。

    接着大家一起去聚餐,没错还是那家“农家小乐”。

    接着就是坐车回长乐了。回到家,拿到了全省的代码。

    woc,我 T3 忘记交上去了?!真气人,怎么会在这种时候掉链子。

    测了一下 T1、T2、T4。

    不会吧不会吧 T1 还真的有人会去卡 long long 阿,于是成功被卡掉 1010 分,希望 CCF 能够做个人。

    ohhhhhh T2 卡过去了,真不错。据说有 O(n)\mathcal{O}(n) 的「Z 函数」高论,感到恐慌。

    T4 也没挂,很不错。

    晚上不断回忆考场上的 T3 代码细节,还原了一下。测出来是 70 …,没有过掉极限数据。但是,70 分就这么白给了。

    T3 没交上去真是一个败笔,难受了,分数直线下降。害,记个教训吧,下次肯定不会犯了。

    2020.12.08

    挂分挂的太厉害了,以至于我分数从 294294 急速下滑到 179179,难受。

    挂分原因:

    • T1:求 lcm\text{lcm} 是“先乘再除”而不是“先除再乘”,以及分母为 11 时只输出分子(90→5090 \to 50)。
    • T2:是理想分数,但是也许实现的比较优秀的话可以卡过去(84→8484 \to 84)。
    • T3:没交上去(70→070 \to 0)。
    • T4:比理想分数要高一点,应该是特判 −1-1 导致我加了 55 分(40→4540 \to 45)。

    (删掉了一些比较自负的话)

    初三是一个实力增长期,希望今年能够完成蜕变。我一定要成为一个绝对的强者,我一定要赢下所有!