BZOJ 1559 JSOI2009 密码状压dp+AC自动机+搜索-白红宇

BZOJ 1559 JSOI2009 密码状压dp+AC自动机+搜索

阅读量：4624 次

发布时间：2019-06-09

本文共 1898 字，大约阅读时间需要 6 分钟。

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1559

分析：

　　这个题意真的是很**啊！！！直接说每一个字符串至少出现一次不就好了吗......一开始理解错了ORZ

　　观察发现这个东西是字符串相关，并且有多个模板串，所有串的长度短并且串的数量不多，最多10个，因此大概可以想到一个AC自动机上面的状压。

　　首先把被包含的单词去掉，它们对决策不影响，这样在写方程的时候就可以不考虑last了。

　　令f(i,l,s)表示当位于AC自动机的状态i时，已经生成了l个字符，所有单词的出现情况为s的方案数。

　　f(i,l,s) = sum{ f(j,l-1,s) | j->i } + sum{ f(j,l-1,s-{i}) | j->i },s包含单词i。刷表实现即可。

　　ans=sum{ f(i,L,all) | 0<=i<=np }

　　当答案小于等于42的时候直接在状态转移图上面倒着搜就可以了，看那些状态对当前状态有贡献，一路搜下去，最后把所有串排个序即可。

　　时间复杂度O(L*N*len*2^N)，最后的方案搜索因为方案很少几乎不要时间。

　　get套路之：字符串算法构造状态辅助字符串有关dp！

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #include
               10 #include
               
                 11 #include
                
                  12 using namespace std; 13 typedef long long LL; 14 15 int L,N,cnt,len; 16 char S[12][12],path[30]; 17 LL f[105][27][1050]; 18 bool vis[12]; 19 struct mstring{ 20 static const int maxn=30; 21 char str[maxn]; 22 mstring(){ memset(str,0,sizeof(str)); } 23 friend bool operator < (mstring a,mstring b){ 24 int n=min(strlen(a.str),strlen(b.str)); 25 for(int i=0;i

q; 50 fail[0]=0; 51 for(int w=0;w<26;w++) 52 if(to[0][w]) fail[to[0][w]]=0,q.push(to[0][w]); 53 while(!q.empty()){ 54 int p=q.front(); q.pop(); 55 for(int w=0;w<26;w++){ 56 int j=to[p][w]; 57 if(!j){ to[p][w]=to[fail[p]][w]; continue; } 58 q.push(j); 59 fail[j]=to[fail[p]][w]; 60 } 61 } 62 } 63 }ac; 64 65 void data_in() 66 { 67 scanf("%d%d",&L,&N); 68 for(int i=0;i

n) continue; 74 bool ok; 75 for(int k=0;k<=n-m;k++){ 76 ok=1; 77 for(int l=0;l

=0;j--) 94 ss[cnt].str[len-1-j]=path[j]; 95 ss[cnt].str[len]='\0'; 96 return; 97 } 98 for(int j=0;j<=ac.np;j++) if(f[j][l-1][s]) 99 for(int w=0;w<26;w++) if(ac.to[j][w]==i){100 path[len++]=w+'a'; run(j,l-1,s);101 len--; break;102 }103 if(ac.val[i]){104 s^=1<

View Code

转载于:https://www.cnblogs.com/KKKorange/p/8746860.html

你可能感兴趣的文章