CodeForces 442A Borya and Hanabi

点击打开链接

题意： 

    每张牌五个花色，五个大小。

     你有n张牌，且知道有什么牌，但是不知道确切哪张是哪张。

     你可以进行两种查询，问知道每张牌确切是那张最少查询多少次。

   两种操作分别是

   1，查询某个花色的都是那几张牌，

   2，查询某个大小都是那几张牌。

题解：

   总共才十种情况，状态压缩也就1024种，所以直接暴力枚举，

   然后每种情况判断查询能否成功；

   如果一张牌的两个权值都被查询，则一定可以知道是什么，所以 找出这样的牌，把他权值查询次数-1；

   然后如果出现未查询过任何权值的牌，且大于一张，则不成立。

   如果某张牌只有一个权值被查询，且该权值被查询多次，也不成立。

#include<bits/stdc++.h>

#define ll long long
using namespace std;
const int maxn=1111;
map<char,int>m,v;
map<string,int>M;
string str[111];
int nu[10];
int n,ans=10,cnt=0;
bool judge(int sta){
    int flag=0,ret=0;
    for(int i=0;i<10;++i) nu[i]=v[i];
    for(int i=1;i<=cnt;++i){
        int t1=str[i][0];
        int t2=str[i][1];
        if((sta&(1<<t1))&&(sta&(1<<t2))){
            nu[t1]--;
            nu[t2]--;
        }
    }
    for(int i=1;i<=cnt;++i){
        int t1=str[i][0];
        int t2=str[i][1];
        if((sta&(1<<t1))&&nu[t1]>1&&(sta&(1<<t2))==0)
             return false;
        if((sta&(1<<t2))&&nu[t2]>1&&(sta&(1<<t1))==0)
             return false;
        if((sta&(1<<t1))==0&&(sta&(1<<t2))==0) ret++;
        if(ret>1) return false;
    }
    return true;
}
void init(){
    m['R']=0,m['G']=1,m['B']=2,m['Y']=3,m['W']=4;
    m['1']=5,m['2']=6,m['3']=7,m['4']=8,m['5']=9;
    v.clear();
}
int main(){
    init();
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        string s;
        cin>>s;
        if(!M[s]){
            str[++cnt][0]=m[s[0]];
            str[cnt][1]=m[s[1]];
            v[m[s[0]]]++;
            v[m[s[1]]]++;
        }
        M[s]=1;
    }
    for(int stat=0;stat<=(1<<10);++stat){
        int t=0;
        for(int j=0;j<=10;++j)
            if(stat&(1<<j)) t++;
        if(judge(stat)) ans=min(ans,t);
    }
    printf("%d\n",ans);
    return 0;
}