Posts

初级字符串算法合集，预计内容包括：哈希、trie、kmp、manacher、z函数。 缓慢填坑。 ...

希望比去年强。 ...

一个很简单的“禁术”。 ...

D类选手，因为一些原因打铁了。 只写一些和比赛关系比较大的事情，乱七八糟的就不写了。 ...

填完了。 ...

LNOI2022 单看省选成绩是第七名，算上 NOIP 就是第十名左右，翻盘失败。 ...

Description 有一个字符串 $S$，有 $n_a$ 个 A 类串是其子串，有 $n_b$ 个 B 类串是其子串，另外有 $m$ 个支配关系，表示第 $x$ 个 A 类串支配第 $y$ 个 B 类串。 求一个长度最大的字符串 $T$，需要满足两个条件： 其可以分割为若干个 A 类串； 不妨设 $T=t_1+t_2+t_3+…+t_k$，$t_i=A_{id_i}$，那么对于所有的 $t_i,t_{i+1}$，都存在一个 $A_{id_i}$ 支配的 B 类串，使得这个 B 类串是 $t_{i+1}$ 的前缀。 只需要输出长度的最大值即可，若可以无限长，输出 $-1$。 $|S|,n_a,n_b,m\leq2\times10^5$，多组数据，每个数据点中 $|S|,n_a,n_b,m$ 的总和不会超过单组数据限制的 $10$ 倍。 ...

参考：出题人 Itst 的题解。 确实是神仙，不好想。 ...

这个提答还算小清新，不用跑很久，主要是观察数据性质。 ...

很多分类讨论的题，不对拍很容易被卡正确性。 ...