算法训练 黑白无常 时间限制：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 样例输出 0 样例输入 5 3 1 0 4 1 3 4 0 1 3 样例输出 35 数据规模和约定 n<=8
解题思路为 如果一个人为真，那么x+1，y 的帽子数量可能为真或者为假 否则 一定为假， 那么x，y+1 的帽子数量绝对为假。 因为测试数据有误差 第二组和倒数前两组为错误数据
#include <iostream>#include <cstdio>#include <cstring>#include <iomanip>#include <cmath>#include <map>using namespace std;int a[20],b[20],n;int tag[20][20];int mins;int ww;void bfs(int l,int r,int t,int z,int f){ //cout<<l<<' '<<r<<' '<<t<<' '<<z<<endl; if(t==n+1) { ww=1; //cout<<l<<' '<<r<<endl; if(z<mins&&(tag[l][r]==1||(tag[l][r]==-1&&f==0))) mins=z; return; } int x=a[t]; int y=b[t]; if(f==0)//确定某人是否为真 { if(tag[x+1][y]==-1)//x+1 y为真 { tag[x+1][y]=1; bfs(l+1,r,t+1,z*10+t,1); tag[x+1][y]=-1; } if(tag[x][y+1]==0||tag[x][y+1]==-1) //否则一定为假 { int w=tag[x][y+1]; tag[x][y+1]=0; bfs(l,r+1,t+1,z,0); tag[x][y+1]=w; } } else { if(tag[x+1][y]==1)//若x+1，y 为真，那么这个人说的话可能为真或者为假。 { bfs(l+1,r,t+1,z*10+t,f); bfs(l,r+1,t+1,z,f); } else //否则一定为假 { int w=tag[x][y+1]; tag[x][y+1]=0; bfs(l,r+1,t+1,z,f); tag[x][y+1]=w; } }}int main(){ while(cin>>n) { ww=0; memset(tag,-1,sizeof(tag)); mins=10000; for(int i=1;i<=n;i++) { cin>>a[i]>>b[i]; while(b[i]>10) { b[i]/=10; //cout<<b[i]<<endl; } } bfs(0,0,1,0,0); if(ww)cout<<mins; else cout<<"NoSolution."; }}新闻热点
疑难解答
