bzoj 3238 差异

题目传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=3238 后缀数组+单调队列 这是一道后缀数组的模板题。 简单来说,就是先用后缀数组求出h数组。 然后利用单调队列在o(n)的时间复杂度下求出任意两个后缀的最大公共前缀长度的和。 大家看代码 …

我能表示自己不会做吗。 好吧。 其实这道题就是个裸的KMP 但我一开始竟然没有看出来 显而易见的是,如果要添加几个字符的话,肯定是字符串的循环节缺了一部分 所以答案是 (n-fail[n])-n%(n-fail[n]) Code: #include<cstdio> #include …

这道就是纯KMP,QAQ。 你只要把这两个字符串合在一起求一遍KMP就可以了 注意最后输出的总长度必须小于等于min(len1,len2). Code: #include<cstdio> #include<cstring> #include<algorithm> …

继续切水题的我。 这道题算法KMP 然后你只需要在做KMP的时候看一下i%(i-next[i])是否等于0且next[i]不为0 如果是0说明这里有循环节(不信你可以自己模拟一下QAQ) Code: #include<cstdio> #include<algorithm> u …

感觉最近只有我在写博客啊。 这道题的方法是AC自动机+dfs序+树状数组。 你扫描字符串,遇到‘P’就把当前节点设为危险节点,遇到‘B’就返回它的父亲,否则正常转移 于是一个AC自动机就建出来了。 然后你就是跑出以fail数组为连边的树的DFS 离线操作,将询问按y排序, 再次扫描字符串 如果为P, …

这是一道AC自动机QAQ. 题意是求任意两个字符串前缀的最大公共后缀,并且这个后缀要在一个字符串里出现过,输出这个后缀转化成十进制后的答案。 显而易见的是,先建个AC自动机,然后求出fail数组。 你的问题其实就是求两个字符串前缀所在的节点的LCA,然后输出根到它路径上所形成的字符串即可(这个可以预 …

这道可以用KMP 很显然又是一个模板题 只不过因为n太大了,于是用了矩阵乘法 你只要先预处理出fail数组, 然后转移矩阵也就可以求出来了, 你只需要枚举每个前缀的转移,假设枚举前缀i,有一个转移是j,你就在g[i][j]上+1 不过注意如果转移为m的话就continue 代码还是很短。 Code: …

啦啦啦,我这种蒟蒻也只能写这些水题了。 话说czy的模板并不是特别好懂诶@RetardedZY。 这道题其实就是你先把这些合法字符串放进AC自动机。 由于要求的是长度为m的包涵其中一个合法字符串的方案数, 则你可以用AC自动机求出不合法的方案数, 然后用总方案数减去它就可以了。 代码也很短。 Cod …
HDU—5017 Ellipsoid

初来乍到,这是我第一次写博客啦。。。 Solution:玄学的模拟退火一般只能拿部分分,但是如果有spj的题就比较有可能满分了。 话说这道题真是不靠谱,本来说是用模拟退火做的,结果只求局部最优解反而过了,跳出局部最优求全局最优反而超时。 因此模拟退火果然不是什么靠谱的算法。。。 这是我求局部最优解的 …