蓝桥杯 黑白无常 二进制枚举

问题描述

　　某寝室的同学们在学术完之后准备玩一个游戏：游戏是这样的，每个人头上都被贴了一张白色或者黑色的纸，现在每个人都会说一句话“我看到x张白色纸条和y张黑色的纸条”，又已知每个头上贴着白色纸的人说的是真话、每个头上贴着黑色纸的人说的是谎话，现在要求你判断哪些人头上贴着的是白色的纸条，如果无解输出“NoSolution.”；如果有多组解，则把每个答案中贴白条的人的编号按照大小排列后组成一个数（比如第一个人和第三个人头上贴着的是白纸条，那么这个数就是13；如果第6、7、8个人都贴的是白纸条，那么这个数就是678）输出最小的那个数（如果全部都是黑纸条也满足情况的话，那么输出0）

输入格式

　　第一行为一个整数n，接下来n行中的第i行有两个整数x和y，分别表示第i个人说“我看到x张白色纸条和y张黑色的纸条”。

输出格式

　　一行。如果无解输出“NoSolution.”。否则输出答案中数值（具体见问题描述）最小的那个，如果全部都是黑纸条也满足情况的话，那么输出0

样例输入

2
1 0
1 0

样例输出

0

样例输入

5
3 1
0 4
1 3
4 0
1 3

样例输出

35

数据规模和约定

　　n<=8

这是我做过的第五道用二进制数枚举所有情况的题目，这道题其他方法都太复杂，直接从00000000到11111111枚举完所有情况，然后逐个判断每种情况是否符合题意即可，参考自https://blog.csdn.net/qq_42835910/article/details/88206011

#include <bits/stdc++.h>
using namespace std;
int a[10][2]; //记录每个人实际说的话 
int t[10][2]; //记录枚举的每种情况下，每个人所能看到的黑白数量 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i][1] >> a[i][0];
    }    
    int b[10]; //b[j]记录枚举的每种情况下第j个人说的是真话还是假话 
    int ans = -1;
    for (int i = 0; i < (1 << n); i++) { //从0~2^n-1遍历所有情况 
        memset(t, 0, sizeof t); //每一次都把t数组清空 
        for (int j = 0; j < n; j++) { //在i这种情况下，生成b数组 
            b[j] = (bool) (i & (1 << j)); //根据二进制下i的每一位是0还是i，决定第j个人是黑还是白，用b[j]记录 
            for (int k = 0; k < n; k++) { //更新其他人看周围人的情况 
                if(k != j) {
                    t[k][b[j]]++;
                }
            }
        }
        bool ok = true; //标志变量 
        for (int j = 0; j < n; j++) {
            if (b[j]) { //如果j说的真话，但是和题目答案不符时，就说明当前的i的这种情况不行，返回false 
                if (t[j][0] != a[j][0] || t[j][1] != a[j][1]) {
                //就是说，如果j说的是真话，但j这个人看到的情况，和题目给的情况不同，就gg 
                    ok = false;
                    break;
                }
            } else {  //j说的假话，但是和题目答案相符false 
                if (t[j][0] == a[j][0] && t[j][1] == a[j][1]){
                //就是说，如果j说的是假话，但j这个人看到的情况，和题目给的情况相同，就gg 
                    ok = false;
                    break;
                }
            }
        }
        if (ok) {
            ans = 0;
            for (int j = 0; j < n; j++) {
                if (b[j]) {
                    ans = ans * 10 + j + 1;
                }
            }
            break;
        }
    }
    if (ans < 0) {
        cout << "NoSolution." << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}