专栏文章

CSP-S 2025 游记

ddoumingze
生活·游记参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minf8tvj
此快照首次捕获于
2025/12/02 01:27
3 个月前
此快照最后确认于
2025/12/02 01:27
3 个月前
查看原文
省流：并查集写成一只老哥，我赢了。一个字符浪费两小时，我赢了。不会写t4，我赢了。不会写t4状压，我赢了。
相信少爷机。
能打成这样是我应得的，烂成一坨了。
[248,312][248,312]。
不省流：T1 感觉很反悔贪心，但是 20mins 才会感觉很不牛啊。然后光速看 T2/T3 发现都会了，写 T2，发现并非会吧。仔细想了想想到了优化成 2knα(n)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×1065 \times 10^6，又发现自己离线的时候发生了 dfs 深度 5×1065 \times 10^6，效率真是太高了。怎么赢。
相信少爷机。
100+[80,100]+[60,100]+[8,12]=[248,312]100 + [80,100] + [60,100] + [8,12] = [248,312]，技不如人没办法。
等出分吧，在联赛没炸之前我都是能活的。
upd：应该 312312 吧（官方没出）。但是根据神秘手段得知的官方成绩是全部顶到上界的，一分不挂。

能去 WC 吗？能去 WC 吗？能去 WC 吗？能去 WC 吗？能去 WC 吗？能去 WC 吗？

upd2：官方 312312，没问题。但是看到了 101010010^{10^{100}} 个比我高的。应该没有 WC 去了。
其实还看到了 101010010^{10^{100}} 个没判 ∣t1∣≠∣t2∣|t_1| \neq |t_2| 的但是 100100 分的游记，然后就，都比我高了，吧。所以：
是的，不保证字符串长度相等也是信息学竞赛的一部分。这就是两个红子相撞引发的宇宙大爆炸延伸至今的优良传统。我只能说输不起就别打比赛。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...