第一次CSP-S

昨天成绩出来了，第一次 CSP-S，初赛没过。其实考完以后心里大概已经有数，只是成绩真的出来，还是会有一点失落。毕竟跟着老师学了挺长时间，第一次真正去参加这种比赛，总还是会想，万一能过呢。结果没有，第一次就停在初赛。

考点在宁德一中。前一天先过去看考场，我当时还穿着五中的校服，走到门口以后越看越觉得显眼，索性把校服外套脱了，混进去找教室。呵呵，这感觉还是学校，只不过换成了宁德一中的教学楼、走廊和课桌。以前算法、C++、数据结构这些东西更多是在跟着老师学，真正跑到另一所学校，发现这里居然有一群人专门来参加同一个比赛，还是挺新鲜的。

考试当天人很多，具体多少没数，至少几十个，感觉快一百人了。候场的时候看过去，基本都是一中的学生，很多人互相认识，有老师带着，也有家长直接陪进来，在旁边说几句话、帮忙拿东西。我就自己一个人站在那里，谁也不认识，也没人送。倒也不是紧张或者孤独，就是感觉有点怪，好像别人本来就在这个环境里面，我是从五中临时跑过来参加一次。前一天还要脱掉校服混进来看考场，第二天已经一个人站在这里等着考试了。

但我其实挺喜欢这种感觉。那一天终于不用坐在自己学校的教室里上每天那些课，而是可以离开校园，专门跑去做一件自己真的感兴趣的事情。也没有特别强烈地想什么获奖、保送，没有认真考虑过这个比赛最后能给升学带来什么。第一次来，更多就是想试试看：真正的 CSP-S 是什么样，卷子会出什么，别人都学到什么程度，自己进去到底能做成什么样。

真正发下卷子以后，脑子很快就开始有点嗡嗡的。第一轮是纸笔考试，和平时写程序完全不是一个感觉。平时有电脑、有 IDE，代码写出来能编译，错了还能改，实在不确定就跑几个数据看看。到了考场，一整段程序印在纸上，变量怎么变、循环走几次、递归跑到哪里，全得自己拿笔一点一点推。稍微长一点，前面的东西还没完全弄明白，后面又接着来了。

前面的选择题还稍微好一点，至少很多题知道它在问什么。往后做就越来越没底，稍微复杂一点的题，说实话已经有不少是在排除几个明显不像的答案以后靠感觉蒙。纸上又不能跑，盯着一段程序看了半天，四个选项还是觉得都像那么回事。做到后面，已经不是“我怎么严谨地把答案推出来”，而是“这个应该比较像吧”。

昨天成绩出来以后，我又把卷子和讲解翻了一遍。有几道题事后看其实没有考场上感觉那么吓人。比如哈希表那题，把 2、7、10、18 放到地址 0～10 的哈希表里面，问哪个哈希函数不会冲突。挨个代进去就行，像 `floor(x / 2) mod 11`，四个数最后得到 1、3、5、9，没有重复，所以不会冲突。考场里看到“哈希函数”几个字会先想一堆，事后看其实就是老老实实代数。

二分图那道也是。24 个顶点，问最多能有多少条边。一个二分图的边只能从左边连到右边，如果两边分别有 \(x\) 和 \(24-x\) 个点，最多就是 \(x(24-x)\) 条边。两边尽量平均，12 和 12 的时候最大，所以是 144。讲解看完以后觉得挺顺，可坐在考场里的时候，前面已经做了一串完全不同的题，再突然切到图论，脑子就是没那么清楚。

程序阅读里面有一道随机划分的程序，事后看讲解才比较明白，它其实是在做类似快速选择的事情。每次找一个 pivot，把数据划开，然后只继续处理包含目标位置的那一边，所以平均情况下不是像快速排序那样两边都递归，复杂度可以做到 \(O(n)\)；但如果每次都划得特别差，还是会一路退化到 \(O(n^2)\)。这些东西老师都讲过，可考试的时候代码换了一种写法，夹在那么长一段程序里面，我就没有马上把它认出来。

还有那道很长的字符串程序，我考场里看得相当迷糊。里面自己写了类似 Map 和 Queue 的东西，两个队列来回跑，一大堆字符串旋转和状态判断。当时只觉得代码怎么这么长，根本没很快看出来整体在干什么。后来对着讲解才发现，它实际上是在两边同时搜索，也就是从初始字符串和目标字符串分别往中间找；哪边生成的状态碰到了另一边已经出现过的状态，就把两边的步数加起来。现在再对着代码看，那两个队列和两套状态记录其实已经把思路摆在脸上了，只是第一次在考场里看到这种写法，脑子根本没往“双向搜索”上面转。

最后一道完善程序还是难。题目给一个整数序列，定义 `w(x) = x + popcnt(x)`，再从里面选一个子序列，让相邻两项异或以后得到的分值总和最大。最直接的想法大概就是动态规划，假设 `dp[i]` 表示选到第 i 个数时的最好结果，那么可以从前面的某个 j 转移过来：

dp[i] = max(dp[j] + w(a[j] xor a[i]))

问题是 n 最大到 40000，这样把前面的 j 全部扫一遍肯定太慢。讲解里面真正关键的地方，是利用每个数只有 16 位，把高 8 位和低 8 位拆开，另外维护状态，把原本每次对所有前驱的枚举压掉。题目本身其实已经给了“把前后位分开计算”的提示，但我考试的时候看到这个提示，也只是知道大概应该利用二进制做点什么，离真的把几个空补出来还差得很远。做到那里，基本已经属于能推一点是一点，实在不会就猜。

这么重新看一遍以后，感觉这张卷子很奇怪。有些题讲解一摆出来，会觉得“原来就这样”；但把讲解拿掉，再把自己放回考场，完全又是另一回事。老师讲过、自己也做过题，并不代表换一套写法、塞进一张陌生卷子以后，马上就能认出来。尤其是纸笔程序阅读，我以前没有特别强烈地感觉到，会自己写代码和能在没有电脑的情况下把别人的代码完整读下来，确实是两种能力。

不过考完出来的时候，第一反应其实没有特别难受。更多是觉得，哦，原来真正的 CSP-S 就是这个样子。前一天还脱掉五中的校服混进宁德一中找考场，第二天自己站在人群里候场，然后真的坐进去做了两个小时。昨天成绩出来，确认第一轮就挂了，当然可惜，但好像也没有什么不能接受的。

毕竟第一次本来就有很大一部分是在试试看。能从平时的学校里跑出去，去参加一场自己确实喜欢的东西，本身就已经挺有意思。没有想太多保送，也没有什么一定要靠它证明什么的任务，只是想去，然后就去了。

至少现在卷子见过了，考场坐过了，蒙也蒙过了，挂也挂过了。

下一次再来，就不是第一次了。