一个似曾相识的 CSP

· · 生活·游记

\text{before Oct.}

初赛 93.5。感觉有点低。

\text{~October 25th}

应该是这一天市赛来着。

市里组织的科技运动会，听说会选出 10 个人晋级参加省赛，感到很神秘。到考场看到许多小朋友，以为自己稳了，赣州市高手应该没有那么多。

开题！

T1 入门题，直接模拟秒了。考场上看笑了。考场后也看笑了，听说挂了 30。

T2 神秘题，可以选择两个相同的数同时减一并获得该数的值的贡献，求最大价值。赛时不知道为啥以为必须要相邻两个，属于是给原题加强了。最终花了点时间才写完，还过了所有样例？无敌了。

T3 入门题，但是似乎也挂了分。

T4 是打乒乓球题，列个式子应该就做完了，但是给的样例答案都是 01，何意味？这能调？赛后讨论发现我又理解错题意了。

质量很拉，没有起到 CSP 热身的作用。不过毕竟是第一次办，倒也理解。

\text{~October 30th}

最后一天在机房，不知道看些什么，也不知道该准备一些什么。

\text{~October 31th}

坐高铁来到了九江。出车站准备找饭吃，被车站边一个饭店的老板娘拉了过去，点菜的时候交流并不愉快，我们最终还是到酒店自己点外卖吃。

下午晚上就爽玩！不知道复习些什么，也不知道该以什样的心态迎接这最后一年。和大家一起玩和平，玩常轨脱离，玩音游，还是很有意思的。

\text{~November 1th}

上午稍微复习了一下，看了看板子。

还是憋不住了！原神启动！速刷了刚更新的新深渊，竟然满星了？不管了，冲刺！同学帮我抽卡，竟然小保底出了芙宁娜？有点意思。

下午 2:30 开考。

进考场快速写了 gen 和辅助编译程序，并建好了文件夹。

2:28 下发了题目。

开 T1，没啥好说的，13min 通过大样例。

开 T2，一开始以为那些关键点是 n 个节点中的 1~k 号节点，并在观察了一下 O(2^km\log m) 暴力算法后想出了优化，考虑去除 kruskal 算法过程中的无用边，将初始的 m 条边降至 n-1 条。从而复杂度来到了 O(2^kkn\log kn)。大样例跑得挺快就先丢了。写完大概过了 53min。

开 T3，很快想到了将每个二元组变成 A+B+C 和 A+D+C 的形式。一开始忽略了前缀 A 和后缀 C 的影响，写了假做法，但很快发现了问题。自此陷入长考。将这些划分的段都套上哈希后，需要给定二元组的 A 是询问串的 A 的后缀，B 是询问串的 B 的前缀，同时考虑这两个限制似乎相当困难，思考了 40min 无果后前去开 T4。

开 T4，是我不擅长的计数题，对于数排列题，我的脑海里似乎只有按 1~n 顺序插入，但由于 s 数组的限制，使得需要确定每个人的绝对位置，前面那种做法需要答案只和相对顺序有关。感觉很难，遂开始拼暴力，会了 O(n^22^n) 的 20 分暴力，会了 m=1,m=n 的 16 分。开始尝试题目给的 A,B 性质。并尝试对于 B 性质，给所有 s_i=1 的位置进行指数级枚举其是否录用成功，发现这些位置的 c 的限制变成了 \ge 与 \le 两种方向的限制，感觉很困难，便没有再思考下去。此时时间大概只剩下 100min 了，切题的希望已经不大了。只能开始拼 T3,T4 的暴力。

T4 写了 36 分，T3 写了 40 分，然后开始检查，给 T2 造了一个极限数据，发现跑的很慢，给他加了一个剪枝就跑的快了很多。不知道官方数据会给多少。

出了考场，感觉考的不太好，还是 250 左右这样平庸的成绩。

捕捉到一位 csh，询问得知他怒切前三题，拜谢。听他讲完做法后，发现给二元组分完段后，只需要给前后缀中间加个特殊字符拼起来插进 AC 自动机里，便可以完成我那些后续的操作，转化成了普通的多模式串匹配问题。实现也很简单。没啥细节。

和 lrz 交流，他会了 T3,T4 的做法，可惜没有调出来。xzq T3 的 SA 做法也没有调出来。明明大家实力都不弱，为什么会是这样的结果？

晚上和 lrz,xzq 出去散了步，绕着公园、南门湖走了一圈，发现了很多小情侣（？）分别时还合了影。

你问我最终会是什么样的结局？你的努力会以怎样的成绩收场？夜空里，看不到星星，也看不到月亮，钓鱼佬正在放杆，有人在桥上唱歌。这一路上，我比以往更清楚地看到了友情和亲情，以及我的成长，我的收获，这些便足以让我继续闯完剩下的路程。

到了车站，等车的时候又和同学开黑，很快乐。在机房一起摸鱼的日子也是很快乐的。我在 OI 的日子也进入了倒计时。

\text{~November 2th}

中午和龙队,lrz 去万象城，吃了蛋包饭。

晚上订正了 T3,T4，如果 T3 能稍微往 AC 自动机方向想的话，那得分就会高很多吧。可能就可以去 WC 了？目前看来，T2 因为枚举集合的时候多加了一个 -1 ，T4 的暴力有一维数组没有开够，现在大概要挂不少分。这是不是和今年省选 d1t1 的剧本差不多呢？

从机房回来，爸妈和我谈论了去广二的事。之前我一直是很纠结的。就是很纠结，说不出个什么具体的理由。

说到野心，我确实是个保守、求稳的人，这也符合我一直以来的作风，所以每次只能获得中规中矩的得分。现在的投入，相比于未来可能的收获，其实是微不足道的。所以要敢于去搏，去冲，去尝试。缩在方寸间的小黑匣，永远看不到窗外的月明。

因此结束了 CSP2025 的故事，并计划于 4 日前往广二集训。开始 NOIP2025 的冲刺。