Gym 101128 B Black Vienna

题意

有A-Z 26张牌，现在从中抽出3张牌，并把剩下的23张牌分给选手1和2，现在有n次询问，每次询问一个选手是否有某两张牌，和选手的回答。回答说自己有这两张牌中的几张，问拿出的三张牌有多少种方案能够满足这n个条件？n<=50

分析

个人感觉这个题是个很不错的题呢。

并查集的应用,有点像那道“关押罪犯”的升级版？www.cnblogs.com/LQLlulu/p/8819599.html

数据很小，只有26张牌和50个询问。那么三重循环枚举抽哪三张牌。对于每次抽出的三张牌，判断一下能否满足这n个询问，如果满足的话ans++。

但是怎么判断？

因为只有两个玩家，那么对于每张牌，如果这张牌没有被抽走，那么要么属于玩家1，要么属于玩家2。对于大多数情况我们都可以通过记录每张牌的归属判断是否冲突。

但是有一种特殊情况：

此时两张牌都未被抽走，而且回答是1。也就是说，这两张牌里有一张是属于这个人，另一张属于另一个玩家。那么我们此时没法直接记录。因为我们并不能知道哪张牌属于谁，只能确定这两张牌不属于同一个人！没错！这句话表明了要用并查集！

对于每个上述的情况：x=find(a),y=find(b)，如果x和y相等说明两者在同一个人手中，那么直接返回false，否则的话我们把他们和另一个的补集相连，p[x]=find(b+n)，p[y]=find(a+n)。这代表两者不在同一个集合（因为只有两个集合，所以满足敌人的敌人就是朋友）。

然后对于每个并查集就分给一个人，判断是否会冲突，如果冲突返回false。

如果上述都没有冲突，则返回true。

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <iostream>

 using namespace std;

 const int maxn=+;

 int n;

 int p[maxn];

 struct Node{

     char s[];

     int who;

     int num;

 }node[maxn];

 int ans;

 int Wh[maxn],val[maxn];

 int find(int x){

     return p[x]==x?x:p[x]=find(p[x]);

 }

 bool check(int A,int B,int C){

     for(int i=;i<=;i++)p[i]=i;

     memset(Wh,-,sizeof(Wh));

     bool ok=;

     for(int i=;i<=n;i++){

         int a=node[i].s[]-'A'+;

         int b=node[i].s[]-'A'+;

         int w=node[i].who;

       //  cout<<a<<" "<<b<<" "<<node[i].num<<endl;

         if(node[i].num==){

             if(a==A||a==B||a==C||b==A||b==B||b==C){

                 //cout<<"-1"<<endl;

                 ok=;

                 break;

             }

             if((Wh[a]==(w^))||(Wh[b]==(w^))){

                 ok=;

                 break;

             }

            // cout<<-1<<endl;

             Wh[a]=w,Wh[b]=w;

         }

         if(node[i].num==){

             if((a==A||a==B||a==C)&&(b==A||b==B||b==C))

                 continue;

             else if(a==A||a==B||a==C){

                 if(Wh[b]==w){

                     ok=;

                     break;

                 }

                 Wh[b]=(w^);

             }

             else if(b==A||b==B||b==C){

                 if(Wh[a]==w){

                     ok=;

                     break;

                 }

                 Wh[a]=(w^);

             }

             else{

                 if(Wh[a]==w||Wh[b]==w){

                     ok=;

                     break;

                 }

                 Wh[a]=(w^),Wh[b]=(w^);

             }

         }

         if(node[i].num==){

             if((a==A||a==B||a==C)&&(b==A||b==B||b==C)){

                 ok=;

                 break;

             }

             else if(a==A||a==B||a==C){

                 if(Wh[b]==(w^)){

                     ok=;

                     break;

                 }

                 Wh[b]=w;

             }

             else if(b==A||b==B||b==C){

                 if(Wh[a]==(w^)){

                     ok=;

                     break;

                 }

                 Wh[a]=w;

             }else{

                 int x=find(a),y=find(b);

                 if(x==y){

                     ok=;

                     break;

                 }

                 p[x]=find(b+);

                 p[y]=find(a+);

             }

         }

     }

     if(!ok)return false;

     memset(val,-,sizeof(val));

     for(int i=;i<=;i++){

         if(Wh[i]!=-){

             int f=find(i);

             if(val[f]==

                (Wh[i]^)){

                 ok=;

               //  cout<<-1<<endl;

                 break;

             }

             val[f]=Wh[i];

             f=find(i+);

            // cout<<Wh[i]<<endl;

             if(val[f]==Wh[i]){

                // cout<<val[f]<<" "<<Wh[i]<<endl;

                 ok=;

                 break;

             }

             val[f]=(Wh[i]^);

         }

     }

     if(!ok)return false;

     for(int i=;i<=;i++){

         int x=find(i),y=find(i+);

         if(x==y||(val[x]==val[y]&&val[x]!=-)){

             ok=;

             break;

         }

     }

     if(!ok)return false;

     return true;

 }

 int main(){

     ans=;

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         scanf("%s%d%d",node[i].s,&node[i].who,&node[i].num);

         node[i].who--;

     }

     for(int i=;i<=;i++){

         for(int j=i+;j<=;j++){

             for(int k=j+;k<=;k++){

                 if(check(i,j,k))

                     ans++;

             }

         }

     }

     cout<<ans;

 return ;

 }

巴特西

Gym 101128 B Black Vienna

最新文章

热门文章