CSP-S 2025 游记
doumingze
·
·
生活·游记
省流：并查集写成一只老哥，我赢了。一个字符浪费两小时，我赢了。不会写t4，我赢了。不会写t4状压，我赢了。
相信少爷机。
能打成这样是我应得的，烂成一坨了。
不省流：T1 感觉很反悔贪心，但是 20mins 才会感觉很不牛啊。然后光速看 T2/T3 发现都会了，写 T2，发现并非会吧。仔细想了想想到了优化成 $2^kn\alpha(n)$ 的方法（然而出考场好久之后才发现写成一只老哥了，怎么回事呢。。）。
这个时候 16:00，T3 差不多会了，有优势好吧。
T3 就一坨吧。
不想写 AC 自动机，实则是不会。然后仔细想了一下想到哈希 + 双 trie 离线做法了。然后就是史中史：
```cpp
void insert(int x) //insert x into a trie
{
int p = 0;
for(int i = 0; s[i]; i ++)
{
int u = s[i] - 'a';
if(!tr[p][u]) tr[p][u] = ++ idx;
u = tr[p][u];
}
}
```
如果你看不出有什么问题：注意到 `p` 始终没有更新。
当然还有一些离谱错误，不过早就发现了，基本 17:10 之前就只剩这一个错了。
然后我 17:55 才调出来这个。浪费我写对拍的时间。
但是跑的怎么这么慢。。
最后几分钟写了 T4 12pts。
毫无卡常。
出考场发现我在看完 T4 题面之后想到的状态是对的，但是被我否决掉了，就是不愿意细想性质和转移说是。
然后又发现状压是简单的，记录用掉的数是什么就行了。我到底在干什么。
然后出考场发现自己 T2 kruskal 写成一只老哥的并查集了。这下这下了。
然后又发现 T3 有 8 个点是 $5 \times 10^6$，又发现自己离线的时候发生了 `dfs` 深度 $5 \times 10^6$，效率真是太高了。怎么赢。
相信少爷机。
$100 + [80,100] + [60,100] + [8,12] = [248,312]$，技不如人没办法。
等出分吧，在联赛没炸之前我都是能活的。
---
**upd：应该 $312$ 吧（官方没出）。但是根据神秘手段得知的官方成绩是全部顶到上界的，一分不挂。**
# 能去 WC 吗？能去 WC 吗？能去 WC 吗？能去 WC 吗？能去 WC 吗？能去 WC 吗？
**upd2：官方 $312$，没问题。但是看到了 $10^{10^{100}}$ 个比我高的。应该没有 WC 去了。**
其实还看到了 $10^{10^{100}}$ 个没判 $|t_1| \neq |t_2|$ 的但是 $100$ 分的游记，然后就，都比我高了，吧。所以：
是的，**~~不保证~~**字符串长度相等也是信息学竞赛的一部分。这就是两个红子相撞引发的宇宙大爆炸延伸至今的优良传统。我只能说输不起就别打比赛。