Atcoder 356 C - Keys 二进制枚举

原题链接：

https://atcoder.jp/contests/abc356/tasks/abc356_c 

C - Keys：

问题陈述

您有 N 个编号为1,2,…,N 的密钥。
其中一些是真钥匙，其他都是假钥匙。

有一扇门，门 X，你可以插入任意数量的钥匙。只有插入至少 K 把真钥匙，X 门才会打开。

你已经对这些钥匙进行了 M 次测试。 i 次测试过程如下：

• 您将 Ci 把 Ai,1​,Ai,2​,…,Ai,Ci​​ 把钥匙插入了 X 号门。
• 测试结果用一个英文字母 RiRi​ 表示。
  • Ri​= o`表示在 i /-测试中门X打开了。
  • Ri​= x "表示在 i /-次测试中门X没有打开。

有 2^N 种可能的钥匙组合，其中哪些是真钥匙，哪些是假钥匙。在这些组合中，找出与任何测试结果都不矛盾的组合数。
给定的测试结果有可能是错误的，没有任何组合满足条件。在这种情况下，请报告 0 。

限制因素

• N 、 M 、 K 、 Ci​ 和 Ai,j​ 是整数。
• 1≤K≤N≤15
• 1≤M≤100
• 1≤Ci​≤N
• 1≤Ai,j​≤N
• Ai,j≠Ai,k,如果 j≠kj=k .
• Ri​ 是 o 或 x。

思路讲解：

 __builtin_popcount(s&S[i])>=K 记录了s,和S[i]的二进制表示中，相同位置都为1的位数，

 __builtin_popcount此函数用来统计，二进制表示当中1的个数
一共n把钥匙，每种钥匙都有2种情况，真和假，因此，一共就有2的n次幂种可能，我们枚举每一种情况，看看有多少种情况是符合题干的即可、如果全为假，即为000，如果全为真表示为111，是2的n次幂-1，故数字枚举0到2的n次幂-1，要求如果有>=k把钥匙和能开门这两个条件是要同时成立的，否则这个方案就不是一个合理的方案

代码实现：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;

typedef long long ll;

int main()
{
    int N,M,K;
    cin>>N>>M>>K;
    vector<int> S(M),R(M);
    for(int i=0;i<M;i++)
    {
        int C; cin>>C;
        for(int j=0;j<C;j++)
        {
            int x; cin>>x;
            x--;
            S[i]|=1<<x;//作用是将S[i]的第x位设为1，因为二进制是从第0位开始的，因此我们需要x--;
        }
        char r; cin>>r;
        R[i]=(r=='o'); //如果这种情况下是可以打开的，则R[i]=1;
    }
    int ans=0;
    for(int s=0;s<(1<<N);s++) //枚举2的n次幂种可能
    {
        int ok=1;
        for(int i=0;i<M;i++)
        {
            if( (__builtin_popcount(s&S[i])>=K) != R[i]) //若两者不是同时成立的，则代表出现了矛盾，则这种方案不满足
            {
                ok=0;
            }
        }
        ans+=ok;
    }
    cout<<ans<<endl;
    return 0;
}