蓝桥杯算法训练 ALGO-114 黑白无常

ゝ一世哀愁。 2023-10-06 09:41 1阅读 0赞

算法训练 黑白无常

时间限制：1.0s 内存限制：256.0MB

问题描述

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

输入格式

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

输出格式

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

样例输入

2  
1 0  
1 0

样例输出

样例输入

5  
3 1  
0 4  
1 3  
4 0  
1 3

样例输出

数据规模和约定

n<=8

示例代码：

1 /*
     2     白纸条： 1
     3     黑纸条： 0 
     4 */
     5 #include<iostream>
     6 using namespace std;
     7 
     8 int n;                //人数 
     9 int cnt;              //有多少种方案 
    10 int color[10];       //保存每个人头上纸条的颜色 
    11 int talk[10][2];      //保存每个人说话的内容 
    12 int result[100];     //保存所有白纸条人序号组成的自然数 
    13 
    14 int colorNum(int x, int col)    //检查除自己外还有多少人为白纸条 / 黑纸条 
    15 {   
    16     int num = 0; 
    17     for (int j = 0; j < n; j++)
    18     {  
    19         if (j == x)
    20             continue;      
    21         else if(color[j] == col)
    22             num++;    
    23     } 
    24     return num;
    25 }
    26 
    27 bool check()    //检查说话的真假
    28 {
    29     bool flag;
    30     for (int i = 0; i < n; i++)
    31     {
    32         flag = (colorNum(i, 1) == talk[i][0] && colorNum(i, 0) == talk[i][1]);
    33         if (color[i] == 1)    //白纸人说真话
    34         {
    35             if (!flag)             
    36                return false;  
    37         }  
    38         else                //黑纸人说假话 
    39         {
    40             if (flag)
    41                return false;
    42         }
    43     }
    44     return true;
    45 }
    46   
    47 void dfs(int now)
    48 {
    49     if (now == n)
    50     {
    51         if (check())    //如果检查正确
    52         {
    53             int temp = 0;              
    54             for (int i = 0; i < n; i++)
    55             {
    56                 if (color[i] == 1)      //计算此种方案时白纸人序号组成的自然数
    57                       temp = temp * 10 + i + 1;
    58                }            
    59             result[cnt++]=temp;  
    60         }     
    61         return;  
    62     }
    63      
    64     color[now] = 1;    //白纸人  
    65     dfs(now+1);
    66     
    67     color[now] = 0;    //黑纸人   
    68     dfs(now+1);  
    69 }
    70 
    71 int main()
    72 {
    73     cin >> n;
    74     
    75     cnt = 0;
    76     
    77     for (int i = 0; i < n; i++)
    78         cin >> talk[i][0] >> talk[i][1];
    79          
    80     dfs(0);  
    81         
    82     if (cnt == 0)    //如果没有白纸人 
    83         cout<<"NoSolution."<<endl;
    84     else            //找出所有方案中最小的一个数 
    85     {
    86         int minNum = 987654321;
    87         for (int i = 0; i < cnt; i++)
    88         {
    89             if (minNum > result[i])
    90                 minNum = result[i];
    91         } 
    92         cout << minNum;  
    93     }  
    94 
    95     return 0;
    96 }