The 11th CCPC Chongqing Site / The 4th Universal Cup. Extra Stage 4 游记

· · 生活·游记

比赛过程

单人参赛。

开赛前十分钟，受到上一场比赛（圣彼得堡站，神仙场）的 EMOTIONAL DAMAGE 影响，认为 M 是签到题并死磕，然而没有成果。

若干分钟后得知签到题是 A 题。这下是真把我当外国人整了。得知此事后，我立刻使用不到 5 分钟的时间完成实现并提交。WA 了。检查后发现多测不清空，清空后 AC。于是我获得了本场比赛我 AC 的题目中的唯一一发罚时。此时比赛进行 15 分钟。

完成实现后立刻得知二签是 H。XCPC 经典之何意味分讨，花费 5 分钟完成实现，提交后直接 AC。此时比赛进行 25 分钟。

完成实现后立刻得知三签是 E。题面属实吓到我了，第一想法是上平衡树等支持动态维护相对顺序和区间和的大型数据结构，不过经过简单思考后果断转化为树状数组上二分，快速完成实现，一发 AC。此时比赛进行 39 分钟。

看看榜，好像没有明显的签到题了，不过 B 看起来有不少人在做。那就去做 B。一开始没读懂题，看懂之后直接绷不住了，这种走一个区间拆成若干个走一步的和的套路是第几次出现了，第一次是重庆集训，第二次是 WC 讲课，第三次是这里，都出几次了还出有没有点创新意识，哦好像的确是有的，这里的 n 非常大，来到了 10^9，不好解决。

那怎么搞？然后看到数据范围，一次最多只会向后跌落 100 步。那直接把转移式写矩阵里做快速幂不就完了，直接开干。

然而，这一干，就是将近两个小时。

看过我游记的都知道，在去年备战 CSP-S 期间，我的健康状态在某一天后突然急剧下滑，或者说，进入了亚健康状态。从那一天之后，我的身体就频繁出现各种状态，直到现在。

实现本题时，我开始频繁地打喷嚏，严重影响了我的思路，同时也严重延长了我花在本题上的调试时间。加之我有不在正赛上就不用草稿纸的习惯，我在将转移式写入矩阵这一步犯了很多错误。好在最后通过了样例之后还是一次就 AC 了。此时比赛进行 2 小时 24 分钟。

最后再回去看一开始我认为是签到题的 M。这个时候才发现树的结构是在输入中直接确定的，不需要搞倍增之类的东西，直接上树链剖分就可以了。加之值域 10^6，可以提前把质因数预处理出来。每个数的质因数个数都不多，暴力检查的时间复杂度可能在 O(\log^2 n\log V) 左右……嘶……

不对，\log V 是上限，最终检查的不会有那么多。直接上！20 分钟后，通过样例，但是怎么跑了 500ms，吓哭了。上 Custom Test 测了一下，88ms，还好还好，因为前面有个 O(\frac{V\log V}{\log \log V})（应该是吧？）的预处理会花点时间。上交！

测试点很多，耗了相当多的时间评测。最后好像花了三分钟左右才完成评测，一次通过。

然后想 K，假了。摆了。

最终解绑。参加了本场比赛的 Ucup 队伍几乎全都排在我上面，吓哭了。对照线下赛榜单得到 rank 72，好像是银牌。

后记

WC 开始前不久，重庆。

我与教练进行了一次长度接近一个小时的对谈。

我：“从出生起，周围的所有人都在告诉我，必须向上看……向下看无异于向深渊坠落。”

教练：“……这可能并不对。当你向上看的时候，你只能看到能力已经远在你之上的前辈。而当你向下看的时候，你会意识到，你向上看到的是高手之中的高手，而在这之前的某一天，尽管你可能没有感受到，你也已经成为了一个相对意义上的高手。”

……

于是，在 WC 期间，我以下限级的发挥，拿到了与铜牌分数线相等的分数，110 分。我应该为此感到高兴吗？我有资格为此感到高兴吗？