CSP2020游记

作者只是 AH 的一个初三蒟蒻。 初赛 J 组 $97pts$，S 组 $81pts$，海星。 膜你赛 $6$ 道题目 $100+40+100+0+100+100=440$，但后来发现 $D1T2$ 数组开小挂掉 $60pts$，$D2T1$ 求 LCA 的时候把不等号写成等号了，所以我本来能 $AK$ 的...... 考前复习了虚树优化、manacher、启发式合并等算法和一些数论知识。写了几页笔记，~~还在数学课上偷写了一点。~~ ## **$Day$ $0$** 中午在家写逆元和中国剩余定理，结果 wzm 来问我文件操作是怎么写的...... 下午去学校上了第一节课（话说听了一节课《水浒传》真的好愉快啊），下课背着书包往校门走，结果被保安拦住了，因为我要自己走回家然后去试机，但是保安不看到家长就不放...... 我：“那怎么办？” 保安：“找你班主任来。” 正往回走，上课铃响了。我到班主任办公室没找到班主任，听别的老师说去隔壁班上课了。找到班主任要手机打了个电话，终于出了校门。 到八中看到一派人头攒动的景象，进去报到排队等了半个小时......试机入门组写了一个 manacher 和 Fenwick Tree，提高组写了 Segment Tree ~~和 A+B~~。然后 $4:50$ 出八中被家长拉回学校物理考试，但是到学校都 $5:40$ 了，距离考试结束只剩 $30min$，于是就回家了。 回家后想复习一下启发式合并，就写了一下 [P5290 [十二省联考2019] 春节十二响](https://www.luogu.com.cn/problem/P5290)。 晚上也没怎么写作业，看了看数论，$10:00$ 就睡觉了。 ## **$Day$ $1$** $7:40$ 左右到了现场，然后站在考场外等了半个小时...... $8:20$ 左右进考场，看到几个小朋友在玩鼠标。然后把文件夹建好。 $8:30$ 开始考试，先开 $T1$，看到标题“优秀的拆分”莫名联想到 NOI2016...... 看完题面首先想到的是倍增，然后 $3min$ 切了。开 $T2$ 发现是个动态排序，没有仔细看数据范围，就看到 $n \le 10^5$ 心态当场炸裂，然后一路向下，开 $T3$ 看到“后缀表达式”这几个字就觉得不简单，直接开 $T4$ 然后 $5s$ 看出来是个 $dp$，$2min$ 写出来一个 $O(n^2m)$，过了样例，有 $70pts$ 了。回去看 $T2$，正准备写个 treap 什么的忽然发现分数不超过 $600$，那就直接桶排就行了。 （但是事实上 NOI 最高能得到 $705pts$ 吧，还有你确定 NOI 有 $10^5$ 人参加？） $3min$ 写完 $T2$ 然后想到了 $T4$ 的优化，再用 $3min$ 把 $T4$ 优化成了 $O(nm)$，于是我开场 $20min$ 期望 $100+100+0+100=300$ 了？？？ 然后平复一下心情回去看 $T3$，顺便吐槽题面，让本来知道后缀表达式的我都看晕了......先在草稿纸上分析了 $15min$ 然后对 $n \le 10^5$ 的数据感到很迷茫，这要是一条链不就原地爆炸了？？？决定先写个暴力。由于考前没有做关于二叉树的练习，差点不知道怎么建树......写了 $20min$ 的 dfs 发现不太对劲，我可以直接显式开栈啊！于是建好树写个暴力 $30pts$ 到手。 然后想正解，莫名其妙想到合并，就往**启发式合并**的方向想，然后有思路了！写代码写了 $40min$，$145$ 行的代码过不了样例，心态大崩。冷静一波输出中间结果，$10min$ 改好了代码过了小样例，一发过掉大样例。于是 $2h$ 时期望 $AK$ 了？？？（flag） 然后回去检查 $T1$ 和 $T2$，$T4$ 写个对拍，$T3$ 不会造数据就眼瞅，最后提前 $10min$ 交卷。 （出来之后感觉 $T3$ 的常数是不是太大了点？） llr 说 $T3$ 应该很简单，我说好难，他说直接暴力就行了，$O(n \log n)$，我说退化成一条链怎么办，他醒悟。 中午在宾馆休息了一会，下午 $2:25$ 进考场。由于上午的密码 “他山之石”，我就猜下午“可以攻玉”，于是随便输了一个没破解出来（乱码是有用的）。 老师在黑板上写下了“可以攻玉”的拼音，然后加上一堆乱码，出现了很多问题（如 k 大小写不分，o和0不分，忘加括号等等），搞得错了好几次，心态有点崩。 开 $T1$，浓郁的历史气息铺面而来（大雾）。从 $4713.1.1BC$，到 $1582.1.1$，到 $1582.10.1$，到 $1582.10.4$，到跨时代的 $1582.10.15$，到 $1582.11.1$，到 $1583.1.1$，到 $1584.1.1$，四年一循环到 $1600.1.1$，四百年一循环，再细化到一百年，四年，一年，月，日，我在历史的长河中踽踽独行（滑稽）。 光是写代码就用了 $40min$，然后样例 $2$ 出错查了 $5min$，然后一发过掉大样例。赛后想想好像可以通过某些方法将那十天直接补上的，循环节可能更好找一点。总之到 $15:30$，我结束了 $T1$。 然后开 $T2$，在草稿纸上简单画画，然后 $10min$ 就有了完整的思路，写了一个 $O(n+m(k+\log m))$，过了一会儿发现时间复杂度算的有问题，并且 $c \le 10^8$ 是假的，也根本不需要对 $q_i$ 离散化，直接令 $q_i$ 为 $i$ 就行了，时间复杂度 $O(n+m)$。 但是忽然发现 $n=0$，$m=0$，$k=64$ 的时候答案貌似是 $2^{64}$？？？去年 $D1T1$ 考了个 unsigned long long 今年又来了，而且不能直接自然溢出啥事也没有，于是写个程序算了一下 $2^{64}$，直接作为字符串输出了。 $1.5h$ 期望得分 $100+100+0+0=200$，这效率远不及上午啊。赶紧开 $T3$。发现是个 $DAG$，然后又往启发式合并上想，但这回没想出来，于是老老实实分析 $subtask$，首先 $\sum{C_j}=0$当然就是一棵 Segment Tree 的事情啦，然后 $n,m \le 1000$ 自然是暴力外加 Segment Tree，于是 $30pts$到手了。 然后去看 $T4$，发现我会写 $n=3$，然后愉快地写了 $20pts$ 的 $subtask$。然后发现什么都不会了 $QwQ$，于是回去看 $T3$，发现我会没有类型一的 $subtask$，于是写了一下，期望得 $10pts$，现在期望得分是 $100+100+40+20=260$ 了。 然鹅后面就没有什么进展了，$T4$ 想到了一个 $O(n^2)$ 的搜索，但是由于各种细节处理不当，直到比赛结束都没有调出来 $QwQ$。 比赛完听 fcy 奆佬讲他如果不挂分能拿 $280pts$， Orz。我果然还是最菜的 $QwQ$。 ## **$Day$ $3$** 洛谷自测当场炸裂：J 组 $90+100+15+100=305$，S 组 $40+95+40+25=200$，我才发现我把 J 组 $T1$ 的数据范围看错了：我看成了 $n \le 10^6$......然后又是一堆奇怪挂分，心态炸裂。 ## **$Day$ $8$** fcy 把全 AH 的 S 组成绩（民间数据）发给我看了一下，我惊奇地发现我 $T2$ 挂成 $65pts$？？？感觉是 Windows 和 Linux 的差异，我估计最后测出来应该是 $40+100+40+20=200$ 左右吧，没脸见人了 $QwQ$。预备退役了......（进不了全省前 $30$ 就要被强制退役了） 但是看了一遍整体成绩，为什么一大群同学都是 $10pts$ ~ $50pts$，貌似只有 $25\%$ 上了 $100pts$？？？排个序发现我全省 $rk42$，如果最终评测加上 $T2$ 的 $35pts$ 貌似全省 $rk29$？？？ **有希望！** 但还是很悬吧，其实如果我 $T1$ 直接离线暴力一天天往后推都有 $80pts$ 啊......这样我不就稳全省 $rk20$ 了吗？还是有不少遗憾啊。 ## **$Day$ $10$** 今天出了昨天市赛的成绩，$100+100+100+70=370$，特别愉快，但是 fcy 更强啊，$90+100+100+90=380$ 实力吊打我，太强辣 Orz。 然后听说能查 J 组的分，一查：$80+100+100+100=380$，我翻盘了！！！ 官网显示 S 组成绩暂时无法查询，那就等一等。 ## **$Day$ $11$** 中午听说能查 S 组成绩了，一查吓一跳：$90+100+70+20=280$！！！二次翻盘！ ## **$Day$ $15$** 我们老师测了一下全省的成绩，我 S 组貌似排名 $rk10$？！ ## **$Day$ $25$** 官方成绩出来了，S 组全省 $rk12$。 总结一下： S 组民间估分 $40+65+40+25$，官方得分 $90+100+70+20$..... 总算是得到家长允许去参加 NOIP 了。（考前打赌进全省 $rk30$ 就参加 NOIP）