CSP-S 一日游

wangyibo201026 · 2025-11-06 21:15:41 · 生活·游记

首先开场 30 min 过 T1, T2。

然后看 T3，发现就是找到第一个不同和最后一个不同位置，判断一下前后缀包含关系即可。

最后分析了近 3h 的 T4，感觉排列计数 + 前缀信息不是很懂怎么 DP，容斥也容不明白，写了个状压也没分析性质就下场了，最后期望 324 pts。

接下来详细揭秘为什么最后出来是 274 pts。

考完试第二天上午，有人说 T3 怎么这么难，我看了一眼，发现是有人没判 t_1 \ne t_2。然后中午我吃饭开始追忆过去，发现 zcx 不是和我一个做法吗？怎么他复杂度是 O(qn) 的？

然后下午去打羽毛球，被打破防了，又开始追忆，突然又想起来我草我复杂度是不是写的 O(qn \log n) 的，他妈场上我认为这个东西是 O(\sum ans \log \sum ans) 的，妈的 \sum ans 不是 O(qn) 级别吗？我在干什么！

然后仔细想了想，是不是求个 trie 树上祖先链交暴力查询就做完了来着，复杂度是不是线性的？我草我是傻逼，我场上没意识到这个东西要用 trie 做，我脑子得唐诗综合征了认为复杂度是 O(q \log n) 的，直到考完后一天上午我都没意识到这一点。

然后 zcx 说它的 O(qn) 在熨斗上能拿 80 pts，说能不能多拿点分，不然上不了 300 就去不了 WC 了。

然后 CCF 不知道啥数据就 50 pts 了（出数据后 30 min 写完了 std）。

幸亏 T2 没卡我懒得实现的 O(2^k kn) 来着（并查集算常数），不然也更爆炸了。

还是太菜了，把 T4 做出来就没这么多事了，警惕一定要赛时分析对复杂度。

省流：我写 std 的过程中复杂度又假了一遍。