麻豆小视频在线观看_中文黄色一级片_久久久成人精品_成片免费观看视频大全_午夜精品久久久久久久99热浪潮_成人一区二区三区四区

首頁 > 學院 > 開發設計 > 正文

藍橋杯 算法訓練 黑白無常 后臺測試數據有誤

2019-11-14 09:18:13
字體:
來源:轉載
供稿:網友

算法訓練 黑白無常 時間限制: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."; }}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 羞羞视频免费网站男男 | h色视频在线观看 | 免费一级欧美大片视频在线 | 免费一级a毛片免费观看 | 国产毛片毛片毛片 | 一级做a爱片性色毛片高清 日本一区二区在线看 | 狠狠干夜夜草 | 在线看成人av | 亚洲91精品 | 久久久久久久久成人 | 国产99久久精品一区二区300 | 日本成人二区 | 成人午夜在线免费视频 | 免费黄色小网站 | 亚洲一区二区三区精品在线观看 | 国产毛片在线高清视频 | 久久撸视频 | 31freehdxxxx欧美 | 在线视频观看国产 | 日韩色视频 | 亚洲成年人免费网站 | 免费毛片观看 | 国产午夜精品久久久 | 国产精品夜色视频一级区 | 广州毛片| 91视频久久 | 黄色av网站免费看 | 国产在线精品一区二区三区 | h视频在线免费观看 | 高颜值美女啪啪 | 久久精品亚洲国产奇米99 | 精品一区免费 | 综合日韩av| 日韩精品久久久久久 | 色悠悠久久久久 | 久久69精品久久久久久国产越南 | 成人aaaaa片毛片按摩 | 免费在线观看成年人视频 | 中文日韩字幕 | 视频一区 日韩 | 国产99久久久久久免费看农村 |