bzoj 1559 [JSOI2009]密码
Description
Input
Output
Sample Input
10 2
hello
world
Sample Output
2
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就好了。。这题我常数写崩了,被卡常,但是对拍没问题,就不往上放了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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; 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]]); } } |