CSP-S2025 游记

主播主播，你怎么没参加 csp 也要写游记啊？

ICPC 武汉站有七位群友来面基，人均花费 30 元吃完饭后回到武汉大学经过一个旅游景点后来到一个石桌前坐下开 CSP 题。

经过群友在 LA 的寻找首先拼凑出第三题和第四题题面，怎么第三题还是串串题。

首先我们一眼丁真出相同前缀后缀去掉只有中间是有效修改，也就转化为每个中间修改为一类，每次修改直接求有多少个包含的前缀后缀就行。

那这不是 AC 自动机模板题吗？？？提高组怎么能考 AC 自动机？？？

最后还得看虎爷说，把每一个类建一棵 trie 树，初始的串前后缀分别对应各自 trie 树上的一个子树，直接拍平成 dfn 序然后扔到二维平面上，这就是一个矩形加单点差的扫描线板子。

但是这个东西放 T3 是不是思维含量有点大了？

开了 T4 首先我们对 k舔 在 LA 发的题面是否为中文表示质疑，用了一些时间终于是读懂了。

这个数据范围肯定是个三次方 dp，而且其中两维显然是天数和倒闭了几个人，那有人说如果我枚举第三维状态不就做完了？难道他真的是天才？

具体思考一下，注意到这种直接看上去是选子集信息的是根本不能直接维护的，一定要用什么东西去转化。进一步地，因为每个人都有各自的 $c$，不难想到去维护每一个 $c$。

我想到我学长这个周就给我看到一个情景比较类似的题，虽然我用不是他的做法把他那题给秒了。这我就不得不想道可以不立即选择哪个具体的人。

设前 $i$ 天有 $j$ 个人倒闭，那么所有的 $c\leq j$ 的和以后变化是没有影响的，因为不管后面怎么搞来了就倒闭。所以不妨设有 $k$ 个通过的人中满足 $c>j$ 的，其中剩余已经通过的人即 $c\leq j$ 的方案数。

那问题转化为每次倒闭一个人更新 $j$ 的时候怎么更新 $c>j$ 的人。那只需要把过量的人中选出若干个人进到这里是不是成功了，但是这直接做是四次方，还是倒闭了。

但是再想想可以直接按照完全背包的思路从 $k$ 转移到 $k-1$ 以此类推转移，直接砍掉一维。

我做完这题突然想过我好像真的出过包含这个 trick 的题，欢迎大家做一下：https://uoj.ac/problem/1005

那我怎么把 T4 给口胡出来了？

群里发了 T1，怎么是不存在绝对众数。当时在场的都是有幸做过众数的人，怎么绝对众数还在追我。

解决了一下内急后回来一看，诶怎么第三题不保证前面的串长度相同？出题人怎么这么坏？难道红子相撞就是 OI 的底层逻辑吗。强强？？！！？？！！

问了一下 T2 题面，怎么还有 $k=10$。用一下最小生成树的性质好像很容易就做完了，归并一下甚至能去 $\log$。

然后我们精神阿克了这场的 CSP。

是不是该说明天武汉站加油，我也该睡了。