【并查集】Gym - 101128B - Black Vienna

约定不等于承诺〃 2022-01-07 01:19 138阅读 0赞

有26张牌（A~Z），其中三张被拿走了。其余23张被分发给了两个人。给你m次调查结果，一次调查结果是对其中一个人询问一对牌，他会告诉你他有这对牌的几张（0~2）。问你有多少种被拿走的牌的组合。

三重循环枚举被拿走的牌。

然后对于一次调查，我们发现可能的十二种情况中（\{这两张牌都被拿走，都不被，其中一张被拿走，其中另一张被拿走\} × \{回答：0，1,2\}），只有一种情况我们不能确定它们的归属，或者无解。即两张牌都不被拿走，并且回答是1。那么必然其中一张牌在一个人手上，另一张牌在另一人手上，但我们不能确定是那张。

其实这是个2-sat的XOR。

因为是双向边，我们可以直接用并查集。

然后有些牌的归属在一开始就已经被制定了。

如果A和!A在同一个并查集里边或者其并查集的取值都一开始确定，并且两者相同，那么无解。其他都有解。

#include<cstdio>
    #include<cstring>
    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;
    }

转载于:https://www.cnblogs.com/autsky-jadek/p/7296641.html