CSP-S2024 游记

DengStar

2024-11-06 21:38:42

Life & Travel

CSP-S2024 游记

洛谷博客不能解析 html,可以在博客园中查看

Day -\infty

比赛前停课了两周,大部分时候都待在海南热带海洋学院的图书馆。开始的一两天还比较自律,后来一天比一天摆了。

赛前的几天 vp 了一次 CSP2021(听上去有点搞笑,但我确实没有做过这些题),发现 T1 只会暴力,心瞬间凉了。一想到几天后我就要参加最后一次 CSP,而我还是这么菜,要掉小珍珠了。稍微平复了一下心情开了 T2,想到了一个 dp,没怎么想清楚细节就直接开码了。码完后发现连样例 1 都过不了,缝缝补补了半天才总算过了,当看到输出和 ans 一样时可以说是如释重负。但最后模拟赛的结果也不甚理想。

这场模拟赛让我对自己的参赛状态感到极大的不自信:我发现自己的思维能力极弱,CSP2021 的 T1 和 T3 都算是比较简单的题,只需要一点灵光(特别是 T1,我看了题解之后感觉恍然大悟,但自己就是做不出来)。如果今年的 CSP 也在 T1 放这种需要灵光乍现的题目,而我不幸没能对上出题人的脑电波,那我不是完了?并且在这几天的训练中我发现考试时能否做出 T1 对我的心态影响极大。如果快速地做出了 T1,手上有分了,心里就不慌;如果想了半天还是只会暴力,心态就会一崩到底,后面的三道题也会彻底寄掉。想到这里,脑中已经把自己 T1 不会做,然后全场只有暴力分的坏结局给预演完了😅虽然在海南 CSP 只要不爆零就可以进 NOIP,但学了这么久,要是真的发挥成这样,然后感谢海南省的平均水平让我过线,真的可以跳楼了😅😅😅

事已至此,只能期望 CCF 多整点简单题,让我多水一些分。

<center><i> 考试前一天的夕阳。台风来临之际,天空中绽开了最绚烂的色彩 </i></center>

Day 1

对待最后一场 CSP,还是得放尊重点。早早从家里出发,在海中旁买了瓶冰红茶和一包奥利奥,以免考试时饿到自己。然后发现来的实在有点太早了,在海中的走廊上对着几棵摇来摇去的树看了几十分钟才进场。

(PS:最近台风要来了,那几棵树的树干都很细,在风中晃来晃去,感觉都要断了)

进机房时才两点,还有半小时才开考,这些时间足够我把缺省源打好,然后稍微配置了一下我习惯用的 Sublime。打代码时发现心中还是难掩紧张,手感觉有点发软。

开考后,对着 T1 沉思了 10 分钟。一开始以为是要求最多能把序列划分成多少个最长上升子序列,这不是 导弹拦截 吗?但又发现不对劲:这题中的序列可以随意排序。进一步思考,突然感觉对上出题人的脑电波了:只需找到众数的出现次数就好,感觉挺正确的。代码超级好写,写完马上过了所有样例,此时才过去了 15 分钟,梦幻开局!这 15 分钟拿的分数已经和去年一样高了 赛前祈祷 CCF 放点简单题,没想到它真放啊,还这么简单,开始时的紧张情绪已经消除了大半。

顺序做题,继续看 T2。题面很长,细节似乎有点多,但感觉很可做。第一个询问是好做的:对于加速度非负的车辆,在最后一个测速仪判断其是否超速;否则在它进入主干道以后的第一个测速仪判断其是否超速,这可以用二分查找。于是快速码了这一部分的代码,肉眼比对了一下,应该是过了所有样例(只看输出的第一个整数)。回头继续想第二个询问。显然对于每辆车,如果它超速了,能测出它超速的测速仪形成一个连续的区间,这是容易预处理的。之后怎么计算最少要留下多少测速仪呢?很快想到一个贪心:按顺序枚举每个位置,如果它是某个区间的右端点,并且这个区间内还没有任何测速仪,那么这个位置必须要有测速仪。(好吧我忘了我是枚举位置还是枚举测速仪了,现在看似乎枚举测速仪就可以,但我怎么记得我枚举了位置?想起来了,我是枚举了位置,感觉有点傻)而判断区间内是否有测速仪可以用树状数组。这样,单组数据的时间复杂度是 O(L + m \log L)。代码实现的细节有点多,但我居然没有遇到什么困难,稍微调试了一下就过了所有样例,并且最大的样例只跑了 0.58s,时限有 2s,非常稳。此时才过去一个半小时,我已经手握 200 分了,再也不用慌了。

剩下的时间就打得特别拉跨了。看了 T3,隐约感觉可以 dp。然后想到了一个状态设计:设 f(i) 表示 i 染成红色时,前 i 个数字的最大得分。根据这个状态设计可以得到一个 O(n) 的转移:f(i) = \max_{0 \le j < i}\{f(j) + val(j + 1, i)\},其中 val(j + 1, i) 表示 [j + 1, i] 染成同色时的贡献。val 可以预处理,这样总时间复杂度是 O(n^2),写完就有 50 分,而且我感觉很有继续优化的潜力。这时我仿佛已经看到 300 分在向我招手了,哐哐开写。写完发现样例 1 都过不了,愤怒地检查后发现做法假完了:没有考虑到 [j + 1, i] 中蓝色点与 [1, j - 1] 中蓝色点的贡献。思考了半天之后尝试给这个做法打个补丁:设 f(i, j) 表示 i 染成红色,且 j[1, i] 中最后一个蓝色点时,前 i 个数字的最大得分。照着这个思路,我发现转移的总时间复杂度居然是 O(n^4),和 O(2^n) 的暴力一样只能过第一个 Subtask,而且细节特别多,完全没有前途,彻底怒了。于是打完暴力之后跑路,去看 T4。

T4 更是阅读理解题。看完这一坨题面之后,研究了半天,发现 A 性质是容易的:由于没有新引入的参赛者,每一局的胜者都是确定的。那么只要把比赛的树形结构建出来,dfs 一遍,就可以做到 O(n) 预处理和 O(1) 查询。B 性质似乎也是容易的,冠军也是唯一确定的。哐哐开写,结果,妈的,没写出来。这东西的细节比我想象的要多,一直因为某些神秘原因 RE,最后也没搞懂为什么,爆零辣!

总结:虽然还是有些遗憾(T4 的部分分没写出来),但比起之前已经进步很多了。作为新赛季的第一场比赛,算是开了个好头,希望 NOIP 能发挥得更好。其实能考 200+(如果不挂分的话) 多少还是有点运气成分,我的思维能力较弱,但本场比赛的 T1 我很快想出来了,T2 也没什么思维难度,算是比较适合我的题。NOIP 可不能把希望都寄托在运气上,还是得多练,特别是锻炼思维能力。

一些疑问:220 在海南能排到第几?

题外话:

  1. 发现 T3 可以设 f(i) 表示 ii - 1 异色时的最大分数,这和我的状态设计简直就是一步之遥,操!赛前写了这么多 dp,赛时还是只会打暴力,我服了呀。
  2. 由于台风影响,周六回不了三亚了,周日上午的票还没了,买了下午的票,其中有一半时间我得站着,这下乐了。不过正好可以找个借口晚上不回学校。

UPD on 11/6:就是 220,一分不差。有道小图灵预计全省排名第四,而第一名是 300 分。