菜鸡的题解016——黑白无常（C++）

想到了之前做的数位DP题目，于是开写！

用一个数字的二进制代表选择情况，第i位上为1代表第i-1个人说的话是正确的，这样写也不用写DFS（虽然DFS熟练了写起来也不会很麻烦），不过感觉挺好。

例如：

7的二进制是111代表第1，2，3个人说的话是正确的，其他人说的都是错的，这样写相当于是遍历吧。
参考代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<set>
#include<sstream>
#include<cstring>
#include<utility>
using namespace std;
typedef long long ll;
typedef long l;
const int N = 200020;
int n,a[3][9],maxa=1<<20;
int main(){
	cin>>n;
	int maxn=(1<<n)-1,f=0;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i][1],&a[i][2]);
	}
	for(int i=0;i<=maxn;i++){
		int ok=1,m=0,g=0;
		for(int j=1;j<=n;j++){
			if(i&(1<<j-1)){
				g++;
				m=1+a[j][1];
			}
		}
		if(g!=m)continue;
		for(int j=1;j<=n;j++){
			if(i&(1<<j-1)){
				if(m!=1+a[j][1]){
					ok=0;break;
				}
			}
			else{
				if(m==a[j][1]){
					ok=0;break;
				}
			}
		}
		if(ok){
			int maxb=0;
			for(int j=1;j<=n;j++){
				if(i&(1<<j-1))maxb=maxb*10+j;
			}
			if(maxb<maxa)maxa=maxb;
			f++;
		}
	}
	if(f==0)cout<<"NoSolution.";
	else cout<<maxa;
}