并查集
本题中不同的变量可以表示不同长度的01串，这给解题带来了麻烦。我们可以把所有长度为p的变量拆成p个长度为1的变量，以简化问题。这样，所有拆分后得到的变量都只能表示一个0或1。假设等号两边的长度都为L，如果把0和1本身也看成特殊的变量的话，等式告诉我们的就是L个相等关系，即某两个变量相等。用并查集维护这些相等关系：初始时每个变量自成一个集合，每遇到一个相等关系，把相等的变量所在集合合并。如果某一时刻0和1所在的集合被合并，则说明出现矛盾，输出0；否则，没有矛盾出现，假设最终除0和1所在集合外共有r个集合，则答案为
。
注意测试数据中存在展开后等式两边长度不等的情况。
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 | #include <iostream> using namespace std; char s1[10011],s2[10011]; int total,len[33],s[10011],f[10011],size[10011],ans[11111111]; int getRoot(int v) { if(f[v]==v) return v; else return f[v]=getRoot(f[v]); } void unite(int a,int b) { int x=getRoot(a),y=getRoot(b); if(x!=y) { if(size[x]<size[y]) { size[x]+=size[y]; f[y]=x; } else { size[y]+=size[x]; f[x]=y; } --total; } } int main() { freopen("row.in","r",stdin); freopen("row.out","w",stdout); int T; for(scanf("%d",&T);T;--T) { int num,l1,l2; scanf("%d",&num); for(int i=0;i<num;++i) scanf("%d",len+i); scanf("%d\n%s\n%d\n%s",&l1,s1,&l2,s2); for(int i=1;i<num;++i) len[i]+=len[i-1]; for(int i=num;i>0;--i) len[i]=len[i-1]+2; len[0]=2; int top=0; for(int i=0;i<l1;++i) if(s1[i]>='a'&&s1[i]<='z') for(int j=len[s1[i]-'a'];j<len[s1[i]-'a'+1];++j) s[top++]=j; else s[top++]=s1[i]-'0'; for(int i=0;i<10005;++i) f[i]=i,size[i]=1; int firstTop=top; top=0; total=len[num]-2; for(int i=0;i<l2;++i) { if(s2[i]>='a'&&s2[i]<='z') for(int j=len[s2[i]-'a'];j<len[s2[i]-'a'+1];++j) unite(s[top++],j); else unite(s[top++],s2[i]-'0'); } if(getRoot(0)==getRoot(1)||top!=firstTop) puts("0"); else { memset(ans,0,sizeof(ans)); int m=1; ans[0]=1; for(;total;--total) { int x=0; for(int i=0;i<m;++i) { ans[i]=(ans[i]<<1)+x; if(ans[i]>9) x=1,ans[i]-=10; else x=0; } if(x) ans[m++]=1; } for(int i=m-1;i>=0;--i) putchar('0'+ans[i]); putchar('\n'); } } return 0; } |