首页 > 代码库 > bzoj 2806: [Ctsc2012]Cheat 熟悉的文章
bzoj 2806: [Ctsc2012]Cheat 熟悉的文章
【题意】
【题解】
fhq自己写的题解就很清楚啦 （里面有关于神秘的阿米巴同学的介绍哦！很帅的样子，，，
我再来理一下思路
这道题思路应该是很简单很常规的，，但我做题太少辣!
二分一下肯定是必要的， 下面是判断是否可行的问题。
容易想到 要开一个 f 数组 表示 扫到了 第 i 位时 能匹配上多少个字母， 最后答案就是 f[lenth] * 10 >= lenth * 9 啦
f[i] 显然可以 通过 f[j] 转移 (j <= i - 二分出的下限的长度 + 1 且s[j……i]出现在字典里)
下一步要确定的就是 有哪些 j 是出现在字典里的， 也就是 在 S 中 以 i 为后缀的这个字符串 最长有多少出现在字典里。
后缀自动机模板就出来啦 （此处该有音乐： 当(sou)当(sou)当(sou)当(?mi)……
然后会发现 dp 的时候 j 显然是单调的（如果 i - 1 的转移时的下限 为 j ， i 的显然不会小于 j ， 否则 i - 1 的也可以小于j 了）
所以单调队列优化一下就好了
代码非常非常短
#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>#define MAXN 3000005using namespace std;int n, m, lenth, cnt, last, q[MAXN], len[MAXN], trans[MAXN][3], fat[MAXN], f[MAXN];char s[MAXN];void insert(int x){ int np = ++ cnt, p = last; len[np] = len[last] + 1; last = np; for(; !trans[p][x]; p = fat[p])trans[p][x] = np; if(!p)fat[np] = 1; else{ int q = trans[p][x]; if(len[q] == len[p] + 1)fat[np] = q; else{ int nq = ++ cnt; len[nq] = len[p] + 1; memcpy(trans[nq], trans[q], sizeof(trans[q])); fat[nq] = fat[q]; fat[q] = fat[np] = nq; for(; trans[p][x] == q; p = fat[p])trans[p][x] = nq; } } }bool pd(int limit){ int bot = 1, top = 0, cur = 1, ll = 0; f[0] = 0; for(int i = 1; i <= lenth; i ++){ f[i] = f[i - 1]; int c = s[i] - ‘0‘; for(; !trans[cur][c]; cur = fat[cur]); if(!cur){cur = 1; ll = 0;} ll = min(ll, len[cur]) + 1; cur = trans[cur][c]; int p = i - limit; if(p >= 0){ while(bot <= top && q[top] - f[q[top]] > p - f[p]) top --; q[++ top] = p; } while(bot <= top && q[bot] < i - ll)bot ++; if(bot <= top) f[i] = max(f[i], f[q[bot]] + i - q[bot]); } return f[lenth] * 10 >= lenth * 9;}int main(){ scanf("%d%d", &n, &m); last = ++ cnt; while(m --){ scanf("%s", s + 1); lenth = strlen(s + 1); for(int i = 1; i <= lenth; i ++)insert(s[i] - ‘0‘); insert(2); } while(n --){ scanf("%s", s + 1); lenth = strlen(s + 1); int l = 1, r = lenth, mid; while(l + 1 < r){ mid = l + r >> 1; if(pd(mid))l = mid; else r = mid - 1; }printf("%d\n", pd(r) ? r : l); } return 0;}
bzoj 2806: [Ctsc2012]Cheat 熟悉的文章
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。