蓝桥杯算法训练VIP-黑白无常 （C++代码）

解题思路:





注意事项:

/*
    白纸条： 1
    黑纸条： 0 
*/
#include<iostream>
using namespace std;

int n;                //人数 
int cnt;              //有多少种方案 
int color[10];       //保存每个人头上纸条的颜色 
int talk[10][2];      //保存每个人说话的内容 
int result[100];     //保存所有白纸条人序号组成的自然数 

int colorNum(int x, int col)    //检查除自己外还有多少人为白纸条 / 黑纸条 
{   
    int num = 0; 
    for (int j = 0; j < n; j++)
    {  
        if (j == x)
            continue;      
        else if(color[j] == col)
            num++;    
    } 
    return num;
}

bool check()    //检查说话的真假
{
    bool flag;
    for (int i = 0; i < n; i++)
    {
        flag = (colorNum(i, 1) == talk[i][0] && colorNum(i, 0) == talk[i][1]);
        if (color[i] == 1)    //白纸人说真话
        {
            if (!flag)             
               return false;  
        }  
        else                //黑纸人说假话 
        {
            if (flag)
               return false;
        }
    }
    return true;
}
  
void dfs(int now)
{
    if (now == n)
    {
        if (check())    //如果检查正确
        {
            int temp = 0;              
            for (int i = 0; i < n; i++)
            {
                if (color[i] == 1)      //计算此种方案时白纸人序号组成的自然数
                      temp = temp * 10 + i + 1;
               }            
            result[cnt++]=temp;  
        }     
        return;  
    }
     
    color[now] = 1;    //白纸人  
    dfs(now+1);
    
    color[now] = 0;    //黑纸人   
    dfs(now+1);  
}

int main()
{
    cin >> n;
    
    cnt = 0;
    
    for (int i = 0; i < n; i++)
        cin >> talk[i][0] >> talk[i][1];
         
    dfs(0);  
        
    if (cnt == 0)    //如果没有白纸人 
        cout<<"NoSolution."<<endl;
    else            //找出所有方案中最小的一个数 
    {
        int minNum = 987654321;
        for (int i = 0; i < cnt; i++)
        {
            if (minNum > result[i])
                minNum = result[i];
        } 
        cout << minNum;  
    }  

    return 0;
}

参考代码: