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

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int a[10][2]; //记录每个人实际说的话 
 4 int t[10][2]; //记录枚举的每种情况下，每个人所能看到的黑白数量 
 5 int main() {
 6     int n;
 7     cin >> n;
 8     for (int i = 0; i < n; i++) {
 9         cin >> a[i][1] >> a[i][0];
10     }    
11     int b[10]; //b[j]记录枚举的每种情况下第j个人说的是真话还是假话 
12     int ans = -1;
13     for (int i = 0; i < (1 << n); i++) { //从0~2^n-1遍历所有情况 
14         memset(t, 0, sizeof t); //每一次都把t数组清空 
15         for (int j = 0; j < n; j++) { //在i这种情况下，生成b数组 
16             b[j] = (bool) (i & (1 << j)); //根据二进制下i的每一位是0还是i，决定第j个人是黑还是白，用b[j]记录 
17             for (int k = 0; k < n; k++) { //更新其他人看周围人的情况 
18                 if(k != j) {
19                     t[k][b[j]]++;
20                 }
21             }
22         }
23         bool ok = true; //标志变量 
24         for (int j = 0; j < n; j++) {
25             if (b[j]) { //如果j说的真话，但是和题目答案不符时，就说明当前的i的这种情况不行，返回false 
26                 if (t[j][0] != a[j][0] || t[j][1] != a[j][1]) {
27                 //就是说，如果j说的是真话，但j这个人看到的情况，和题目给的情况不同，就gg 
28                     ok = false;
29                     break;
30                 }
31             } else {  //j说的假话，但是和题目答案相符false 
32                 if (t[j][0] == a[j][0] && t[j][1] == a[j][1]){
33                 //就是说，如果j说的是假话，但j这个人看到的情况，和题目给的情况相同，就gg 
34                     ok = false;
35                     break;
36                 }
37             }
38         }
39         if (ok) {
40             ans = 0;
41             for (int j = 0; j < n; j++) {
42                 if (b[j]) {
43                     ans = ans * 10 + j + 1;
44                 }
45             }
46             break;
47         }
48     }
49     if (ans < 0) {
50         cout << "NoSolution." << endl;
51     } else {
52         cout << ans << endl;
53     }
54     return 0;
55 }