算法訓(xùn)練 黑白無(wú)常 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB 提交此題 問(wèn)題描述 某寢室的同學(xué)們?cè)趯W(xué)術(shù)完之后準(zhǔn)備玩一個(gè)游戲：游戲是這樣的，每個(gè)人頭上都被貼了一張白色或者黑色的紙，現(xiàn)在每個(gè)人都會(huì)說(shuō)一句話“我看到x張白色紙條和y張黑色的紙條”，又已知每個(gè)頭上貼著白色紙的人說(shuō)的是真話、每個(gè)頭上貼著黑色紙的人說(shuō)的是謊話，現(xiàn)在要求你判斷哪些人頭上貼著的是白色的紙條，如果無(wú)解輸出“NoSolution.”；如果有多組解，則把每個(gè)答案中貼白條的人的編號(hào)按照大小排列后組成一個(gè)數(shù)（比如第一個(gè)人和第三個(gè)人頭上貼著的是白紙條，那么這個(gè)數(shù)就是13；如果第6、7、8個(gè)人都貼的是白紙條，那么這個(gè)數(shù)就是678）輸出最小的那個(gè)數(shù)（如果全部都是黑紙條也滿足情況的話，那么輸出0） 輸入格式 第一行為一個(gè)整數(shù)n，接下來(lái)n行中的第i行有兩個(gè)整數(shù)x和y，分別表示第i個(gè)人說(shuō)“我看到x張白色紙條和y張黑色的紙條”。 輸出格式 一行。如果無(wú)解輸出“NoSolution.”。否則輸出答案中數(shù)值（具體見(jiàn)問(wèn)題描述）最小的那個(gè)，如果全部都是黑紙條也滿足情況的話，那么輸出0 樣例輸入 2 1 0 1 0 樣例輸出 0 樣例輸入 5 3 1 0 4 1 3 4 0 1 3 樣例輸出 35 數(shù)據(jù)規(guī)模和約定 n<=8
解題思路為 如果一個(gè)人為真，那么x+1，y 的帽子數(shù)量可能為真或者為假 否則 一定為假， 那么x，y+1 的帽子數(shù)量絕對(duì)為假。 因?yàn)闇y(cè)試數(shù)據(jù)有誤差 第二組和倒數(shù)前兩組為錯(cuò)誤數(shù)據(jù)
#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 為真，那么這個(gè)人說(shuō)的話可能為真或者為假。 { 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."; }}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
