算法训练 黑白无常
时间限制：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
1 0
1 0
样例输出
0
样例输入
5
3 1
0 4
1 3
4 0
1 3
3 1
0 4
1 3
4 0
1 3
样例输出
35
数据规模和约定
n<=8
示例代码：
/*
白纸条： 1
黑纸条： 0
*/
#include<iostream>
using namespace std; int n; //人数
int cnt; //有多少种方案
int color[]; //保存每个人头上纸条的颜色
int talk[][]; //保存每个人说话的内容
int result[]; //保存所有白纸条人序号组成的自然数 int colorNum(int x, int col) //检查除自己外还有多少人为白纸条 / 黑纸条
{
int num = ;
for (int j = ; j < n; j++)
{
if (j == x)
continue;
else if(color[j] == col)
num++;
}
return num;
} bool check() //检查说话的真假
{
bool flag;
for (int i = ; i < n; i++)
{
flag = (colorNum(i, ) == talk[i][] && colorNum(i, ) == talk[i][]);
if (color[i] == ) //白纸人说真话
{
if (!flag)
return false;
}
else //黑纸人说假话
{
if (flag)
return false;
}
}
return true;
} void dfs(int now)
{
if (now == n)
{
if (check()) //如果检查正确
{
int temp = ;
for (int i = ; i < n; i++)
{
if (color[i] == ) //计算此种方案时白纸人序号组成的自然数
temp = temp * + i + ;
}
result[cnt++]=temp;
}
return;
} color[now] = ; //白纸人
dfs(now+); color[now] = ; //黑纸人
dfs(now+);
} int main()
{
cin >> n; cnt = ; for (int i = ; i < n; i++)
cin >> talk[i][] >> talk[i][]; dfs(); if (cnt == ) //如果没有白纸人
cout<<"NoSolution."<<endl;
else //找出所有方案中最小的一个数
{
int minNum = ;
for (int i = ; i < cnt; i++)
{
if (minNum > result[i])
minNum = result[i];
}
cout << minNum;
} return ;
}