题意:有N种01字符串,每种有无限个..问你这些字符串是否有多种组成方案组成相同的串!
分析:求字符串的组成问题,并且求是否能组成相同的字符串.我们可以把所有字符串的状态表示出来.
vis[i][j][k],(0<=i<=1<<22,0<=j<=22,0<=k<2)
i表示这个字符串的十进制的数,j表示这个字符串二进制的位数(这样就可以知道有多少前导0了),k表示是否是题目给的原字符串
这样当有i==0,j==0这个状态时表示符合题目要求,能找到,..故输出"Ambiguous",否则输出"Not ambiguous";
注意:因为状态很大,故每次都初始化的话就会超时!,所以不能初始化,因此我们对状态vis[i][j][k]=cas;表明这是第cas组的状态...只要判断是否等于cas即可判断这个状态是否找到!
(这里TLE了很多次!看了大牛的code,看了很久才看出来!囧啊)
// File Name: 11604.cpp // Author: Zlbing // Created Time: 2013/5/8 9:06:56 #include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<cmath> #include<queue> using namespace std; #define CL(x,v); memset(x,v,sizeof(x)); #define INF 0x3f3f3f3f #define LL long long #define REP(i,r,n) for(int i=r;i<=n;i++) #define RREP(i,n,r) for(int i=n;i>=r;i--) const int MAXN=105; int n; int num[MAXN][26]; int array_len[MAXN]; int inum[MAXN]; struct node { int p,le; int idx; }; int vis[(1<<22)][22][2]; int True=0; int main() { int cas=0; char ch1[100],ch2[100]; while(~scanf("%d",&n)) { if(!n)break; True++; REP(i,0,n-1) { scanf("%s %s",ch1,ch2); int len=strlen(ch2); array_len[i]=len; inum[i]=0; REP(j,0,len-1) { num[i][j]=ch2[j]-'0'; inum[i]=(inum[i]<<1)+num[i][j]; } } bool flag=false; queue<node>Q; node tt; int i; for(i=0;i<n;i++) { tt.p=inum[i]; tt.le=array_len[i]; tt.idx=0; Q.push(tt); if(vis[tt.p][tt.le][tt.idx]==True)break; vis[tt.p][tt.le][tt.idx]=True; } if(i!=n) { printf("Case #%d: Ambiguous.\n",++cas); continue; } node t; int C[26]; while(!Q.empty()) { t=Q.front(); if(t.p==0&&t.le==0) { flag=true; break; } Q.pop(); CL(C,0); int tmp_num=t.p; for(i=t.le-1; i>=0; i--) { C[i]=tmp_num%2; tmp_num/=2; } for(i=0; i<n; i++) { if(t.p==inum[i]&&t.le==array_len[i]) { if(t.idx!=0) { tt.p=0; tt.le=0; tt.idx=1; if(vis[tt.p][tt.le][tt.idx]=True)continue; vis[tt.p][tt.le][tt.idx]=True; Q.push(tt); } continue; } int np,nl; if(t.le>array_len[i]) { nl=t.le-array_len[i]; int j; for(j=0; j<array_len[i]; j++) { if(C[j]!=num[i][j]) { break; } } if(j!=array_len[i])continue; np=0; for(int k=j; k<t.le; k++) { np=(np<<1)+C[k]; } } else { nl=array_len[i]-t.le; int j; for(j=0; j<t.le; j++) { if(C[j]!=num[i][j]) { break; } } if(j!=t.le)continue; np=0; for(int k=j; k<array_len[i]; k++) { np=(np<<1)+num[i][k]; } } tt.p=np; tt.le=nl; tt.idx=1; if(vis[tt.p][tt.le][tt.idx]==True)continue; vis[tt.p][tt.le][tt.idx]=True; Q.push(tt); } } if(flag) printf("Case #%d: Ambiguous.\n",++cas); else printf("Case #%d: Not ambiguous.\n",++cas); } return 0; }