CSP-2025游记

· · 生活·游记

Day -1

在家休息，让 Chatgpt 找了几道分类讨论的题写了写。

Day 0

上午啥也没干，摆摆摆。

中午出发，发现手机没电了，于是乎蜘蛛纸牌接接接。

下午到了酒店，感觉打板子没用，于是复习编译选项以及常见tricks，一车人在我房间耍。途中尝试跟 S08577 联机 MC，发现 S08577 的菜鸡电脑啥都带不动，遂放弃。

发现酒店的饭不如 wfyz 一根，随便吃了点就找 quyuan 点了外卖。

然后去试机，感觉机器特别好用啊，敲个线段树试试。欸怎么重启了，我们的系统跟考试不一样说是。重启之后文件都没了，就懒得再写一遍了，只是把所有按键都试了一遍没问题就离场了。

Day 1

上午爽睡到 7:30，吃完饭回来就稍微复习了一下，然后被 S08577 通知去 tianruihan 的房间，于是随便收拾了一下，然后去玩了会。

吃完午饭也不想睡觉，发了会呆就到点了，然后下去集合，尝试预言必考线段树。

进考场开题，看了眼第一题，欸怎么这么难，先想想没限制不就是全选最大的，那就至多只有一个是 > \frac n2 的，那直接把最大减次大放三个 set 就做完了，于是马上开写，写完很快就过了大样例，此时我同桌还在问压缩包密码是啥。

然后看第二题，怎么题面这么混乱，怎么城市跟乡镇混着用，他本来不就是城市，怎么还要城市化改造。先去看看第三题，看第三题发现只有可能是 i 不相同，不可能是 x,z 不相同，然后就是直接把两个串最长公共前后缀找出来，然后匹配一下，发现暴力有很多分，于是回去看 T2。

先按照乡镇就是前 k 个城市来理解吧，那就是直接 2^k 枚举改不改造，然后把新的边和原图最小生成树上的边混一块再做一遍最小生成树，那就开写。

欸小样例怎么没过，欸他怎么 1 向 1 连边，哦原来乡镇是独立的，那直接把编号改成 n + i 就行，一遍过了大样例，但是我并没有用归并，因为相信 CCF 神机。

吃个士力架，嗯嚎吃。

然后看了看第四题，设了好几个状态都假了，然后发现只会状压，便回去想第三题。

想想，欸我之前怎么会的是 O(L^2)，L^2 怎么分这么少，想想还能怎么做，哦那我只把公共后缀取出来，然后枚举前缀的长度，那左端点就固定了，然后只需要使得公共后缀相同就行，然后总共只有 n 个，所以就是 O(nq + L)，写写吧。欸不对，样例二怎么有个长度不相同的，这是啥阴，长度不同不是一定不行吗，让我想想，哦对啊，这不是直接输出 0 就行了，为啥放这种没用的数据啊。

吃个士力架，嗯嚎吃。

写写写，要用哈希懒得双了，就用单哈希吧不会卡的，写写写怎么还要用 map<pair<int, int>, int> 要不要离散化一下然后少一维，算了反正是暴力，写写写，好前两个样例过了，欸第三个怎么寄了，这怎么调，自己写一个比较程序吧。

然后找到是第 101 个询问不对，输出了一下，发现很多串都有这个子串，这我怎么找，欸我怎么输出 0，哦我后缀怎么求得是询问串的后缀，应该从前缀往后延伸的，改完对了，欸怎么跑这么快，不管了应该过不去。

吃个士力架，嗯嚎吃。

现在还剩 1.5h，想想还是先写特殊性质吧，第三题只有特殊性质 B 没写，发现这个只需要满足前缀且后缀长度比询问的串小就行，那我直接提前排好序然后二分就是喽，写写写，怎么挂了，再次使用比较程序。

哦原来是没有元素的时候会一直 continue，不会触发 break 导致寄了，那就先 break，好过了，怎么跑的没暴力快，不管了。

吃个士力架，嗯嚎吃。

现在还剩 1h，先写第四题暴力吧，没怎么调就过样例了，此时还剩 40m。

继续尝试思考第三题，发现可以直接把中间不同的那一段删了，然后把相同前后缀拼起来，中间隔开，然后把中间相同的分成若干等价类，然后每个等价类就相当于统计有多少串是询问串的子串，这不就是AC自动机板子。但是感觉写不完了，于是看了眼第四题把 n=m 写了，然后就摆了，开始肉眼调试四道题。

发现第三题特殊性质判错了，改了改，然后到最后也没看出来啥其他的。

出考场没碰到熟人，然后就直接往巴车方向走，也没看到老师，然后看到了 Dtw，他说第二题不归并会被卡，感觉有点可能不过还是相信 CCF 神机，然后又碰到了 xuyunao，他说 xz001 因为运气不好，导致电脑炸缸写不了代码，浪费了几个小时，可能去不了 WC 了，默哀。

然后去到大巴随便吃了点东西就摆了，发现大家有点炸缸，而且好像有人每判第三题长度不相同。

后记

早上起来一看，哟云斗这么速度，发现自己没挂分，很开心。

在其他平台上测了测我的码，发现第二题很可能就是会被卡到 80，第三题得分在 [70, 90] 之间。

然后跟 S08577 聊了聊发现他第一题挂成了 5 分，感觉非常神秘，仔细一看发现他第一题判特殊性质判的是只要有非 0 的就执行特殊性质，全是 0 才是 n^3 的暴力，然后挂飞了，只有 n \le 200 并且 b_i, c_i 全等于 0 的这一个点有分。

发现很多人第二题读错题之后数组开小了忘改了。

NOIP 加油吧