首页 > 代码库 > Codeforces 442A Borya and Hanabi

Codeforces 442A Borya and Hanabi

2024-07-10 01:42:26   221人阅读

有五种花色 外加 五种点数 共25张牌，每次有n张牌，主人知道这n张牌中有哪些牌，并且哪种牌有几张，但是不知道具体是哪张牌，他可以问某种花色，然后知道了哪几张是该花色，也可以问点数，然后就知道了哪几张是这个点数。最终可以把所有牌都确定下来，问最少要询问几次。

这个题目一开始想到枚举（事实证明最后就是枚举），然后又想到二分图去了，。。主要是这个花色对应点数，连成边之后太像二分图了，而且感觉为了得到所有的牌，隐隐约约有点像 DAG上的最小点覆盖。。。而且看了下样例，有点像，所以就去敲二分图去了，结果。。。擦。跪了

其实还是要回到枚举上面来，总共才10个点是不是，用个状态压缩才1000，关键是怎么判断当前枚举是合法的，正向考虑会比较复杂，我想了半天没想到一个比较轻松的方法，但是反向考虑就舒服多了，假设我枚举了k个点，也就是说这k个点（包括花色与点数）都是要询问的，那么不成立的条件有这样：

1.某种牌的两个端点都没询问，而且不止一次（如果只是一次的话，是可以的，因为主人知道所有的牌，这张牌放到最后即可）。

2.某种牌只访问了一个端点，但是这个端点又不止被访问一次（这样的话就肯定无法确定是哪张牌）

所以只要出现了以上两种情况中的一种，即不合法。

#include <iostream>#include <cstdio>#include <cstring>using namespace std;int mat[15][15];char ch[6]={‘A‘,‘R‘,‘G‘,‘Y‘,‘W‘,‘B‘};int bitcount(int x){    if (x==0) return 0;    else return bitcount(x>>1)+(x&1);}bool judge(int x){    int num[20];    memset(num,0,sizeof num);    int tot=0;    for (int i=1;i<=5;i++)    {        for (int j=6;j<=10;j++){            if (mat[i][j]){                if (((1<<(i-1))&x) && (!((1<<(j-1))&x))) num[i]++;                if ((!((1<<(i-1))&x)) && ((1<<(j-1))&x)) num[j]++;                if ((!((1<<(i-1))&x)) && (!((1<<(j-1))&x))) tot++;            }        }    }    //cout<<tot<<endl;    if (tot>1) return 0;    for (int i=1;i<=10;i++){            if (num[i]>1) return 0;    }    return 1;}int main(){    int n;    char s[3];    while (scanf("%d",&n)!=EOF)    {        memset(mat,0,sizeof mat);        for (int i=0;i<n;i++){            scanf("%s",s);            int a=0;            for (int i=1;i<=5;i++){                if (s[0]==ch[i]){a=i;break;}            }            int b=s[1]-‘0‘+5;            mat[a][b]=1;           // cout<<a<<" "<<b<<endl;        }        int ans=100;        for (int i=0;i<(1<<11);i++){            if (judge(i)){                ans=min(ans,bitcount(i));            }                //cout<<ans<<endl;                //if (ans==0) break;            }        printf("%d\n",ans);    }    return 0;}

 


联系
我们