专栏文章

蒟蒻 の CSP 2025 游记

封封禁用户
生活·游记参与者 5已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@minel2wm
此快照首次捕获于
2025/12/02 01:08
3 个月前
此快照最后确认于
2025/12/02 01:08
3 个月前
查看原文

CSP-2025游记（总结）

绿勾了一年终于要一雪前耻了！

Day-0

倒是没有感觉特别大的压力啦，不过最后一场模拟赛居然T3爆0！这给我极大的不安感......
晚上精神状态：啊！Manacher我忘了，快复习！！！ 啊！平衡树我不会，赶紧学！！！啊啊啊啊什么啊。
晚上睡觉不知道怎么个事压力一下子就飚上来了，好可怕好可怕，还好听宝宝巴士睡着了。

Day-0.5

早早起床来到机房，结果发现别人全到了，好家伙一个比一个卷 早上也没什么时间的说，随便开电脑翻了翻发了亿点RP++就准备 入场了！！

Day-1

CSP-J

考前心中默念：AK...AK...AK...
拿题一看：666一年比一年水 30min30min 就做完了还写什么总结....
预估分：100+100+100+100=400pts100+100+100+100=400pts
实际得分：100+100+100+100=400pts100+100+100+100=400pts

CSP-S

坏了我们机房全是大佬，压力！！！！！
刚拿T1那一刻直接给我上午打来的自信全干完了，怎么感觉有点小难，瞅了一眼数据范围，发现 nn 很大，猜测是贪心做法，随便推了推发现可以从最优策略调整， 20min20min 打完T1拿到 100pts100pts 。
打完T1想起要先看题的说，先把后 33 题的题目看了一眼，感觉T2很可做（不可做我可以退役了）显然在确认点集的情况下的最优解就是 MSTMST，又发现 kk 很小暴力 2k2^k 枚举点集即可做到 O(2kmlog⁡m)O(2^km\log{m}) ，复杂度太大，显然过不了。但发现 nn 较小，于是把一开始的 MSTMST 先保留，再对每个点集跑 KruskalKruskal 可以做到 O(2kknlog⁡n)O(2^kkn\log{n}) ，沿用刚才思路，对于每个子集保留 MSTMST ，做到 O(2k(k+nlog⁡n))O(2^k(k+n\log{n})) 。 不太对劲啊，这好像不太能过的样子，思考5min5min想到瓶颈在于排序，而每次求出的 MSTMST 都是一个有序序列，如果将点的连边也提前排好序，两个有序序列就可以做到 O(n)O(n) 合并，于是简单预处理即可做到 O(2kn𝛼(n))O(2^kn𝛼(n)) . 感觉 1s1s 还是有点不太行，不过应该能过了，反正大数据只用了 500ms500ms ，没什么大问题，此时过去了1.5h1.5h ，拿到 200pts200pts 。
还有时间，T3看上去也比较可做，尝试一下。一开始题目看错了，以为是换了一次还能继续换问方案数，那 si,1=si,2s_{i ,1}=s_{i ,2} 不成无限种了？过了一会才发现看错了，原来只能换一次，那就好做了，很容易想到字符串匹配，找到极长的一段不同的子串，现在能换的充要就相当于满足存在一个 sjs_j 的子串使得 sj,1s_{j,1} 的这一段与 ti,1t_{i,1} 匹配，sj,2s_{j,2} 的这一段与 ti,2t_{i,2} 匹配，并满足其他地方都相等，哈希判断可以做到 O(nq)O(nq) , 拿到 250pts250pts 。容易发现 sjs_j 的极长不同子串长度也必须相等，因此可以对极长不同子串哈希对相同哈希值单独判断，复杂度降了很多，O(q×玄学)O(q\times玄学) ，拿到 [250,270]pts[250,270]pts ，此时还有 2h2h 。
然后我就糖了！瞪了半天想什么字典树啊树上差分啊，双字典树怎么匹配啊！！！瞪了 1h1h 没想出来，换了换思路，诶！既然除中间以外都需要满足相等，那不就是字符串匹配？？？有道理，把中间替换成#，跑 ACAMACAM ，哇我太聪明了，赶紧打了出来，此时还有 30min30min ，前面数据都过了，大数据也差不多，哇塞！300pts300pts ，保险起见，先打个大数据对拍，怎么错了......欧布！虚空调试20min20min终于在比赛快结束前发现手残写了个跳到根节点就返回......欧克，极限调出T3，复杂度 O(L1∑)O(L_1\sum) ,瓶颈在于...初始化？？？不管了，跑不满，拿到 300pts300pts 。
T4,em...暴力都没来得及打就Over了，早知道打快点，中间不摸鱼还能再拿 20pts20pts 暴力，加容斥+m=n 高达整整 36pts36pts 啊！！！
预估分：100+100+100+0=300pts100+100+100+0=300pts
正常发挥：100+100+70+36=306pts100+100+70+36=306pts
超常发挥：100+100+100+36=336pts100+100+100+36=336pts
实际得分：100+100+100+4=304pts100+100+100+4=304pts？？？神秘T4我最后一分钟输出了个00给了我4pts4pts？
结果乍一看感觉还不错？但其实蛮有问题的，T3有赌的成分在里面，我赌我能调出来，万一没调出来不仅T3扣 50pts50pts ，T4暴力我也没拿，赛场上千万不要学我，求稳才是最正确的，而且在我调很久都调不出T3的时候应该果断放弃，T4暴力+m=n特别简单，最低得分也可以达到 100+100+50+24=274pts100+100+50+24=274pts 而且还能留出很多时间，显然是比打T3正解含金量要高得多，此时再想到容斥可以再拿 m=1m=1 的点，+12pts+12pts ，打T3性质B，+20pts+20pts ，最低得分 306pts306pts 。
所以说暴力是特别重要的！！！！ 特别是CSP，一般都会给特别多部分，一定先拿部分分！

Day-2

赛后才是压力最大的说，于是我在家玩了一整天

题外话

  1. 不是T3T4是不是放反了啊，T4比T3好写多了啊...很自然的一道计数
  2. T234都有点小卡常，T4还好，CCF全开1s1s真的没问题吗？
  3. 听说一大堆人没判∣ti,1∣≠∣ti,2∣\lvert{t_{i,1}\rvert}\ne\lvert{t_{i,2}}\rvert ? 还好我判了，默哀默哀

upd：合着根本没有 ∣ti,1∣≠∣ti,2∣\lvert{t_{i,1}\rvert}\ne\lvert{t_{i,2}}\rvert 啊？

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...