BZOJ 4460 [Jsoi2013]广告计划 ——Bitset 后缀自动机
标签：match == 表示 end name char s add freopen int
Orz，好久没有自己想出正解来了。
看了看题目并不是很会做，然后看了一下题解，
这都是些什么玩意。
没看懂只能回来自己想。
然后发现n比较小，直接枚举答案，然后发现连续的一段是确定的，然后我们只需要判断每个位置是否有这个连续的一段就好了
发现起点不同，最后的位置可能会有差距，所以DP一下就好了
然后用0表示未折返，1表示从最下面换到最上面，然后就是发现所有位置互不干扰，直接用Bitset压一下就可以做了
复杂度N^3/64
#include
using namespace std;
#define maxn 100005
int fa[maxn],go[maxn][26],last,cnt,l[maxn],v[maxn],q[maxn];
char s[maxn];
bitset bit[maxn],Nothing,dp[2][2];
void init()
{
last=cnt=1;
}
void add(int x,int pos)
{
int p=last,q;
if ((q=go[p][x])){
if (l[q]==l[p]+1) last=q;
else{
int nq=++cnt;
l[nq]=l[p]+1;
memcpy(go[nq],go[q],sizeof go[q]);
fa[nq]=fa[q];
fa[q]=nq;
for (;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq;
last=nq;
}
}
else{
int np=++cnt; l[np]=l[p]+1;
for (;p&&!go[p][x];p=fa[p]) go[p][x]=np;
if (!p) fa[np]=1;
else{
q=go[p][x];
if (l[q]==l[p]+1) fa[np]=q;
else {
int nq=++cnt;
l[nq]=l[p]+1;
memcpy(go[nq],go[q],sizeof go[q]);
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for (;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq;
}
}
last=np;
}
bit[last][pos]=1;
}
void insert()
{
last=1;
scanf("%s",s+1);
int Len=strlen(s+1);
for (int i=1;i=1;--i) q[v[l[i]]--]=i;
for (int i=cnt;i>=1;--i)
bit[fa[q[i]]]|=bit[q[i]];
}
int n,m,Len;
char t[maxn];
bool test(int x)
{
int now=1,pre=0;
dp[now][0].reset();
dp[now][1].reset();
dp[now][0].set();
int all=(Len+x-1)/x;
for (int i=1;i Match=bit[pos];
if (tmp Test;
Radix();
Nothing.reset();
scanf("%s",t+1);
Len=strlen(t+1);
for (int i=1;i
BZOJ 4460 [Jsoi2013]广告计划 ——Bitset 后缀自动机
标签：match == 表示 end name char s add freopen int
原文地址：http://www.cnblogs.com/SfailSth/p/7133840.html
评论