CSP-S2 2019 游记

我简直是咸鱼，一只彻头彻尾的咸鱼。 慵懒，成为了我本次比赛的主调。 10 月 27 日晚上——也有可能是 10 月 28 日的凌晨，睡眼惺忪的我坐在书桌前，照常奋笔疾书着。作业本放回一本又拿出一本，练习材料做完一张又掏出一张，我就这样机械着循环反复着，完全看不到尽头。 在这种困倦又疲劳的情形下，我申请了停课，开始为 CSP-S2 做准备。 写完停课申请的我仿佛如释重负，用最后一点气力把作业扔到一旁，然后摊到床上，不久就睡熟了。 ------ 为期三周的训练，是缓和而有趣的。每天早上七点钟起床，慢条斯理地吃完早饭后悠闲走到学校，参加校内举行的提高模拟赛。在三个半小时里，我只愿意思考每题的满分做法，对部分分置若罔闻。倘若遇到三道简单题，被一个半小时穿了，我们便开始“指责”出题人不会出题；倘若遇到难题，思考无果或想到一种码量超级大的做法，我们便开始骂出题人毒瘤。下午原本安排的订正计划被我直接抛到脑后，跟着几个同学带着麻将，到隔壁空着的 VR 教室一起玩。一个个工作日，就在这样“欢快”的气氛中，快速地流去。 11 月 15 日，第二天就是正式比赛了，但我不想紧张，也懒得紧张。我自大地认为，凭借我的能力，两天比赛总分上 $500$ 不在话下，考前只要尽可能放松就可以了。 ------ 11 月 16 日，CSP-S2 2019 Day1。 考点就在自己的学校，我感受到了极大的便利。不单是仅靠步行就能到考点，更是我熟悉这里键鼠的手感。如往常一样的，熟练地接受安全检查、熟练地找到自己的位置、熟练地关掉安全软件、熟练地配置好 FrC……一切都是那样熟悉与亲切。 8:30 准时开题。 看到第一题时，我被那长长的题面吓了一跳。 细细读完后，发现只需模拟题意反着推一遍就可以了，再观察一下数据范围，$n \le 64$，那需要 $\texttt{unsigned long long}$，输入是 $\texttt{\%llu}$。另外就没有什么细节了，我就开始实现。 大概 8:40 的时候，过样例了。我又测了一组 $n = 64, k = 2^{64} - 1$ 的数据，发现输出是 $10000\dots$，感觉很有道理，就没有再管它，去看下一题了。 第二题似乎是要求括号序列数。读完题，我第一时间的反应是： 根据套路，某个点之前的括号序列不好统计，那就统计以某个点为结尾的。 根据套路，括号序列可以用一个栈维护。一个右括号可以与栈顶的左括号转移。 于是我会做序列的情况了。 根据套路，dfs 到树上的一个点 $u$ 时，dfs 栈内所有点恰好是 $u$ 在树上的所有祖先节点，且按照顺序排列。 于是我也会树的情况了。 又思考了细节，似乎没有的样子。 接着就开始打了，大概 8:50 的时候过了样例。然后写了个 $\mathcal{O}(n^4)$ 的暴力作对拍，就放在一旁去看第三题。 9:00 进入第三题，似乎可以 AK 的样子。 读完题：这题还挺有意思的。$\mathcal{O}(n \log n)$ 做法似乎很不好想。 看到 $n \le 2000$：天哪这不是简单题吗，把贪心 + check 路径的 $\mathcal{O}(n^3)$ 用树剖之类的东西维护一下不就做到 $\mathcal{O}(n ^ 2 \log n)$ 了吗。 接着开始写，写了半个小时左右，发现过不了样例的第二组数据。小黄鸭调试法找不出什么问题，手玩一下才发现 $5$ 号节点上不去，而题目要求每条边必须被删除。换句话说，我想的贪心是错的。 我无比懊悔，赛前教练无数次地提醒过，想到一个做法时，一定要仔细检查它的正确性，以及注意它是否存在细节和边界问题。在这题上，我被欲望冲昏了头脑，忽略了教练的忠告，导致了将近一个小时的时间被浪费。 我开始苦想正解。大概一个小时后，我还是没有任何思路。 11:00，我才终于决定写第三题的暴力。 根据我的经验，这样的题目，暴力应当是很好打的。在往年的 NOIP 赛场上，每题的暴力分都达到了大六七十。 $n \le 10$，随便 $\mathcal{O}(n!)$ 枚举一下就行。 树退化成链，贪心从小到大考虑……诶等等，一个节点似乎可以把它的权值先转移走，再赋为其它的权值……这样与先交换后跨点交换好像是等价的，那就对原序列建一个双向链表，然后维护一下贪心似乎就可以了。 我这么去写了，写了半个小时，又调不出来。而且还不知道是做法假了还是实现假了。 算了不想链了，去想想菊花。菊花似乎就是找到一个大轮换，使得排列字典序最小。那这样直接贪心找并查集维护就好了，感觉复杂度没有问题，还特别好写。 五分钟左右写完了，过了样例，$10$ 以内的数据和暴力拍没有问题。 剩下的时间我全部在调链，始终没调出来。 最后一题 $35$ 分收场，太难过了。我无比自闭，因为我的经历告诉我，一名出题人，尤其是在这种官方比赛里，如果出了一道难题，那么部分分一定会给非常多；这也就是说，如果一题的部分分非常少，就说明这是一道简单题，除非出题人希望被喷。 按照这种部分分水准，这题应该是一道简单题，应该又是一天全场 AK 的 Day1，又是一天没有区分度的 Day1，但我被区分了。 出考场时，出我所意料的，又如我所希冀的，我校一位 NOI 银牌大佬开始问候 T3 出题人的家人，旁边还有一群人跟着附和。 我上去打听了一下，没有一个人写出正解，也没有一个人写出链，甚至没有一个人写出菊花，全部都是 $10$ 分。 有一位同学想出正解了，但他说细节太多代码非常难写，三个小时打不完。 有好多同学有 $\mathcal{O}(2^n)$ 做法，但出题人没给部分分。 还有一位同学有 $\mathcal{O}(n^5)$ 做法，但出题人也没给部分分。 我在疑惑与不解中，结束了这没有区分度的 Day1。考后把程序放到各大 OJ 的民间数据测，结果都是 $100 + 100 + 35 = 235$。 ------ 11 月 17 日，CSP-S2 2019 Day2。 这真的是我做过的体验最好的一套题，发自心底地说。 区分度良好，思维难度不太大，码量适中，有 AK 可能性。比 Day1 好了太多太多。 第一题，果不其然来了一道 $998,244,353$。我一开始想的是枚举菜品数，然后组合数计算方案，结果发现 $a_{i, j}$ 可能不同，组合数派不上用场。 正卡壳之际，我又想起教练赛前传授我们的经验：题目给的每一个条件都至关重要，不能浪费。于是我开始考虑这个 $\lfloor \frac{k}{2} \rfloor$ 的限制有什么特殊之处。 自然地，我想到了只会有一个数大于 $\lfloor \frac{k}{2} \rfloor$。也就是说，一种不合法的方案中，一定有且仅有一件主要食材超过使用限制。这使得枚举不合法方案成为了可能，容斥的做法被摆上了台面。 接着，我大胆的设计了一个状态为 $n^3m$ 的 DP，因为我知道这肯定可以优化。果然发现有两维可以作个差分压成一维，于是复杂度就变成了 $\mathcal{O}(n^2m)$，通过了第一题。 这时候已经接近 10:00 了，我寻思对拍很难写，时间也不太够，就懒着没有写对拍。 做完第一题后，我同时看 T2 和 T3。发现 T3 的 $75$ 分暴力非常好写，性价比极高，就花了十几分钟写完了，过了样例。同样是没有对拍，因为太懒。 我深知，Day2T2 决定了全场比赛的成败。它不如 D1T1, D1T2, D2T1 一样自带签到属性，也不像 D1T3, D2T3 那样压轴防止 AK。作为腰部，一场比赛真正的区分度都需要在 Day2T2 这道题上体现。它往往思维量极高，极其考验选手能力。 我很快会了 $\mathcal{O}(n^2 a_i)$ 的 DP 做法，大概有 $24$ 分。 注意到区间和只有 $n^2$ 种可能，我把 DP 优化到了 $\mathcal{O}(n^3)$，大概是 $36$ 分。 把递推式写出来，发现可以用后缀最小值优化转移，我又得到了一个 $\mathcal{O}(n^2)$ 的做法，$64$ 分。 这里状态就是平方的了。接着一个小时我全部在思考如何优化这里的状态数，大致思路是从分析 DP 值的单调性开始，然后试着能不能离散，用动态开点线段树去维护每一个 DP 的状态，然后线段树合并之类的整体 DP 技巧进行转移…… 我还是不会，然后就果断放弃了，因为这样就算会了也打不完，只好 $64$ 分交卷。 考后证明了，这道 Day2T2 是我最后悔的一题。 我随便问了几个同学，要么说自己看到题一眼秒掉，要么是不会高精度的拿了 $88$。当我问他们怎么做时，他们的回答是：“这不是睿智题吗，猜个结论就过了。虽然我不知道这个结论为什么是对的。但是你看着数据范围，显然不是个大聪明就不会往 DP 这方面去想嘛，这种 $4 \times 10^7$ 怎么可能是 DP 呢，肯定是贪心或结论题啊。” 看来还是自己经验不够，我果然又被区分了。 Day2 结束了，民间数据测出来分数仍然是 $100 + 64 + 75 = 239$，各 OJ 测都一样。 总分只有 $474$，随便问个人都是 $485, 498, 499, 504$，我哭了。 这道 Day2T2 给我留了太大的遗憾，到头来追究原因，才发现自己的失败在自己的慵懒中早已奠定。 我开始懊悔自己考前没有认真对待模拟赛，没有端正自己的考试策略。 我开始懊悔自己考前没有多刷题，积累做题套路。 我开始懊悔自己考前没有勤写题，导致写题速度偏慢。 我开始懊悔自己的懒，自己的妄自尊大。 ------ 结束了，回去学文化课了。 我感谢这次竞赛的经历，它带给我许多宝贵的东西。它让我意识到，自己作为一名普普通通的高中学生，所拥有的知识量是多么的浅薄，所了解的世界是多么的狭隘。我也从中感受到，学习是多么幸福、多么重要的一件事，只有努力学习积攒知识，才能被更多人正眼相待。未来路上，我将更加努力前行。 $$ \texttt{by Tweetuzki} \quad \mathcal{2019.11.18} $$