bzoj 1559 [JSOI2009]密码

内容

Description

Input

Output

Sample Input

10 2

hello

world

Sample Output

helloworld

worldhello

HINT

题解

输出方案太恶心了。

发现n很小，考虑状压。

首先对于所有串建个ac自动机。f[i][j][k]表示长度为i，ac自动机的j节点，当前串的状态为k（二进制），按照往儿子走的顺序转移下、

最后结果是f[len][1..sz][(1<< n)-1]求和

发现空间不够，第一维滚动一下。。

发现输出方案的答案是42。可以观察一下，对于所有s1+a..z+s2的这种组合，方案数肯定是大于42的（a..z可以换位置，还是合法的）

那么一开始就去掉所有串包含串的情况（子串），那么最后就是这些串的紧密全排列。（还要考虑一个串的后缀是另一个串的前缀的情况。。）

反正这个暴力非常难写。。hdu有个不输出方案的，实在懒得写就去搞那个吧。

（hdu2825，要求有至少k个串是子串，就是最后统计答案的时候判下二进制位数是不是多于k就好了。。这题我常数写崩了，被卡常，但是对拍没问题，就不往上放了。

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 110
using namespace std;
long long n,m,sz,tot,root,ans,ch[N][26],is_end[N],fail[N],f[2][N][1<<12],len[N];
char s[25][N],a[45][27],c[27];
void insert(char s[],int t)
{
int len=strlen(s),now=root;
for (int i=0;i<len;now=ch[now][s[i]-'a'],i++)
if (!ch[now][s[i]-'a']) ch[now][s[i]-'a']=++sz;
is_end[now]=1<<t-1;
}
void make_fail()
{
queue<int>que;
for (int i=0;i<26;i++)
if (ch[root][i]) que.push(ch[root][i]);
while(!que.empty())
{
int now=que.front();que.pop();
for (int i=0;i<26;i++)
if (ch[now][i])
is_end[ch[now][i]]|=is_end[ch[fail[now]][i]],
fail[ch[now][i]]=ch[fail[now]][i],que.push(ch[now][i]);
else
ch[now][i]=ch[fail[now]][i];
}
}
int rk[47],l,o; bool vis[11],del[11];
void dfs(int x,int u)
{
if(x>o)
{
if(u!=l)
return;
++tot; 
memcpy(a[tot],c,sizeof a[tot]);
return;
}
for(int i=1;i<=n;++i)
if(!vis[i] && !del[i])
{
vis[i]=1; 
int L=len[i],k;
for(int j=max(u-L,0);j<u;++j)
{
for(k=0;k<L && k+j<u;++k) 
if(s[i][k]!=c[j+k])
break;
int temp=u;
if(k==L || k+j==u)
{
for(;k<L && temp<l;++k)
c[temp++]=s[i][k];
if(k==L)
dfs(x+1,temp);
}
}
if(u+L<=l)
{
for(k=0;k<L;++k)
c[u+k]=s[i][k];
dfs(x+1,u+L);
}
vis[i]=0;
}
}
int comp(int x,int y)
{
for(int i=0;i<l;++i)
if(a[x][i]<a[y][i])
return 1;
else if(a[x][i]>a[y][i])
return 0;
return 0;
}
int find(int x,int y)
{
for(int i=min(len[x],len[y]);~i;i--)
{
bool flag=0;
for(int j=0;j<i;j++)
if(s[x][len[x]-i+j]!=s[y][j])
{
flag=1;
break;
}
if(!flag) return i;
}
}
main()
{
scanf("%d%d",&l,&n);
for (int i=1;i<=n;i++)
scanf("%s",s[i]),len[i]=strlen(s[i]);
for (int i=1;i<=n;i++)
if (!del[i])
for (int j=1;j<=n;j++)
if (i!=j)
if (find(i,j)==len[j])
del[j]=1;
for (int i=1;i<=n;i++)
if (!del[i])
insert(s[i],i);
make_fail();
f[0][root][0]=1;
int all=1<<n;
for (int i=0;i<l;memset(f[i&1],0,sizeof f[i&1]),i++)
for (int j=0;j<=sz;j++)
for (int k=0;k<all;k++)
if (f[i&1][j][k])
for (int l=0;l<26;l++)
f[i+1&1][ch[j][l]][k|is_end[ch[j][l]]]+=f[i&1][j][k];
int te=0;
for (int i=1;i<=n;i++)
if (!del[i])
te+=(1<<i-1),o++;
for (int i=0;i<=sz;i++)
ans+=f[l&1][i][te];
printf("%lld\n",ans);
if (ans<=42)
{
dfs(1,0);
for (int i=1;i<=tot;i++)
rk[i]=i;
sort(rk+1,rk+1+tot,comp);
for(int i=1;i<=tot;++i)
printf("%s\n",a[rk[i]]);
}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

#define N 110

using namespace std;

long long n,m,sz,tot,root,ans,ch[N][26],is_end[N],fail[N],f[2][N][1<<12],len[N];

char s[25][N],a[45][27],c[27];

void insert(char s[],int t)

{

int len=strlen(s),now=root;

for (int i=0;i<len;now=ch[now][s[i]-'a'],i++)

if (!ch[now][s[i]-'a']) ch[now][s[i]-'a']=++sz;

is_end[now]=1<<t-1;

}

void make_fail()

{

queue<int>que;

for (int i=0;i<26;i++)

if (ch[root][i]) que.push(ch[root][i]);

while(!que.empty())

{

int now=que.front();que.pop();

for (int i=0;i<26;i++)

if (ch[now][i])

is_end[ch[now][i]]|=is_end[ch[fail[now]][i]],

fail[ch[now][i]]=ch[fail[now]][i],que.push(ch[now][i]);

else

ch[now][i]=ch[fail[now]][i];

}

int rk[47],l,o; bool vis[11],del[11];

void dfs(int x,int u)

{

if(x>o)

{

if(u!=l)

return;

++tot;

memcpy(a[tot],c,sizeof a[tot]);

return;

}

for(int i=1;i<=n;++i)

if(!vis[i] && !del[i])

{

vis[i]=1;

int L=len[i],k;

for(int j=max(u-L,0);j<u;++j)

{

for(k=0;k<L && k+j<u;++k)

if(s[i][k]!=c[j+k])

break;

int temp=u;

if(k==L || k+j==u)

{

for(;k<L && temp<l;++k)

c[temp++]=s[i][k];

if(k==L)

dfs(x+1,temp);

}

if(u+L<=l)

{

for(k=0;k<L;++k)

c[u+k]=s[i][k];

dfs(x+1,u+L);

}

vis[i]=0;

}

int comp(int x,int y)

{

for(int i=0;i<l;++i)

if(a[x][i]<a[y][i])

return 1;

else if(a[x][i]>a[y][i])

return 0;

}

int find(int x,int y)

{

for(int i=min(len[x],len[y]);~i;i--)

{

bool flag=0;

for(int j=0;j<i;j++)

if(s[x][len[x]-i+j]!=s[y][j])

{

flag=1;

break;

}

if(!flag) return i;

}

main()

{

scanf("%d%d",&l,&n);

for (int i=1;i<=n;i++)

scanf("%s",s[i]),len[i]=strlen(s[i]);

for (int i=1;i<=n;i++)

if (!del[i])

for (int j=1;j<=n;j++)

if (i!=j)

if (find(i,j)==len[j])

del[j]=1;

for (int i=1;i<=n;i++)

if (!del[i])

insert(s[i],i);

make_fail();

f[0][root][0]=1;

int all=1<<n;

for (int i=0;i<l;memset(f[i&1],0,sizeof f[i&1]),i++)

for (int j=0;j<=sz;j++)

for (int k=0;k<all;k++)

if (f[i&1][j][k])

for (int l=0;l<26;l++)

f[i+1&1][ch[j][l]][k|is_end[ch[j][l]]]+=f[i&1][j][k];

int te=0;

for (int i=1;i<=n;i++)

if (!del[i])

te+=(1<<i-1),o++;

for (int i=0;i<=sz;i++)

ans+=f[l&1][i][te];

printf("%lld\n",ans);

if (ans<=42)

{

dfs(1,0);

for (int i=1;i<=tot;i++)

rk[i]=i;

sort(rk+1,rk+1+tot,comp);

for(int i=1;i<=tot;++i)

printf("%s\n",a[rk[i]]);

}