第一次CSP-S
昨天成绩出来了,第一次 CSP-S,初赛没过。
其实考完以后心里大概已经有数,只是成绩真的出来,还是会有一点失落。毕竟跟着老师学了挺长时间,第一次真正去参加这种比赛,总还是会想:
万一能过呢。
结果没有,第一次就停在初赛。
去宁德一中
考点在宁德一中。
前一天先过去看考场。我当时还穿着五中的校服,走到门口以后越看越觉得显眼,索性把校服外套脱了,混进去找教室。
呵呵。
进去以后感觉还是学校,只不过换成了宁德一中的教学楼、走廊和课桌。以前算法、C++、数据结构这些东西更多是在跟着老师学,真正来看看以后,才发现这里居然有一群人是专门来参加同一个比赛的。
还是挺新鲜的。
考试当天人很多,具体多少没数,至少几十个,感觉快一百人了。候场的时候看过去,基本都是一中的学生。很多人互相认识,有老师带着,也有家长直接陪进来,在旁边说几句话、帮忙拿东西。
我就自己一个人站在那里,谁也不认识,也没人送。倒不是觉得紧张或者孤独,就是有点怪。感觉他们本来就在这个环境里面,而我是从五中临时跑过来参加一次。
前一天还要把校服外套脱掉混进来找考场,第二天已经一个人站在人群里面等着考试了。
不过我其实挺喜欢这种感觉,那一天终于不用坐在自己学校的教室里上每天那些课,而是可以离开学校,专门跑出来做一件自己真的感兴趣的事情,说孤独吧,也有。我也没有特别认真想什么获奖、保送,更没有想过这个比赛最后到底能给升学带来什么。
第一次来,更多就是想看看:
真正的 CSP-S 是什么样?
卷子会出什么?
别人都学到什么程度?
我进去到底能做成什么样?
然后就来了。
纸上写程序真的不是一回事
真正发下卷子以后,脑子很快就开始有点嗡嗡的。
第一轮是纸笔考试,和平时写程序完全不是一个感觉,平时有电脑、有 IDE。代码写出来可以编译,错了还能改,不确定就跑几个数据,实在不行还能一点一点调,但是到了考场,一整段程序直接印在纸上。
变量怎么变
循环走几次
数组现在是什么
递归跑到了哪里
最后输出什么
全部要自己拿笔一点一点推,稍微长一点,前面的东西还没有完全弄明白,后面又接着来了。前面的选择题还稍微好一点,至少很多题知道它在问什么,往后做就越来越没底。稍微复杂一点的题,说实话已经有不少是在排除几个明显不像的答案以后靠感觉蒙。
纸上又不能跑,盯着一段程序看半天,四个选项还是觉得都像那么回事。
做到后面,已经不是:
我怎么严谨地把答案推出来?
而是:
这个应该比较像吧……
有些题事后看又觉得不难
昨天成绩出来以后,我又把卷子和讲解翻了一遍,然后就出现一种很奇怪的感觉。
有些题事后看,好像根本没有考试的时候那么吓人,比如哈希表那题。
把:
2
7
10
18
放进地址:
0 ~ 10
的哈希表里面,问哪一个哈希函数不会产生冲突。
其中一个函数是:
floor(x / 2) mod 11
那就老老实实代进去:
2 -> 1
7 -> 3
10 -> 5
18 -> 9
没有重复。
所以不会冲突。
就这样。
但是考场里面看到:
哈希函数
几个字,脑子会先自动觉得它很复杂,事后重新看,发现其实就是代数,奶奶的,感觉自己还是有点傻。
二分图
还有一道二分图,24 个顶点,问最多能有多少条边。
假设二分图两边分别有:
x
和:
24 - x
个顶点。
那么最多可以把左边每一个点都和右边每一个点连起来,所以边数为:
展开:
这个二次函数在:
的时候取得最大值。
所以:
也就是左右两边尽量平均的时候边最多,讲解看完以后觉得很顺,但是坐在考场里的时候,前面已经连续做了一堆完全不同的题,再突然切到图论,脑子就没这么清楚。
那段随机划分
程序阅读里面还有一道随机划分的程序,考试的时候我没有马上看出来它到底想干什么,后来对着讲解才发现,它其实很像快速选择。
每次找一个 pivot,把数据划成两边。
但是和快速排序不同,快速排序需要两边都继续处理,而这里如果只是寻找某个特定位置的元素,只需要继续进入:
包含目标位置的那一边
所以平均情况下复杂度可以做到:
但是如果每次 pivot 都选得特别差,划分一直极端不均衡,最坏还是会退化到:
这些东西老师其实讲过。
但是考试的时候代码换了一种写法,又夹在一大段程序里面,我就没有马上把:
随机划分
+
只递归一边
和快速选择联系起来。
这个问题后来想想还挺明显的,我学过这个东西,不等于我换个壳以后还能马上认出来。
那道长得离谱的字符串程序
还有一道很长的字符串程序,这个我考试的时候看得相当迷糊。
里面自己写了类似:
Map
Queue
的东西。
两个队列来回跑,又是一堆字符串旋转、状态记录和判断。
第一眼就是:
这代码怎么这么长,然后看着看着就开始丢状态。
后来对着讲解重新看,才发现其实是在做:
双向搜索
也就是:
初始状态
↓
往前搜索
目标状态
↓
往回搜索
两边同时扩展。
如果其中一边新产生的状态,已经在另一边出现过,就说明两条搜索路径碰到了。
然后把:
左边走过的步数
+
右边走过的步数
加起来。
现在重新看代码,那两个队列和两套状态记录其实已经把思路摆得很明显了。
但是第一次在考场里看到这种写法,脑子根本没有往:
双向搜索
上面转。
最后一道完善程序
最后一道完善程序还是难。
题目给一个整数序列,定义:
然后从里面选一个子序列,让相邻两项异或以后得到的分值总和最大。
最直接当然会想到 DP。
假设:
dp[i]
表示选到第 i 个数作为当前结尾时能够得到的最大分值。
那么最直接的转移就是:
但是:
n <= 40000
如果每一个 i 都把前面的所有 j 扫一遍,复杂度就是平方级,肯定太慢。
讲解里面真正关键的地方,是利用每个数只有16位,把:
高8位
+
低8位
拆开。
然后再维护额外状态,把原来:
枚举所有 j
的过程压掉。
题目其实已经给了“把前后位分开计算”的提示。
我考试的时候看到这个提示,也知道大概应该:
利用二进制
拆位
维护一些东西
但是知道方向和真的把那几个空补出来,中间还是差得非常远。
做到这里的时候,基本已经属于:
能推一点是一点
不会就猜
了。
会写代码和会读代码
把整张卷子重新看一遍以后,感觉挺奇怪的。
有些题只要把讲解摆出来,就会觉得:
原来就这样?
但是把讲解拿掉,再把自己塞回那个考场里面,完全又是另一回事。
老师讲过,自己也做过题,这些都不代表换一种写法,塞进一张陌生卷子以后,我就一定能马上认出来。
尤其是纸笔程序阅读。
以前没有特别强烈地感觉到:
会自己写代码
和:
没有电脑的情况下
把别人写的一大段程序完整读下来
确实是两种不完全一样的能力,自己写的时候,整个思路本来就在脑子里面。
但是读别人代码的时候,必须反过来从:
变量
循环
递归
数据结构
状态变化
里面重新猜出:
他到底想干什么?
CSP-S 第一轮一下把这个问题暴露得非常明显。
第一次就这样了
不过考试出来的时候,第一反应其实没有特别难受。
更多是:
哦,原来真正的 CSP-S 就是这个样子。前一天还把校服外套脱掉,混进一中找考场,第二天一个人站在人群里面候场。然后真的坐进去做了两个小时,昨天成绩出来,确认第一轮就挂了。
当然可惜,但好像也没有什么不能接受的,毕竟第一次本来就有很大一部分是在试试看。
能从平时的学校里面跑出去,去参加一场自己确实喜欢的东西,本身就已经挺有意思,我没有想太多保送,也没有什么一定要靠这个比赛证明什么的任务,就是想去,然后就去了。
至少现在:
卷子见过了
考场坐过了
程序读过了
题也蒙过了
初赛也挂过了
下一次再来,就不是第一次了。

















这一切,似未曾拥有