CSP 2025 游记

· · 生活·游记

Day -inf

笔试 AK 了，很有实力。

怎么学校的运动会在 CSP 前两天举行啊，彻底怒了。

Day 1

在 bs 的一机房，是 Windows11。

只参加 S 组。

T1 10min 就会了，比较简单。

T2 首先发现最小生成树可以边加边边做。然后用归并排序就可以做到 O(n2^k)。

T3 花了 1h 才想到可以把最长的前后缀去掉，然后剩下的得一样。相当于 x+'#'+y+'#'+y'+'#'+z 做匹配。赛时忘记 ACAM 怎么写的，所以枚举 x 的长度，然后 y 的部分可以建立 Trie 树，询问时使用二分找到第一个有值的祖先即可（需要用哈希表）。时间复杂度 O(L\log L)，主要看哈希表的常数了。

T4 设 f_{i,j,k} 表示前 i 天中，有 j 个人没选上，有 k 个位置满足耐心度小于等于 j。注意我的状态不考虑耐心度大于 j 的位置，这些位置显然可以在最后计算。

转移是简单的，但是 s_i=0 的转移写错了，所以只有 32 分。

预计 100+100+100+32，不是很差，但是 T3 有概率挂分啊，只有寄希望于 CCF 神机了。

出来一问怎么 AK 一车，这下很爆炸了。

赛后发现 T4 且只有一个转移系数写错了，并且时间复杂度可以被分析到 O(n^3)，改改就过了。痛失 S 组 AK/ll。

赛后发现 100+100+80+32=312，T3 的死因如下：

  1. hash 数组预处理太小了
  2. map<pair<pair<int,int>,int>,int> mp

就这样了。