首页 > 代码库 > 【并查集】Gym - 101128B - Black Vienna
【并查集】Gym - 101128B - Black Vienna
有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;
}
【并查集】Gym - 101128B - Black Vienna
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。