CSP J/S 2021 游记

· · 个人记录

写在前面

初中 OI 生涯的最后一场 CSP 了,时间过得好快,感觉初一第一次信竞课好像还历历在目。

虽然每年无论在代码上、算法上还是在思维上都会有很大的进步,但是对于一些不好想的题目还是做不到手到擒来啊。。。路还很长啊

J 组是最后一场了呢……那就写篇游记记录一下吧。

更完就去搞 whk 吧。

考前一周

校内罕见的集训,每天晚自习都可以自愿申请留校,而且还免掉部分作业!

太阳真是打西边出来了(

那不用说啊,肯定申请啊

周一打了一场友校同学出的模拟赛,唔,充斥着 int128 和板子的气息,比赛体验……一眼难尽()最重要的是写分层图数组还开小了……3M+2N 的空间硬生生的被我开成了 3M,鉿鉿

周二练了练树剖,平衡树,网络流之类的板子,感觉状态很不错,思路啥的挺活跃的,还和同机房的大佬们讨论了很多 trick。

周三周四翻了翻之前的一些笔记,感觉快忘光了,收获蛮大的 ,不过没考就是了本来还想着再复习一下 AC 自动机,2-SAT 之类的,但是想到绝对不会考就没再看。

周五感觉有些迷,不知道该干啥了,有点慌,就开始翻 oi-wiki,复习了一下树上的基础知识,学了学什么启发式合并,感觉十分玄学,看了看虚树什么的,虽然没有看懂,然后打了个期望 dp 的蓝题,还没有调通一直玄学挂分,回到家才发现是方程手残有一个细节打错了(

总体来说状态不错,写题的时候还把所有的坑基本上都踩了个遍(,也使得我 pj 比赛的时候慎之又慎。

集训万岁!免作业万岁

CSP-J

一大早就起来了,特地剪了个指甲洗了个头,增加 RP qwq!

吃完早饭就坐车赶去河工大了。路上拿了电脑还刷了两道橙题,发现不会做(bushi)

进了走廊,还在考场外等了半个小时,差评,拿出手机又翻了翻板子,感觉还不错。

$8:20$ 第三次 CSP 了当然有经验,第一时间下载好了 Dev,并打上了快读板子放到了缺省源里面。 $8:25$ 试图打 Dijkstra 板子未遂,被监考老师口中的网址打断了,于是就前往网址下载试题。 $8:30$ 打好了对拍文件夹,信心满满。 $8:33$ 试题解压成功,正式开始做题!~~然而我旁边的那位同学正在问监考老师在哪下 dev~~ $8:40$ 发现第 $1$ 题就是个数学题,写了个 $\min$ 两行搞定。开始看第 $2$ 题。 $8:50$ 第 $2$ 题读到了关于操作 $1$ 次数的限制,内心狂喜,自然地想到了 $O(n)$ 操作 $1$ 维护答案,$O(1)$ 操作 $2$ 直接输出的做法,简单想了一下发现十分可做。 $9:10$ 第 $2$ 题写完,过了前两个样例,第 $3$ 个样例卡住了,仔细想了想应该是插入排序对于相同大小的元素输入顺序小的应该在前的缘故,于是判断时将 $id$ 作为第二大关键字就过了。 $9:30$ 开始看第 $3$ 题,发现和预料中的 dp 大相径庭,全然就是一副橙色萌萌字符串模拟的样子,根据判重就想到了 map 维护,然后就开始乱搞。 $9:40$ 代码大体部分写完,但是分别在第二、第三、第四个样例卡住了,~~良心大样例~~,于是加了对于不规范字符串关于两个标点连在一块、数字的前缀 $0$,冒号后没有数字以及第一个点前面没有数字等各种各样情况的讨论,写了几十分钟最后在对拍样例四输出和答案无误时喜极而泣( $10:00$ 开始 T4,读完题目又喜又惊,喜的是感觉题面很简单易懂,显然链表维护,惊的是怎么可能这么简单身为普及组 T4 一点算法都没有。 $10:10$ 链表做法写了会发现细节不太会写(大雾),观察数据范围发现 $log$ 做法也可,于是开始想 $log$ 做法。想了一会发现对于一块 $0$ 消失之后,它周围的两块一定是 $1$,并且 $1$ 中间就没有任何 $0$ 了!(废话),所以完全可以~~写一个平衡树~~用两个 set 分别维护 $0$ 和 $1$,每次询问不断找当前 $0$ 后面的第一个 $1$ 和当前 $1$ 后面的第一个 $0$ 即可,而且非常好写。 $10:30$ 四道题全部写完并且过掉大样例啦!史无前例!内心狂喜但还是按捺下来,毕竟题目简单意味着大家普遍分数也会很高。开始检查。 $10:40$ 听说代码放到 C 盘电脑重启后会丢,吓得我赶紧将代码备份了一份到 D 盘。~~你可以永远不相信CCF的机器~~ $11:00$ 对于每道题将考前一周犯过的所有错误和进入考场前翻过的教训版全部代入检查,由于怕 cin 和 puts 冲突,还特意将第三题的输出改为了 cout。 $11:20$ 又对于每一道题测了大样例,并对于每一道题测试了 freopen。 $11:30$ 再次检查每一道题的代码思路,寻找漏洞。 $11:40$ 压缩代码,删除多余 exe 文件,检查 freopen。 $11:50$ 线上线下提交代码。 $12:00$ 普及结束。 出来之后和同机房大佬讨论了讨论做法,发现应该没有写假的。 **预估分数:** $100+100+100+100=400

考前不敢想系列

不过同机房还有其它 AK 巨佬 orz

中午吃了盖浇饭,真香,在车上睡了一觉就又回考场了。

CSP-S

下午的机房好挤啊QAQ

一到考场还是先打了快读板子,然后码了一遍上午未完成的 Dijkstra(bushi)

第一题第一眼发现暴力十分好写,于是直接开始暴力然后暴力调了30分钟。打完有些慌,就没想正解,直接开始看第二题。

第二题看到了一大串括号,直接想到了 dp,但是总感觉 dp 状态不好设(md我为啥不往区间dp想),就开始暴力,然后发现递归暴力不会打心态崩了/fad

滚去看第三题,发现十分可做,然后发现可以从左右选一个方向切入然后内外一起递归,暴力调了半个小时走人。感觉能得 60 左右。

第四题看到了很开心啊,感觉像最小割,但是发现还有额外点这个东西还指定了颜色。。。然后又想到了 dp,更开心了,还设 dp_{i,j} 表示点 (i,j) 的答案,试图从上到下,从左到右进行转移,调了一个多小时发现假了,这么转移并不是真正的答案,于是心态崩了。当时大脑一片空白,有种无力回天的感觉。

又开始尝试写第二题暴力,未果。当时已经完全忘记第一题了,只记得第一题已经拿到分了,不断的在调第二题和第四题,想拿个暴力。但人生有的时候就是这么奇怪,越想拿什么越得不到,真正如果心态放平一点不要慌去写第一题反而就好了……

很快就只剩十分钟了,匆匆忙忙压缩代码提交代码一气呵成,全然没有了上午的潇洒与自然。提交之后我的心里一片茫然,大脑一片空白。无助地点开扫雷,双目失神地瞎点起来。提高组,就这么废掉了。

预计得分:

40+0+(40-60)+0=80-100

赛后 OJ 评测

普及组:

洛谷: 100+100+100+100=400

计蒜客: 100+100+100+100=400

提高组:

洛谷: 40+0+44+0=84

总结与反思

这次 CSP 算是收获颇多吧,他让我再次深刻认识到了自己在思维题上的不足。

以前一直在推算法,可能算是已经推到了一些基础的省选和国赛算法了吧,可是那有什么用呢?遇到一些 dp 甚至几乎什么高级算法都没有的题目不还是不会做、无从下手吗?说句不好听的,你配那些算法吗?不考算法的思维题都不会,你还真的打算只做板子题啊?

以后还是多刷些杂题吧,,,算法方面就暂时先不推了,毕竟学那么多也用不到不是?现在学的基本上在未来一年都够用了,就不要在好高骛远了QAQ

希望可以通过这次比赛更上一层楼!

不过话说回来,准 AK pj 还是很高兴的qwq

也算是初中 OI 的一个圆满的答卷吧。