CSP-J/S 2025 游记

OrientDragon · 2025-11-06 21:25:23 · 生活·游记

在大连大学内租了酒店，并且在 Day -1 和 grz 激情♂交流。

给他看了一道我出的状压 DAG 可达性问题。（伏笔）

上午打 J，30 min AK 离场。（大雾）

注意到四道题非常水，出场之后问了同学，他居然没有 AK。由于当天是万圣节，所以一律按叛国罪处理。

下午打 S，啊呀骇死我力。

开场 1\text{h} 切前两道（并非），然后就没管了（\bangbangt）。

特别地，注意到 T2 非常类似我出的那道题目，所以自然想到了用 f[S] <- f[S-lowbit(S)] 压掉一个 k。然而忘了写路径压缩。不过时间复杂度是对的，但是并没有 AC，原因等会再细说。

然后死磕 T3。注意到 s_1 和 s_2 的 \text{lcp} 和 \text{lcs} 只需要分别为 t_1 和 t_2 的 \text{lcp} 的后缀、\text{lcs} 的前缀即可。想发明一下二维 trie，但是被大码力创飞了。并没有注意到二位数点神秘离线做法。

想到如何转化到多模匹配，然而我认为 S 组不会考 ACAM，并且我不会写 ACAM，并且我认为 ACAM 时间复杂度不对，遂不写。

期间想出了 T4 的 24\text{pts} 暴力，并且写了一个暴力 hash set 的 T3，但是注意到能够卡到 \mathcal O(nq)。

没有注意到操你妈的世界。

最后看到 CCF 测的 T2 80\text{pts}，此时还在心存侥幸，想着如果 TLE 可以申诉一发。结果发现 T2 并查集数组开小了：

const int N=10005;
int fa[N];
...
for(int i=1;i<=n+k;i++)fa[i]=i;

所以还是操你妈的世界。

居然是省前十，LN 还是太菜了，望加强。

注意到这个分数平移到 NOIp 省队就倒闭了，所以需要加训！加训串串！