落日余晖——CSP2024闲谈

这是我最后一次参加 CSP 的机会。身份的转变使得我能够以一个更客观的视角看待这次比赛。不过我还是更想以“我”这一第一人称视角来叙述我的所见所思。

初赛

第一感受，相比之前几年的题来说很轻松。

选择题没有什么特别大的亮点。对哈希表的考察可能创到了一些人，因为其实还是有很多人没怎么学哈希表的（包括我在内）。最后一题最小割方案数可以通过观察来大大减少枚举情况。属实很轻松。

大题第一题用伪随机生成数据然后快排，常规。

第二题用简单的组合意义分析两份代码的差别就是第一份代码会忽略前导 0。其中最大差值的计算猜测情形是 01111111 即可。证明也是简单的。

第三大题揉了个筛法跟二叉树，反正也简单。

程序填空更是更是。。。

第一大题来了个浙江信技二分题，不过这样的题确实很 educational，还是会有某些人打了好几年 oi 连二分每种情况怎么写也写不明白的。

第二大题是一个错误的次短路。选答案还是很好选的。可惜代码就是错的。

于是我在这样一场轻松的初赛中获得了新成就 AK 初赛。。。相比我初中时参加的初赛这次简单太多太多了。怀念当年的四毛子与高低位状压 dp。

复赛

总共复健写了个位数道题就出战了。

首先我想提一嘴 J 组的 D 题。我还是想提醒一些 oier，要培养自己对于题目的难度定位能力！在我的理解中这个题其实比 S 组的某几个题还难（如果是你觉得我太菜了那就是你对hhh）毕竟两个 step 都比较吃一些基本的观察能力与解决问题能力？

说回我参赛的 S 组。不得不说，oi 比赛这东西属实是一年变一个样。

第一题是比较基础的题，分析题目可以发现从小往大考虑是一个很正确的思考方式。思考了之后就发现对于一个人来说比他小的那些人对他来说没有本质区别，所以模拟一下即可。当然再归纳一下就能归纳出答案等于众数的出现次数（我只会归纳，我赛场里并没有看出来这一点）。

第二题有点长，我先看了题目长度更短的第三题。通过注意到“两个隔得远的相邻同色点”才是需要特别关注的对象，可以设出 dp 状态 dp_i 表示 i 与 i+1 颜色不一样（即某个同色连续段以 i 结尾下一个以 i+1 开头，把它称之为“间隙”），然后转移到下一个间隙 j。我们发现转移的代价用前缀和分成独立的两部分很简单并且特殊的代价只在 col_i=col_{j+1} 时发生所以用桶就可以简单做到线性。

这两个题只花了我 15 分钟时间。然后我去看第二题，第一眼我对这样的题目背景嗤之以鼻。

写了一会儿式子发现好多式子在最后给了。然后问题可以转化成经典的“最少点覆盖一堆区间”，贪心就好了。我认为这个题出的挺好，可惜后面这个问题已经早就成套路了。

然后我就有充足的时间做 D 题。看了一眼数据范围就发现不乐观，应该只有 O(Tn) 的做法能够通过。

然后我进行了分析，题目多次询问某个前缀，那么首先认为我应当在逐个插入的视角下把每个前缀的答案都求出来。

逐个插入看起来避免多一个 \log 因子是一个很困难的事情，我先在脑子里保留了诸如 \sum \log_2{(i\ \text{xor}\ i+1)} 的猜想，但是当然是要先把带 \log 的做法分析干净。

首先分析没确定值的那部分，形如诸多棵子树，考虑 x 从比赛结构树（用每场比赛作为一个结点建成的树，也可以直接说是 trie 树）上不断往上走的过程，维护有那些“能够走到当前点并且是未确定值的下标”的和，由于每次比赛的限制是能力值大于等于轮数，也就是说以前进行的比赛对当前这一轮没有影响，也就是说对于这些位置，任意时刻都可以看作是值未确定。这部分分析是简单的。确定值的那部分复杂了很多，一个观察是：这些位置一定是在 i 往上走的某个点的左儿子的胜者，它们想要往上走要么自己当擂主够格，要么对面当擂主不够格。后者如果走上来一个未确定值的点可以让它放水。这样直接做可能需要 \log^2 把后面的限制提前预处理掉在这里判断就可以单 \log。（upd on 当天晚上：突然发现做法稍微改一下就线性了，感觉还是当时没想明白的原因hhh）

说的有点乱，这是我在考场上的做法。由于好久不写代码了写的很慢也调了很久。常数还很大！T=64 都过不去。

最后 300+76 离场了，不知道会不会挂。留下了一点点的小遗憾。

这些就是我的比赛思考过程，写的比以往的游记详细了很多，希望能给大家一个参考。

总结与拓展思考

最后，评价这次的 CSP 试题：题目单独拆开来都不错，组题有点令人不适。三个极其简单的题+一个思考内容体量较大的题确实会带来比较差的体验（至少对于我来说是这样的）。不过官方比赛最近两年几乎没有过一场大部分选手体验都很不错的组题，这也是挺正常的。

OI 比赛每年的命题人都在更迭，“命题经验”很难在短时间内得到积累。并且某些“组题人”的能力与作用有待商榷，因此我们应当对大部分命题人表示理解并致以敬意（除了某些把个人姿态摆得极高逃避责任的出题人，这里有很多例子想必也不用我多说了）。另外，在役的选手们，也可以尝试将自己放在出题人这个视角来看待一场比赛。无论未来是否有命题想法，这个行为绝对是有帮助的。一方面，能够帮助你找到一些一定程度上规避比赛中操作的变形或者不确定因素的干扰的方法。另一方面，如果未来有命题的想法，你作为选手打过的每一场比赛经历与每一次体验感受都是很宝贵的，及时将其转化为命题经验当然是一件“何乐而不为”的事。

接下来就是我的一些胡乱说话，也放在这儿了。

首先，我注意到了 OI 存在一些前人未归纳过的一些抽象的基本功概念。例如我认为对于学习数据结构来说很重要的一个能力：在颅内生动形象地模拟数据结构维护信息的动态过程。

例如学习笛卡尔树，直接扔给别人一段文字很难让人 get 到意思，但是如果让他尝试在脑子里模拟这个过程，或者说做个动画给他看，那么学习的难度会大幅下降并且会有更全面的理解。

更进一步的，我认为有了对基础的数据结构的深刻认知，学会灵活运用它们的能力的基础上才应该去高频率地尝试更高级的数据结构。多尝试用简单的数据结构来解决问题能很好地提升数据结构解题能力，甚至是一些图论解题能力！

由于是胡乱说话而且暂时还没有时间整理一些例子来说明这些观点。以后会写的，算是预告？