Time Limit: 1 second Memory Limit: 50 MB
【問題描述】
明明同學最近迷上了偵探漫畫《柯南》并沉醉于推理游戲之中，于是他召集了一群同學玩推理游戲。游戲的內容是這樣的，明明的同學們先商量好由其中的一個人充當罪犯（在明明不知情的情況下），明明的任務就是找出這個罪犯。接著，明明逐個詢問每一個同學，被詢問者可能會說：證詞中出現的其他話，都不列入邏輯推理的內容。 明明所知道的是，他的同學中有N個人始終說假話，其余的人始終說真。 現在，明明需要你幫助他從他同學的話中推斷出誰是真正的兇手，請記住，兇手只有一個！
【輸入】
共m+p+1行；第一行是有二個整數，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）； M是參加游戲的明明的同學數，N是其中始終說謊的人數，P是證言的總數。接下來M行，每行是明明的一個同學的名字（英文字母組成，沒有主格，全部大寫）。 往后有P行，每行開始是某個同學的名宇，緊跟著一個冒號和一個空格，后面是一句證詞，符合前表中所列格式。證詞每行不會超過250個字符。 輸入中不會出現連續的兩個空格，而且每行開頭和結尾也沒有空格。【輸出】
如果你的程序能確定誰是罪犯，則輸出他的名字；如果程序判斷出不止一個人可能是 罪犯，則輸出 Cannot Determine；如果程序判斷出沒有人可能成為罪犯，則輸出 Impossible。【輸入樣例】
3 1 5MIKECHARLESKATEMIKE:I am guilty.MIKE:Today is Sunday.CHARLES:MIKE is guilty．KATE:I am guilty.KATE:How are you??【輸出樣例】
MIKE【題目鏈接】:http://noi.qz5z.com/viewtask.asp?id=b302
【題意】
【題解】 題目描述不清啊 可以確定兇手的有兩種情況 一種是確定m-1個人不是兇手。 另外一種是確定了一個人是兇手。 這里impossible的情況有兩種 一種是全都不是兇手,另外一種就是無法達到滿足的要求,即N個人說謊然后P條話都不沖突; 然后無法確定的就是剩余的; 有點迷。 不用理這種題。 (冒號后面還有一個空格。。。) O(2^m)*p爆搜就好 【完整代碼】
#include <cstdio>#include <cmath>#include <algorithm>#include <string>#include <iostream>#include <map>#include <cstring>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%lld",&x)typedef pair<int, int> pii;typedef pair<LL, LL> pll;const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };const double pi = acos(-1.0);const int N = 20+10;const int P = 100 + 50;struct abc{ int id, who,author; int xingqi;};int m, n, p,tot,ma = 0;bool bo[N],is[N],notis[N],xingqi[N];string name[N];string t;char ts[300];abc xinxi[P];map <string, int> dic;map <string, int> dic2;void sear_ch(){ int today = -1; memset(xingqi, true, sizeof xingqi); memset(is, false, sizeof is), memset(notis, false, sizeof notis); rep1(i, 1, tot) if (bo[xinxi[i].author]) { if (xinxi[i].id == 2) { if (today == -1) { if (!xingqi[xinxi[i].xingqi]) return; today = xinxi[i].xingqi; } else { if (today != xinxi[i].xingqi) return; } } else { int y = xinxi[i].who; if (xinxi[i].id == 0) { if (is[y]) return; notis[y] = true; } else { if (notis[y]) return; is[y] = true; } } } else if (!bo[xinxi[i].author]) { if (xinxi[i].id == 2) { if (today == xinxi[i].xingqi) return; xingqi[xinxi[i].xingqi] = false; } else { int y = xinxi[i].who; if (xinxi[i].id == 0) { if (notis[y]) return; is[y] = true; } else//說y是兇手 { if (is[y]) return; notis[y] = true; } } } int cnt = 0,j = -1,cntnot = 0; rep1(i, 1, m) { if (is[i]) cnt++, j = i; if (notis[i]) cntnot++; } if (cnt == 1) { cout << name[j] << endl; exit(0); } if (cntnot == m - 1) { rep1(i, 1, m) if (!notis[i]) cout << name[i] << endl; exit(0); } if (cntnot == m) puts("Impossible"); else puts("Cannot Determine"); exit(0);}void dfs(int x, int now){ if (x > m) { if (now == n) { sear_ch(); } return; } bo[x] = false; dfs(x + 1, now + 1); bo[x] = true; dfs(x + 1, now);}int main(){ //freopen("F://rush.txt", "r", stdin); memset(bo, true, sizeof bo); dic2["Monday"] = 1, dic2["Tuesday"] = 2, dic2["Wednesday"] = 3, dic2["Thursday"] = 4; dic2["Friday"] = 5, dic2["Saturday"] = 6, dic2["Sunday"] = 7;//處理出星期對應的數字 rei(m), rei(n), rei(p); rep1(i, 1, m) { cin >> name[i]; dic[name[i]] = i;//為每個名字搞hash對應到它的標號 } char tt = getchar(); rep1(i, 1, p) { cin.getline(ts, 300); t = string(ts); t += ' ';//在末尾加上一個空格,方便獲取信息 int po = t.find(':', 0); string who = t.substr(0, po);//把說話的人提取出來 t.erase(0, po + 2);//把說話人和冒號去掉 string s[5]; rep1(j, 1, 4)//只找前4個單詞 { s[j] = ""; if (t == "") { rep1(k, j + 1, 4) s[k] = ""; break;//空掉了就結束 } po = t.find(' ', 0); s[j] = t.substr(0, po);//否則把那個單詞搞出來 t.erase(0, po + 1);//連同空格刪掉 } if (s[3] == "") continue;//如果沒有3個單詞肯定不是信息 if (s[1] == "I" && s[2] == "am" && s[3] == "guilty.") xinxi[++tot].who = dic[who],xinxi[tot].id = 1,xinxi[tot].author = dic[who]; if (s[1] == "I" && s[2] == "am" && s[3] == "not" && s[4]== "guilty.") xinxi[++tot].who = dic[who], xinxi[tot].id = 0, xinxi[tot].author = dic[who]; if (s[2] == "is" && s[3] == "guilty.") xinxi[++tot].who = dic[s[1]], xinxi[tot].id = 1, xinxi[tot].author = dic[who]; if (s[2] == "is" && s[3] == "not" && s[4] == "guilty.") xinxi[++tot].who = dic[s[1]], xinxi[tot].id = 0, xinxi[tot].author = dic[who]; if (s[4] != "") continue; s[3].erase(int(s[3].size()) - 1, 1); if (s[1] == "Today" && s[2] == "is" && dic2[s[3]]) xinxi[++tot].id = 2, xinxi[tot].xingqi = dic2[s[3]],xinxi[tot].author = dic[who]; } dfs(1, 0); puts("Impossible"); return 0;}新聞熱點
疑難解答
