CSP-S 2020 游记

以前没有写游记的习惯（主要是写出来的文字太烂），就让这次 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。 $n=3$ 简直是在送分，5min 不到 20 分到手。 接下来 $n=10$ 好像也很好拿，不过想到了贪心 + set 解法 $O(n\log n)$ 就直接 rush。 码完后 18:20，发现能过小样例但是大样例会相差 1，难受，估计也 debug 不出来就弃掉了，剩下 80pts 随缘拿分。 18:28 检查完，18:30 准时收卷。 估分 100+100+100+20=320。 这次签字确认比去年不知道快到哪里去了，好评。 但是一开始把编号和机位号弄混掉了，找不到在哪签字（雾 --- 出了考场和 ycx & tzc 交流了一下，发现他们估分也是 320，大众分 320？ 他们是 100+100+50+70，原来 T4 这么水的吗？难受。 后来说 T2 会炸 ull 他们全部傻眼（（（不过应该也就 5 pts 回到家想自测但是一直没有数据，大概九点的时候 ycx 发来消息：315。 遂要了网站前去自测，评测的时候手都在抖。 民间数据没有挂分！hooray！比去年还高了 9 pts（ ## Day 2 & 总结 不说遗憾那是假的，毕竟 T4 的 70pts 那么好拿。 自今年九月以来，进入初三，学校的压力顿时大了很多，很大一部分时间都分给了 whk，只是借 CF 吊着一口气。 在这样的情况下，能比周围大部分同学高，运气成分确实功不可没。 诚然，如果再给 1h 说不定能 AK 比赛，但是能够避开 T1,T2 的大坑，找出 T3 的 bug，已经是非常幸运了。 upd： 洛谷民间数据：100+100+100+20=320。 没有掉坑，没有对拍，没有挂分，这得归功于一年来打的五六十场 CF 啊（ ycx T4 $a$ 数组没还原挂成 15pts 了，惨惨。 tzc 好像 T2 挂成 75pts 了？ csy 370，%%% **如果一个人碰上了 $5\%$ 的好运，他又有什么资格不去感激这 $5\%$，而是遗憾没有那 $1\%$ 的运气？** ## 题解 T1（julian）： 模拟就行，就不放代码了，没啥意义。 T2（zoo）： [动物园](https://www.luogu.com.cn/blog/AlexWei/solution-p7076)。 T3（call）： [函数调用](https://www.luogu.com.cn/blog/AlexWei/solution-p7077)。 赶紧复习 whk 去了，溜了溜了。 求赞 QAQ