[CF1252D]Find String in a Grid

这个题令我有点自闭,比赛的时候干了两个多小时,虽然干出来了,但是后面三道傻逼题来不及写了,导致排名一落千丈。
这个题思维比较顺畅,应该并不难。但是我为什么会做这么长时间呢?因为我菜。
首先可以发现,能在表中被查出来了字符串一定是最多7000万种字符串的后缀,用这7000万个串去建广义SAM显然直接炸空间了。那么只能对询问的串建广义SAM。
建完广义SAM,我们遍历一下网格,把这些字符串一个一个放进去更新代价,由于这些字符串有一定规律,所以我们每次在广义SAM上只需要移动很少的步数,也就是我们最多移动大约7000万次,复杂度不能带log。
每次移动完之后会产生贡献的一定是其fail树上的祖先,但是直接做有些询问会被重复统计,如果加个条件那就要在fail树上二分,也就是要带log了,不行。但是我们发现可以先做一遍,然后把多统计的次数减掉。这样就不会有问题了。
所以这道题就做完了。

Tagged with:

发表评论