标签： 坑

发布于

[AC自动机][字符串][模板][优化] HDU3695 Computer Virus on Planet Pandora

https://cn.vjudge.net/problem/HDU-3695

跟2222几乎一样，求文本中出现了多少个模式串，但是数据量变大了，5e6的长度。这时候用原来的写法已经会tle了，看到别人说用打标记的方式记录trie上一个节点有没有走过，一开始是不理解的，为什么这么做是正确的？后来想了想，AC自动机的算法确定了一个起点之后，沿着fail回溯的路径便已经确定（神奇），所以这条路上被走过的单词尾，再走的时候就会重复，而我们可以简单的把走过的节点计数标志变为-1，而在之后的过程中再遇到就可以不用管这个节点及其之后所有的节点了。注意这个是在while一开始就得判断。

WA的话，是从带括号的那个原串解压过后忘了在最后加’\0’。。。emmmm以后试验这种一定要从大到小试验数据。还有就是模板一定要用自己熟悉的。。原来以为这题问题在于kuangbin的板子不够快后来发现是没标记。。第二个是一开始没意识到q可以不止1位。。

继续阅读“[AC自动机][字符串][模板][优化] HDU3695 Computer Virus on Planet Pandora”

发布于

[DP][线段树][离散化][细节][坑] XDOJ 1324

离散化写挫了就wa了n发。。

先按照右端点排序，设dp[i]为铺满1到i的最小价值，注意是铺满，那么就可以在这里更新dp[r[i]]=min(dp[j])+v[i]  l[i]<=j<=r[i]，注意这里有一个-1，对于左端点来说，因为如果两个线段相邻二不相交，比如(1,2)(3,4)，这样其实也是可以的。这里的话，如果直接把端点离散化，就会导致后面的操作很复杂，因为要考虑相邻中间有没有空（我也是这么错的），所以不如直接在一开始读入左端点的时候就给他-1，这样之后就不用什么多余的操作了，直接每次线段树查询最小值即可。 继续阅读“[DP][线段树][离散化][细节][坑] XDOJ 1324”