符文锁 题解

发现 $N\le15$，考虑状压。

---

状压思路

定义一个 $N$ 位的二进制数为该选择方案的表示，如 $(11)_{10} = (1011)_{2}$，即表示该方案拿了 1 号、2 号和 4 号。

实现

不难思考，将所有已有条件压入 vector 中或两个数组中，表示每种方案的可取性，然后一次暴力枚举每一种条件，即枚举 $0\to2^{N}-1$，与每一个条件对照，累加 ans，得出答案。
时间复杂度 $O(qN\times2^N)$。

---

AC 代码

#include<iostream>
#include<vector>
#include<set>
using namespace std;
int n,q,m;
vector<int> tru;
vector<int> fal; 
bool check(int t){
    for(int i=0;i<tru.size();i++){
        int cnt=0;
        for(int j=0;j<n;j++){
            if(tru[i]&(1<<j) && t&(1<<j))cnt++;
        }
        if(cnt<m)return false;
    }
    for(int i=0;i<fal.size();i++){
        int cnt=0;
        for(int j=0;j<n;j++){
            if(fal[i]&(1<<j) && t&(1<<j))cnt++;
        }
        if(cnt>=m)return false;
    }
    return true;
}
int main(){
    cin>>n>>q>>m;
    for(int i=0;i<q;i++){
        int k,a,t=0;
        cin>>k;
        for(int j=0;j<k;j++){
            cin>>a;
            t^=1<<(a-1);
        }
        char c;
        cin>>c;
        if(c=='o'){
            tru.push_back(t);
        }
		else{
            fal.push_back(t);
        }
    }
    int ans=0;
    int N=1<<n;
    for(int i=0;i<N;i++){
        if(check(i)){
            ans++;
        }
    }
	cout<<ans;
}