CSP2025游记（谨慎观看）

· · 生活·游记

其实已经退役了，但是还是来稍微打一下。我已经料想到这一年里将会发生多么神人的事情，所以就稍微记录一下。总之在此提醒一下各位，接下来会记录一些非常诡异的事情，这可能超出人类的理解，忍住不笑的都是神人。但是还是希望你能选择耐心地读下去。另外其中可能会出现一些看似是批话的东西，但是我都经历了如此的事情了你就原谅我吧。因此感到不适请立即退出本文章，对此感到抱歉。还有就是以下真的是真人真事，千万不要因为过于神人就以为我虚构出来的神秘小说。

最近半年其实一道题也没做，一个代码也没写，因为在学习文化课。（其实文化课也没怎么学，主要还是以打解谜为主。）

很快就到了一年一度的 CSP，总之很快就进了考场。这次考场是我们学校的另一个校区，就在我们学校旁边不到一公里。但是我们入场的时候正好是我们学校放学的时候，然后出现了对流现象，有点草台班子。

然后就进考场了，比赛开始前一直在想上次省选 D1T1 文件名写错之类的事情，有点害怕了，总不能这次又出现神秘错误导致挂分吧。感觉于我而言就没有不挂分的比赛，希望这只是错觉而已。

但是很快我的思绪就被打乱了，因为我忘了那句改变输入输出流效率的神秘指令到底是什么，只记得是 ios:: 开头，但是很明显，基于我多年的 OI 经历，这段代码早就成为肌肉记忆，现在想不起来敲代码的时候自然就想起来了，但是果真如此吗。总之后面还有两行，cin.tie(0); 和 cout.tie(0);，至少这两个还记得，输入效率的要求应该没那么高吧。

很快比赛就开始了，我打开了题面，一下就被谐音替换的题目名吸引了，打解谜打多了是这样的，但是没咋看所以没看懂，没看懂所以没咋看。最后还是选择了顺序开题。

看了眼第一题，一看就是水题，总感觉贪心就行了，仔细思考片刻，发现只需要把超过 \cfrac{n}{2} 的那个部门选几个人换到别的部门就行了，但是如果其他部门再超过怎么办呢，我没仔细想，就开始打代码，很快模板就被我打完了，特意简称了一下所有的文件名是否是对的。但是我仍然没有想到 ios:: 后面是什么，反复打了很多次，突然一个神秘的四字母出现在了屏幕之上：sync，虽然不知道这是什么，但是我总觉得这似乎就是我要追寻的那段神秘指令的一小部分。

我还在疑惑为什么没有自动补全，我突然想到都已经是 \cfrac{n}{2} 了，那很明显不会出现第二个超过的部门。那不就是水题吗！我在心底疑惑了片刻，很快就想到这里是 CSP 考场，第一题就应该这么水。然后就随便写个贪心就好了。再回头去看 ios::sync，接下来应该是下划线了，嗯……打出了 stdio()，但是并不能编译成功。

总之先别管这个了，注释掉了这一行，把样例测试了。测试了三个都没有问题，我本想直接换下一题，但是转念一想还是好好打这场比赛，就都测试了，没有问题。

接着是第二题，是最小生成树，一看到稍微推了一下，完全没注意到城镇是新的节点，总之没进度不了了之了。

于是就来看第三题，本以为是困难的字符串问题，吓哭了。但是看着第二个样例怎么四个 0，很快就发现其实只能替换一次，我才知道这是一个水题，完全没有在意样例里 |t_1|\not=|t_2| 的情况。

突破口是很显然的，首先要关注两个字符串不同的部分，这部分完全可以用哈希进行判断，不过想到前年我就因为调试的时候 base=100 而挂分就莫名的不安。思绪很快回到题目上，只需要判断前缀和后缀都包含就行了。开两个字典树分别记录一下，只需要记录两个字典树上同时出现的编号个数就好了。只需要开个桶记录就好了。

思路有了，代码就很随意了。不过我缺失了 sync 那段代码，输入的效率可没法保证，那就使用快速读入吧，考虑到两个字符串长度是一样的，于是就没写 s_2 后半段判断长度的代码，并且把读入 s1,s2 和 t1,t2 的函数写成了一个。同时，再次凭借肌肉记忆也发现了 ios::sync_stdio()要传入参数 false。很快就到了 debug 环节，毕竟半年没写代码了，有 bug 也很正常。随着几个弱智的问题解决之后，代码正常运行了。我于是测试起样例。

然后我并不会文件对比，所以只能打开 3.out 一个一个看，但是这真没法看出有没有问题。我索性翻到最后，恰好出现了问题。然而我并不解我重新审视代码：字典树上相同的字符串重叠在了一起，那怎么办？开个链式前向星就好了，不顾错误的复杂度，我修改了代码。

然而，代码仍然过不去 3.out 的最后几个询问，于是我打开 3.in——好在能打开——于是我注意到只有一个字母的查询都出了问题。紧接着我发现原来是哈希的时候只判断了 s_1 和 t_1，这能对就怪了，紧接我就写下了：

  for(int i=0;i<tot;i++){
    hsh=(hsh*base%Mod+t1[i])%Mod;
    hsh=(hsh*base%Mod+t2[i])%Mod;
  }

显然正常人都不怎么写，但是我仔细思考了一下，毕竟长度都一样，就这样吧。就这样样例就全过了，包括样例二。

翻到第四题，看上去是诡异的计数题，完全没思路，就放弃了。

回到第二题，才发现原来城镇是新的节点，并且只有 10 个，那暴力岂不是随便打的。

首先 k=0 是糖的，比我还糖。然后注意到 n=10^4，这个和 m 完全不是一个量级，显然有问题。最小生成树显然只需要保留最优的 n-1 个边。那 k 较小的时候暴力判断每个城镇要不要就行了，不过因为刚看完第四题，我以为这个判断是需要 k! 次的，然后就只在 k\le5 的情况。然后就拼了一堆有的没的暴力。总之 75pts 也算多了，没啥必要冲刺正解。

剩的时间还很多，但是我的分数已经很高了，第四题也没有思考的动力，随便写了个 44pts 的暴力。

离比赛结束还有一个小时，但是我依然不想再继续思考了。随便打开了个新的 cpp 文件开始输入，总感觉心底萦绕着 with 这个词，鬼迷心窍就写进了 ios::sync_stdio(false); 中间，没想到编译成功了，于是愉快的放进了四个代码里。

之后就是百无聊赖的等待。

最终就得到了 100+75+100+44=316

——吗

出了考场，就发现几个比我小的人在讨论第一题，还完全不会，何意味。

然后在讨论中我发现，原来 |t_1|\not=|t_2|，那岂不是炸了。随着讨论的继续，我发现原来线段树+桶复杂度是不对的。再后来，我发现我第二题明明能得 100pts，彻底绷不住了。

但是我没有破防，我只是若无其事的继续活着罢了，这只是 CSP 而已，又不是 NOIP。到时候一定不会再这样吧。或许是吧，也可能不是，但那都是以后的事了，现在我只能随波逐流，只能选择安逸，选择逃避。

CSP已然结束了，反正我肯定能过，得多少分吗，那好像也不是很重要，重要的去看看眼下的事情。

眼下的事情吗……

总之，11 月 21 日有解谜活动 ZJUPH，我肯定参加，也希望大家也参加。