上次写竞赛游记还是高二呢,但和高中时偏向竞赛总结一样的“游记”不同,这真的是一篇游记了。因为这次参赛过程真的就是在旅行中度过的(笑),不过文章里还是有很多对参赛的帮助的,各位想参加CSP和CCSP的朋友也可以认真看看,相信也能有不少收获。
一次随意参加的CSP认证
高中时有幸参加了最后一次NOIP2018,当时因为三道题爆零导致差5分而没拿到省一,等到第二年NOIP就被取消了,而是改成了CSP-J/S认证(都是CCF为了收钱啊),OIer中很多人都说“CSP认证多水啊,以后信竞还有没有含金量啊”。但我到大学大一参加CSP认证的时候,发现题目其实并不是多么简单,从T1到T5那是真的普及到省选的跨越,最后我也只拿了300分,刚刚摸到及格线了算是。
之后因为疫情、封校等原因,CSP认证也没有正常展开过几次,等到大三下终于恢复正常,团报的名额异常火热,稍微晚点就抢不到,而没有团报要200块钱(CCF你搞认证就是为了收钱吧)。所以直到大四上,也就是刚刚9月份这次,我才终于又参加了第二次CSP认证考试。这次报名前,班上一个大佬还问我:“你不都参加过一次了,再说现在参加这个又有什么作用呢?”是啊,好像也并没有什么作用,但可能就是为了给我的算法竞赛之路画上一个句号吧,我还是参加了这次认证,但也正是如此,才有了之后更多的精彩。
入选校队和赛前准备
这次CSP认证出乎意料的顺利,T1和T2都是简单的前缀和,T3是个大模拟。而在区分度较大的最后两题,T4是一个数据结构,我并没有什么思路,当时已经只剩40分钟,就在我以为这次又得300分结束的时候,我发现T5和NOIP2018的保卫王国几乎如出一辙,一样的树上DP,一样的单点修改,甚至连子任务分布都极为相似,所以我当场断定,这题一定是动态DP,虽然写不了正解,但是凭借记忆,我还是很快完成了60分的子任务,最终凭借着本次CSP的360分,我被学校CCSP队伍选中,获得了参加CCSP2023的资格。
入队以后,我们每个成员负责分析一道CCSP历年题目,并完成报告。我负责研究CCSP2021的抽卡(题解点这),但其实我并没有花很多时间在研究题目上,因为当时正好是中秋国庆假期,我已经回老家了。而且还先后去了曲阜、济南、泰山、蚌埠游玩(所以我说是真的游记嘛),我是在从济南回家以后,中途休息了三天,正好完成了题解,7号晚上在线上会议讲完题,第二天就又和哥哥去爬泰山了。下山后又去我哥学校逛了几天,正好他宿舍室友不在,我就拿他室友卡伪装成学生进去,住他寝室里,成功省了一笔住宿费。等回学校已经18号了,离比赛也没几天,剩下的时间我就把历年题的标程在Ubuntu下调了调,熟悉下环境。我并没有去动手写更多的代码,其实也有一个原因是CCSP的题目大多难度不高,但是解题过程非常繁琐,所以我也建议大家在研究历年题时不要将过多的精力放在实现上,而是搞懂思路和流程就好。(这里放几张旅游照片,泰山还是很壮丽啊)
![](/img/CCSP2023游记/泰山-1.jpg)
![](/img/CCSP2023游记/泰山-2.jpg)
![](/img/CCSP2023游记/栖岩寺.jpg)
Day0
其实CCSP并没有Day0的概念,既没有热身赛,也不能提前试机,甚至连在考场门口拍照都不行,提前到达只是说为了养足精神。我们是中午从学校出发,下午四点到沈阳宾馆。接着去考场签到,顺便看考场,这时候就隐约感觉不妙,因为考场并不是想象中的大机房,而是一个类似会议室的房间,在里面摆了六七张大圆桌,每个桌子用隔板分成八份,各摆上一个笔记本。这环境可以说烂到爆了,人家蓝桥杯都是在机房,CCF收了这么多钱(CCSP报名费500)还搞这种比赛环境,也是真的难绷。
![](/img/CCSP2023游记/比赛环境1.jpg)
![](/img/CCSP2023游记/比赛环境2.jpg)
晚上教练请我们吃了铁锅炖,不得不说东北的大杂烩还是挺好吃的。
CCSP特色1-携带电子资料
回宾馆以后继续准备资料,这里就要提到CCSP很有趣的一点了,NOIP就跟高考一样什么都不给带,需要选手自己或理解或硬背的记忆模板,ACM则允许带纸质资料,减轻了记忆难度,而CCSP更进一步,直接允许带硬盘拷贝代码,并且比赛过程中硬盘可以一直插在电脑上,可以说完全没有死记硬背的要求。这其实挺好的,毕竟实际开发中也有那么多“Ctrl+C/V”的,花精力去背经典模板也没有什么必要。
Day1
试机
CCF设计的流程很捞,正式赛9点开始,8:00-9:00是试机时间,就是说提前一天试机不好吗。
真上手摸到电脑,发现之前的担忧果然没错,比赛电脑是联想的T480(具体是哪一款分不清),我也不多说什么,就简单列几个特点:
- 720P高清显示屏
- 87键包浆键盘
- 一键起飞的散热引擎
除去这些外表上的落后,实际使用的细节更是拉跨,首先是fn键正好和Ctrl反转位置,导致我总是在保存的时候按倒fn,它“fn+S”的快捷键还是截屏,比赛结束我看图片目录下面得截了90多张图。然后就是缩小的方向键,左右键的上方还是“page up/down”,每次按方向键都可能误触,然后就给我疯狂翻页。最最难绷的还是那个触摸板,它接触不良到就算我的手不碰电脑,鼠标都会在那一直乱窜,必须要使劲按几下触摸板才能解决,关键是我还找不到怎么把触摸板关掉,甚至后来都严重到要使劲锤触摸板才能让鼠标稍微乖巧一点。
上面还只是硬件,软件上提供了VSCode,看起来还不错,但是当我打开设置界面想调整一下,才发现设置全是空的,整个界面没有一个字母或图标,就算在搜索框搜索也找不到任何设置。后来还好找到了“settings.json”,凭借着记忆和自动补全直接编辑,把字体、格式化、自动保存等功能都打开了,不然就这破电脑加上白板VSC,还不知道得多难受。
![](/img/CCSP2023游记/比赛现场照片.jpg)
中间那个红色的就是我ヾ(≧▽≦*)o
CCSP特色2-超长比赛时间
这时候就要说一下CCSP的另一个特色了,就是远超大多数算法竞赛的比赛时间,CCSP要从早上9点持续到晚上9点,整整12个小时,期间CCF会负责提供中饭和晚饭,期间选手可以多次提交评测(每题最多32次),取最高分为最终成绩,最后两个小时封榜。
T1
开始后首先看T1(我就不写题目和题解了,想了解的看我校大佬的博客),题面非常啰嗦,但其实就是一个大暴力,依次枚举每个交换要不要做,每个礼包要不要买,再计算价值取个最小的就行。程序写好以后一发提交,结果95分!?接着开始调试,硬是调了40分钟也没找到问题。这总不能在一颗树上吊死,于是开始看下一题。
T2题面倒是挺简洁,当时隔壁的两位已经在研究T2了,我当时用余光瞥见他们草稿打的飞快,特别是左边那一位都用了两张草稿纸,上面写满了组合数,让我以为这是什么非常复杂的计数问题,想想NOIP2018的填数游戏,当时觉得还是不浪费时间了,于是打了30分暴力就先扔了。
T3
然后开始看T3,当时一看到那个“波动最大值的最小化”,我便立刻确定这题是二分答案,为什么呢?请看下图
![](/img/CCSP2023游记/NOIP2018D1T3.png)
因为对此一无所知,导致此题得分很低,当年差5分痛失省一
确定了二分以后,开始思考check方法,题目里那个“波动最大值”其实就是最长子序列问题,所以我猜就是每当最长子序列在哪个位置超了,就倒着往前依次给每个位置减D。这就体现出CCSP的好了,也不用管对不对,先打了再说,打完最暴力的程序,交上去成功10分,证明猜想没错。然后就是优化了,因为每个位置最多减一次D,可以套个并查集,拿20分,然后发现减D操作能差分维护,可以用树状数组,我直接从带的模板里掏了个封装好的代码粘上去,减去了手打数据结构的麻烦(所以说CCSP的赛制真的太舒服了)。优化完拿了40分,这咋才这么点?然后尝试了各种奇异的方法,提交次数都用了20多次,终于发现,减完D以后更新前缀和可以直接在单调队列里维护,加上这个操作,直接变成了80分,算是把$O(n \log^2 n)$的分全拿满了。最后20分应该是类似DP的做法了,因为已经3点多了,感觉继续熬T3不值得,就直接把这20分弃了。
T2
看了一下榜,发现T3大部分都是拿10分20分的,而T2很多都AC了,那说明T2难度并不大。于是又回头看T2,觉得可以直接用组合数学硬推,然后就从第二个子任务开始,依次推导每种情况的式子。出乎意料的是,我这次居然没画图也没打表,纯靠推把几种情况都搞出来了。大概一个多小时就把T2正解搞出来了,拿了95分,有个点超时,后来用记忆化的方式优化一下就行了。
![](/img/CCSP2023游记/草稿1.jpg)
![](/img/CCSP2023游记/草稿2.jpg)
整场比赛我就打了这么点草稿
CCSP特色3-系统设计题
这是CCSP和其他算法竞赛最大的差别,系统设计题并不考察高难度算法,而更像是去实现一个具体的项目,并且评分也和算法题不同,采用了“竞速”的评分方式,除了10分基础分外,另外90分需要和其他选手比拼程序运行的速度,并按照比例得分,只有最快的选手才能获得满分。(CCSP2023没有采用竞速评分)
T4
说到大模拟,搞NOIP的应该看过猪国杀,算是OI里模拟题的极致,我记得当时机房里很多同学都说等退役了要A了体验体验。或许还有人看过未来程序·改,不知道有没有人敢挑战,反正当时机房里每个人都对它望而却步。
这次的第四题,比“未来程序·改”还要复杂。平常的编程中,有各种变量类型,我们还会定义数组、结构体、联合来简化变成难度,而每个类型的长度都是不同的,将不同长度的变量装在结构体里,在分配内存的时候,就必须面对内存空间占用大小的计算,以及内存空间对齐的问题,第四题给出了一种定义变量的方式,要求写一个编译器,去完成对内存空间的分配。
编译原理课设可是写了两周才完成,考场上这点时间还写个毛。(清华大佬这题拿了51分,也是真的神)
T5
搞完T2时间已经到了五点钟,我才开始看T5,这题也不是什么善茬,起码在篇幅上直接占了一半,有19页长。
这题研究起来不像是个OI题,倒像是个阅读理解,需要在巨长的文章中找到与答案相关那几个点,最开篇出题人花了5页给我们科普了流处理系统的工作方式,其中唯一有用的就是时间窗口和watermark这个概念。别看说了这么多,其实也很简单:
- 时间窗口:一个统计的区间,每个到达的事件会被放到对应的区间里统计,出题人已经给出了分配区间的函数,我们只要调用即可
- watermark:一个时间标记,时间早于watermark标记的事件会被丢弃
任务一子任务一
前面5页纸其实就是要分析出这点东西,然后就是任务一,要我们根据事件的到达时间,生成watermark标记,具体的生成方式题目已经给了,我们其实就只要确定时间就行。这里其实题目描述的很迷惑,但我分析了样例,觉得它就是每十个事件取最大值,再减60秒就行。既然有了想法,肯定要先试试,反正就几行代码,然后成功拿下任务一。
任务一子任务二
有了子任务一的积累,子任务二更加简单,就是流从一个变成了两个,我们要按要求取两个流中最小的那个,再判断能不能输出,这样看不就是几个if的事。事实也确实如此,子任务二轻松解决。
任务二
任务二要求对流中的事件和watermark进行区分,事件按时间窗口存储到内存,遇到watermark则将存储的数据输出,也就是个普及组小模拟的水平,搞map嵌套就行(题目里也贴心的提示了)
任务三
任务三开始,出题人又细心的给我们科普了容错机制的内容,但归根到底,任务三和任务二基本是一样的,只不过是输出的时机不同,并且是输出到文件。这里就很有趣了,一个在线评测的OJ,居然还要文件读写,而且还是有的数据输出到标准输出,有的数据输出到文件。大家搞OI的时候经常用 freopen
,但是这改变了stdout,等输出完文件,你还会改回来吗?反正我不会,但还好在各类课设中我学会了多种文件读写方式,最终用 fopen
和 fprintf
解决了问题。
比赛结束
至此CCSP的比赛就全部结束了,整体上说除了电脑太烂,体验都还不错,部分分也很足,最后我是 95+100+80+0+100=375
分,整场比赛我都在金线上下徘徊,也不知道最终如何?
还有就是CCF虽然提供中晚餐,但那个盒饭实在是垃圾,如果各位谁体会过疫情封寝,那肯定会记得那时候盒饭的味道。我当时中午吃完,下午就感到恶心,晚上正好肝T5索性就没吃,结果回宾馆还是吐了一堆,也不知道是饭的问题,还是我泡的咖啡的问题。总之如果各位参加CCSP比赛,还是带点面包和压缩饼干吃吧。
CNCC(Day2)
参加CCSP可以免费参加CNCC大会,并且可以免费乘坐地铁,还有沈阳故宫等景点可以免费参观,可以说是非常赚了。上午签完到,我也没听报告,直接去景点转了一圈。不得不说沈阳故宫是真的小,建筑也不算豪华,旁边的张学良旧居比它要壮丽多了。
![](/img/CCSP2023游记/沈阳故宫.jpg)
![](/img/CCSP2023游记/张学良旧居.jpg)
左边是沈阳故宫大政殿,右边是张学良旧居的大青楼(这名字挺奇怪蛤)
下午是CCSP颁奖,我居然还蹭线拿了金奖,校队成绩也挺好,两金四银,排名第七,应该算是几次CCSP最好的吧。