算法訓練 黑白無常 時間限制：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."; }}新聞熱點
疑難解答
