CSP-S 2020 游记

Alex_Wei · 2020-11-07 23:59:15 · 个人记录

以前没有写游记的习惯（主要是写出来的文字太烂），就让这次 CSP-S 2020 成为起点吧。

坐标 JS NJ。

Day -?

QQ 显示异地登录，于是把密码改成了 iakcsp2020（

Day -5 ~ -4

CF 连炸两场直接 IM（Div.1C 害人），心态爆炸直接导致接下来一周都没有碰键盘，同时也预示一周后 CSP 爆炸（确信

Day -3 ~ -1

沉迷 whk 无法自拔。

Day 0

下周二期中考，所以绝大部分精力都放在了 whk 上面，回到家后才想起来第二天有 CSP（雾

不过化学真的好有意思啊（雾

（update on day 4：期中考试化学炸了，淦）

晚上打了几（零）个板子，发现连 dijkstra 都不会打了，顿时感觉要凉。

九点收到了 ycx（@chenxia25）& syx（@Sunny_Sun）的祝福，他们俩老好人了/qq

Day 1

抱着 “反正才初三影响不大，随便玩玩” 的心态，早上还是在搞 whk（

八点又收到了 @Isaunoya 的祝福 /qq

吃过午饭 12:30 出发去南航，背包里装了一大堆 whk 复习资料（

路上在复习英语 grammar points（单选 25 分啊，雾）看着看着就睡着了（

小堵一会儿，13:20 到了南航西大门口，一眼看见 ycx & tzc（@ET2006）& syx & lyc（@LTb_），相互假了一会后进了南航。

带了手机可惜没拍照。久别重逢总是令人感慨万千：第一次来这儿参加 NOIP-pj 2018 的时候还是个小不点（）

太阳特别晒。我那一群同学就在太阳底下傻站着聊天（（（

csy 竟然和我在同一个考场，%%%。

后来发现周围的人都带了零食，只有我是一瓶水，馋啊（

进门的时候每人发了一个参（xuan）赛（chuan）手册，听说不给带进考场 ycx 直接给扔掉了（

csy：应该会有一个 998244353（泄露试题实锤了，引恐禁三，雾）。

我：盲猜会考高精（ycx：都 0202 年了怎么可能还考高精）

《假 如 T 2 算 高 精》

13:50 准时进了考场，好评。

进考场的时候刷了一遍金属探测仪，后来监考人员提醒手机要关机，不放心回去检查又刷了一遍金属探测仪。

发现没拿水杯又刷了一遍金属探测仪（）

试机的时候打了个快读板子和一些宏定义，希望能省点时间。

等待试题下发的时间心情比较轻松，就像是当做一场小 test（确实也是），没有去年很紧张的那种感觉（可能是实力增加了？），看来做足心理准备，保持风（sui）轻（bian）云（wan）淡（wan）的心态确实挺重要。

14:26 提前四分钟下发试题好评（）

点开 pdf：这也太丑了吧（ 没有 LaTex 看得很不习惯。

扫了一眼 TimeLimit：1s，1s，2s，2s，没有 O2。

然后看 T1：？？？

大模拟，然后开始写，写到一半发现只保证答案在 10^9 以内。然后估摸着这作为一个坑点，大样例应该会在 int 范围以内，点开一看，果然，应该能坑掉不少人？

写着写着时间就过了 30min，测了一下样例，WA。

一看这情况不对劲啊，不会栽在 T1 手上吧，不会吧不会吧？

debug 好一会才发现 “只要年份是 4 的倍数就是闰年” 这句话适用于所有 1582 前的年份（我以为是公元前）。淦，还要分情况讨论，出题人 ****。

调着调着时间就过了 1h，15:40 的时候终于调过了样例和大样例。

想到接下来三题都还没看，感觉有点慌。

T2 一眼题，想了想极端数据（n,m,c,k=0,0,1,64）发现这是要用高精的亚子？（内心狂喜：这绝对坑掉一大批人，拉低分数线，就有更大概率 1=）

码到一半发现空间可能会炸，又看了看题面发现 a_i,q_i 互不相同。

这不就简单了嘛，连 a_i 的数组都不需要开，空间复杂度瞬间降为 \log（实际上可以做到线性，不过没啥区别）

15min 码完高精程序，小样例大样例一遍过，爽啦。

（出考场后发现可以特判 ans=2^{64} 的情况，剩下来直接 ((2^{bit}-1)\oplus n)+1 就行）

（upd：大概 2^{bit-1}-n+2^{bit-1} 就够了/fad）

（upd：我在考场写的是 O(nk) 的，想了下可以做到时间 O(n+m) 空间 O(1)）

感觉没啥问题，懒得打对拍，直接丢掉看 T3。

16:00

看到题目描述没有任何字符感到很惊讶，以为是什么奇奇怪怪的题目。

认真读一遍题：函数调用？建图！没有递归？有向无环图！单加多乘？数据结构！

等等。。。有向无环图怎么上数据结构。。。有向无环图上 DP！

想 T3 的时候总感觉和正解特别接近，又仿佛是那么遥远。。。

一番苦思冥想，终于搞出了正解。

然后就是码码码，码到大概 16:50 过了两个小样例，但是大样例死活过不去。

使用干瞪眼法 debug 无果，期间一度怀疑是不是假掉了。。。

最后还是决定 d(ui)p(ai)，17:20 拍上，第一组小数据（n,m,q=20）就挂掉了 /fad

缩小数据范围后（n,m,q=5）第一组数据又挂掉了，离谱。

又看了 10min，终于发现是计算贡献的时候，函数编号和数据编号弄混了。。。改掉就能过大样例了。

fatal mistake！浪费了 40min 啊 QAQ。

（后来听说 T3 大样例很水，不过和暴力 + 随机数据拍上的我丝毫不慌，雾）

想着 300 分 1= 大概稳了就没打算再认真搞。

先用 15min 检查了一下文件，确保没有问题之后才开的 T4。

17:45。