csp-s2025游记

· · 生活·游记

本人不知道为什么在考完10天后，突发奇想开始写游记。

考号GD-S01905

由于当天中午只睡了30min-，在车上补了会觉。

进入考场，就正常地开题，给密码单独开个文件存下来，后面就可以很方便地复制了。

t1，某社团的人数不超过一半，肯定是类似那种只有一个会不合法，然后之后再搞一下的题。奇怪，怎么想不出来？15min了，还没想出来？完了，我脑子里怎么还开始播歌了？我早上也没听歌啊，赶紧强制切歌对冲一下，就《樱花树下的约定》了。虽然歌手塌了，但歌还是好听的。诶，t1先直接分配，多的那个随便扔不就得了？好像很有道理，写了。

31min，开t2。k=10？n=10000？肯定是和 O(2^kn) 有关的玩意，对吧？然而由于脑子里在播歌，我去想了3min这些新城镇能不能建虚点，额。这m这么大，但是能很轻易地发现原图之后那棵原来的最小生成树是有用的，然后枚举一下那些乡村城镇化集合就行了。但是每次对边排一次序，会爆炸， O(2^knklog{nk}) ，归并就是把 log{nk} 换成 k (其实归并可以把log或k都消掉的，只是我没想到)。

诶，我有个猎奇的想法：就是对每一个新城镇内部的边排序，每次就对 O(k) 条数组归并，我们用个 priority_queue 维护每条数组的头，删一个头就加一个进去，复杂度 O(2^knklog{k}) ，还带1/2常数，肯定可以过。然后我就走了，它也并没有过，跟直接硬排序一个分(虽然用基排的人也跟我一样)。

75+min，开t3。终于对冲成功了，一点歌都没了。两个s的长度相等啊，那我直接给你压成一个字符串，虽然字符集大了点(。两个t也压成一个。然后，题目就转化为t有一些关键点，要求有多少个s是包含这些关键点的、t的子串，位置不同的算不同的。那直接AC自动机啊，开个vector存儿子节点。分析一下求fail指针的复杂度，发现均摊貌似是对的，不对的话也很难卡。至于关键点的要求，就相当于走到AC自动机的一个位置，然后得是该节点在fail树到根的路径上的s，且s的长度要大于某个值。直接倍增。2e6的数据0.28s，不理它了，走了。

还好我考前一天写了AC自动机的板子，不然我就有1年没写这玩意了。

2.5h，开t4。诶，貌似有点套路，状态好像很快就出来了。然后我推了40min转移，反复觉得之前的状态搞错了，修改多次，最后发现最开始的就对的(。于是终于开始对着正确的状态转移。由于我没用容斥，所以做法就是题解区里面最屎的那个。四条转移，15min写第一条，7min写第二条，3min写最后两条。。。抄上去代码，发现第一个样例直接过了，开心至极。第二个过不了，于是写暴力找hack，发现把第一个样例的m改成1就能hack我(。总比没有好。盯自己的dp值，发现少乘了个组合数，乘上去，全部大样例都过了，此时比赛还剩20min。

还有一个搞笑的事情。我以为是最后1h不给上厕所，于是在还剩40min时一直憋着。写完t4后，我想试试能不能上，结果那个老师还真就让我起来了。起来后，另一个老师叫住了我，说最后30min不能上厕所，让我起来的那个老师搞错了。早知道就先去上了。

到这里，这还是个很好的故事，t2卡成80也无伤大雅。出来，发现同学里面只有我全做出来了，挺开心的。

然后，能通过bug查分了，100+80+100+0 。0 ？？！，0 ！！！啊！！！我那天真的崩溃了。

后面发现，我开了 505 505 505 的 long long 的dp数组，然后空间1G，开了滚动就过了。**的，更崩溃了。那我做出来t4算什么？状压就有20，写状压有300。

当然，明年肯定还是希望自己做出t4的。

嗯，明年肯定还是要做出来t4 。

啊啊啊