题目链接

bzoj1559: [JSOI2009]密码

题解

构造长度为n包含所有模式串的的串，求方案数
构造AC自动机的trie图
对于模式串可以装压dp
设dp[i][j][s]表示位于字符串第i位,位于trie图上的第j个节点，状态为s方案数
转移边为trie图
考虑ans<=42的情况，若字符串的某一个位不属于n个字符串中的任何一个
则至少存在52（2 * 26）种方案。那么答案就是可行
卡内存能信？

代码

/*构造长度为n包含所有模式串的的串，求方案数 构造AC自动机的trie图 对于模式串可以装压dp 设dp[i][j][s]表示位于字符串第i位,位于trie图上的第j个节点，状态为s方案数 转移边为trie图 ?考虑ans<=42的情况，若字符串的某一个位不属于n个字符串中的任何一个则至少存在52（2 * 26）种方案。那么答案就是可行 ?*/#include<queue> #include<cstdio> #include<cstring> #include<algorithm> #define LL long longinline int read() { ????int x = 0,f = 1;char c = getchar(); ????while(c < '0'||c > '9')c = getchar(); ????while(c <= '9' &&c >= '0')x = x * 10 + c - '0',c = getchar(); ????return x * f; } #define LL long long const int maxn = 57; const int maxNode = 137; char a[maxn][maxn],A[maxn][maxn]; int len[maxn]; ?int l,m,n;LL dp[maxn][maxNode][1100 + 7];int sz,bor[maxn][maxn]; int ch[maxNode][31],Snum[maxNode],fail[maxNode]; int border(int x,int y) { //维护一串前与一串后的相同部分，方便搜索 ????for(int i = std::min(len[x],len[y]);i >= 0;-- i) { ????????bool flag = false; ????????for(int j = 1;j <= i;++ j) ????????????if(a[x][len[x] - i + j] != a[y][j]) { ????????????????flag = true;break; ?????????????} ?????????if(!flag) return i; ?????} } ?void insert(int x) { ????int now = 0; ????for(int i = 1;i <= len[x]; ++ i) { ????????int s = a[x][i] - 'a'; ????????if(!ch[now][s]) ch[now][s] = ++ sz; ????????now = ch[now][s]; ????} ????Snum[now] = (1 << (x - 1)); } std::queue<int>que; void getfail() { ????for(int i = 0;i <= 25;++ i) if(ch[0][i])que.push(ch[0][i]); ????while(!que.empty()) { ???????int now = que.front();que.pop(); ?????????for(int i = 0;i <= 25;++ i) { ????????????if(ch[now][i]) fail[ch[now][i]] = ch[fail[now]][i],que.push(ch[now][i]); ???????????else ch[now][i] = ch[fail[now]][i]; // ????????} ????}} int del[maxn]; bool check(int x,int y) { ????for(int i = 0;i < len[y] - len[x] + 1;++ i) { ????????int j = 1; ????????for(;j <= len[x];j ++ )if(a[x][j] != a[y][i + j]) break; ????????if(j == len[x] + 1) return true; ????} ????return false; } void unique() { ????for(int i = 1;i <= n;++ i) for(int j = 1;j <= n;++ j) ??????????if(len[j] > len[i] && !del[j] && !del[i] &&check(i,j)) del[i] = 1,m --; ???for(int i = 1;i <= n;++ i) ????????for(int j = 1;j <= n;++ j) ????????????bor[i][j] = border(i,j); } int Atot = 0,Gtot = 0,g[maxn]; bool vis[maxn]; void dfs(int x) { ????if(x > m) { ????????Atot ++; int t = 0; ????????for(int i = 1;i <= Gtot;++ i) ????????????for(int j = bor[g[i - 1]][g[i]] + 1;j <= len[g[i]];++ j) ????????????????A[Atot][++ t] = a[g[i]][j]; ????????if(t != l) Atot --; ???????return; ????} ????for(int i = 1;i <= n;i ++) { ?????????if(!del[i] && !vis[i]) { ????????????vis[i] = 1; g[++ Gtot] = i; ?????????????dfs(x + 1); ?????????????vis[i] = 0;Gtot --; ????????} ???} } bool cmp(int x,int y) { ????for(int i = 1;i <= l;++ i) if(A[x][i] != A[y][i]) return A[x][i] < A[y][i]; return false;} int rk[maxn]; void solve() { ????dp[0][0][0] = 1; ????for(int i = 1;i <= l;++ i) { ????????for(int j = 0;j <= sz;++ j) ?????????????for(int s = 0;s <= (1 << n) - 1;++ s) ????????????????if(dp[i - 1][j][s]) ?????????????????????for(int x,ss,l = 0;l <= 25;++ l) { ????????????????????????x = ch[j][l]; ss = s; ???????????????????????if(Snum[x])ss |= Snum[x]; ?????????????????????????dp[i][x][ss] += dp[i - 1][j][s]; ????????????????????} ????} ????LL ans = 0,s = 0; ????for(int i = 1;i <= n;++ i) if(!del[i])s += 1 << (i - 1); ????for(int i = 0;i <= sz;++ i)ans += dp[l][i][s]; ????printf("%lld\n",ans); ????if(ans <= 42) { ???????dfs(1); for(int i = 1;i <= Atot; ++ i)rk[i] = i; ????????std::sort(rk + 1,rk + Atot + 1,cmp); ????????for(int i = 1;i <= Atot;++ i) { ????????????for(int j = 1;j <= l;++ j)printf("%c",A[rk[i]][j]); ????????????puts(""); ????????} ???} } int main() { ????l = read(),m = read(),n = m; ????for(int i = 1;i <= m;++ i) ????????scanf("%s",a[i] + 1) , len[i] = strlen(a[i] + 1); ??????unique(); ????for(int i = 1;i <= n;++ i) if(!del[i]) insert(i); ????getfail(); ?????solve(); ????return 0;} ?

bzoj1559: [JSOI2009]密码

原文地址：https://www.cnblogs.com/sssy/p/9270208.html