有26张牌（A~Z），其中三张被拿走了。其余23张被分发给了两个人。给你m次调查结果，一次调查结果是对其中一个人询问一对牌，他会告诉你他有这对牌的几张（0~2）。问你有多少种被拿走的牌的组合。
三重循环枚举被拿走的牌。
然后对于一次调查，我们发现可能的十二种情况中（{这两张牌都被拿走，都不被，其中一张被拿走，其中另一张被拿走} × {回答：0，1,2}），只有一种情况我们不能确定它们的归属，或者无解。即两张牌都不被拿走，并且回答是1。那么必然其中一张牌在一个人手上，另一张牌在另一人手上，但我们不能确定是那张。
其实这是个2-sat的XOR。
因为是双向边，我们可以直接用并查集。
然后有些牌的归属在一开始就已经被制定了。
如果A和!A在同一个并查集里边或者其并查集的取值都一开始确定，并且两者相同，那么无解。其他都有解。
#include#include using namespace std;int n,whi[55],xs[55],ans;char op[55][4];bool cho[105];int beg[105];int fa[105],val[105];int find(int x){ return x==fa[x] ? x : fa[x]=find(fa[x]);}int main(){// freopen("b.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%s%d%d",op[i],&whi[i],&xs[i]); --whi[i]; } for(int i='A';i<='Z';++i){ for(int j=i+1;j<='Z';++j){ for(int k=j+1;k<='Z';++k){ memset(beg,-1,sizeof(beg)); memset(val,-1,sizeof(val)); for(int p=1;p<=52;++p){ fa[p]=p; } cho[i]=cho[j]=cho[k]=1; bool flag=1; for(int p=1;p<=n;++p){ if(cho[op[p][0]] && cho[op[p][1]]){ if(xs[p]>=1){ flag=0; break; } } else if(cho[op[p][0]]){ if(xs[p]==0){ if(beg[op[p][1]]==whi[p]){ flag=0; break; } beg[op[p][1]]=(whi[p]^1); } else if(xs[p]==1){ if(beg[op[p][1]]==(whi[p]^1)){ flag=0; break; } beg[op[p][1]]=whi[p]; } else{ flag=0; break; } } else if(cho[op[p][1]]){ if(xs[p]==0){ if(beg[op[p][0]]==whi[p]){ flag=0; break; } beg[op[p][0]]=(whi[p]^1); } else if(xs[p]==1){ if(beg[op[p][0]]==(whi[p]^1)){ flag=0; break; } beg[op[p][0]]=whi[p]; } else{ flag=0; break; } } else{ if(xs[p]==0){ if(beg[op[p][0]]==whi[p] || beg[op[p][1]]==whi[p]){ flag=0; break; } beg[op[p][0]]=beg[op[p][1]]=(whi[p]^1); } else if(xs[p]==2){ if(beg[op[p][0]]==(whi[p]^1) || beg[op[p][1]]==(whi[p]^1)){ flag=0; break; } beg[op[p][0]]=beg[op[p][1]]=whi[p]; } else{ int f1=find(op[p][0]-'A'+1),f2=find(op[p][1]-'A'+1+26); fa[f1]=f2; f1=find(op[p][0]-'A'+1+26),f2=find(op[p][1]-'A'+1); fa[f2]=f1; } } } if(flag){// if(i=='X' && j=='Y' && k=='Z'){// i='X';// } for(int p='A';p<='Z';++p){ if(beg[p]!=-1){ int f=find(p-'A'+1); if(val[f]==(beg[p]^1)){ flag=0; break; } else{ val[f]=beg[p]; } f=find(p-'A'+1+26); if(val[f]==beg[p]){ flag=0; break; } else{ val[f]=(beg[p]^1); } } } if(flag){ for(int p='A';p<='Z';++p){ int f1=find(p-'A'+1),f2=find(p-'A'+1+26); if(f1==f2 || (val[f1]==val[f2] && val[f1]!=-1)){ flag=0; break; } } if(flag){ ++ans; } } } cho[i]=cho[j]=cho[k]=0; } } } printf("%d\n",ans); return 0;}