题目描述题目要求根据若干居民说的话推断出居民的类型神、人、恶魔以及当前是白天还是黑夜。神总是说真话恶魔总是说谎人在白天说真话、晚上说谎。每句话的格式如A: I am divine.、B: A is human.、C: It is day.等。输入多组对话输出可推断的事实。输入格式输入包含多个对话。每个对话以整数nnn开头表示语句数量。接下来nnn行每行一个语句。输入以n0n 0n0结束。输出格式对于每个对话输出Conversation #X然后若无一致的可能情况输出This is impossible.若无法推断任何事实输出No facts are deducible.否则输出所有可推断的事实人物类型按字母顺序然后时间。每个对话输出后跟一个空行。样例输入1 A: I am divine. 1 A: I am lying. 1 A: I am evil. 3 A: B is human. B: A is evil. A: B is evil. 0输出Conversation #1 No facts are deducible. Conversation #2 This is impossible. Conversation #3 A is human. It is night. Conversation #4 A is evil. B is divine.题目分析本题的核心是枚举所有可能的赋值555个人每人有333种类型加上白天/黑夜222种共35×24863^5 \times 2 48635×2486种检查哪些赋值与所有语句一致然后找出在所有一致赋值中保持不变的结论。枚举方法使用回溯法枚举所有可能的赋值。对每个赋值检查所有语句的真假是否符合说话者的类型和当前时间。统计所有一致赋值。若没有一致赋值输出This is impossible.若所有一致赋值的某些结论相同则这些结论可被推断。语句解析根据语句内容判断该语句的真假并与说话者类型比较。复杂度分析枚举486486486种情况每次检查最多505050条语句可接受。代码实现// Island of Logic// UVa ID: 592// Verdict: Accepted// Submission Date: 2017-04-23// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorstringstatements;constintDAY1,NIGHT2;constintDIVINE1,EVIL2,HUMAN3;intfacts[8]{0},presented[8]{0};intresult[8]{0},accepted;string kinds[]{divine,evil,human,lying};boolmatched(){for(autos:statements){intsomeones.front()-A1,others[3]-A1;if(s.find(am lying)!s.npos){returnfalse;}elseif(s.find(day)!s.npos){if(!((facts[someone]DIVINEfacts[0]DAY)||(facts[someone]EVILfacts[0]NIGHT)||facts[someone]HUMAN))returnfalse;}elseif(s.find(night)!s.npos){if(!((facts[someone]DIVINEfacts[0]NIGHT)||(facts[someone]EVILfacts[0]DAY)))returnfalse;}elseif(s.find(am divine)!s.npos){if(!(facts[someone]DIVINE||facts[someone]EVIL||(facts[someone]HUMANfacts[0]NIGHT)))returnfalse;}elseif(s.find(am not divine)!s.npos){if(!(facts[someone]HUMANfacts[0]DAY))returnfalse;}elseif(s.find(am evil)!s.npos){if(!(facts[someone]HUMANfacts[0]NIGHT))returnfalse;}elseif(s.find(am not evil)!s.npos){if(!(facts[someone]DIVINE||facts[someone]EVIL||(facts[someone]HUMANfacts[0]DAY)))returnfalse;}elseif(s.find(am human)!s.npos){if(!(facts[someone]EVIL||(facts[someone]HUMANfacts[0]DAY)))returnfalse;}elseif(s.find(am not human)!s.npos){if(!(facts[someone]DIVINE||(facts[someone]HUMANfacts[0]NIGHT)))returnfalse;}elseif(s.find(is divine)!s.npos){if(!((facts[someone]DIVINEfacts[other]DIVINE)||(facts[someone]EVILfacts[other]!DIVINE)||(facts[someone]HUMAN((facts[0]DAYfacts[other]DIVINE)||(facts[0]NIGHTfacts[other]!DIVINE)))))returnfalse;}elseif(s.find(is evil)!s.npos){if(!((facts[someone]DIVINEfacts[other]EVIL)||(facts[someone]EVILfacts[other]!EVIL)||(facts[someone]HUMAN((facts[0]DAYfacts[other]EVIL)||(facts[0]NIGHTfacts[other]!EVIL)))))returnfalse;}elseif(s.find(is human)!s.npos){if(!((facts[someone]DIVINEfacts[other]HUMAN)||(facts[someone]EVILfacts[other]!HUMAN)||(facts[someone]HUMAN((facts[0]DAYfacts[other]HUMAN)||(facts[0]NIGHTfacts[other]!HUMAN)))))returnfalse;}elseif(s.find(is lying)!s.npos){if(!((facts[someone]DIVINEfacts[other]EVIL)||(facts[someone]DIVINEfacts[other]HUMANfacts[0]NIGHT)||(facts[someone]EVILfacts[other]DIVINE)||(facts[someone]EVILfacts[other]HUMANfacts[0]DAY)||(facts[someone]HUMAN((facts[0]DAYfacts[other]EVIL)||(facts[0]NIGHTfacts[other]DIVINE)))))returnfalse;}elseif(s.find(is not divine)!s.npos){if(!((facts[someone]DIVINEfacts[other]!DIVINE)||(facts[someone]EVILfacts[other]DIVINE)||(facts[someone]HUMAN((facts[0]DAYfacts[other]!DIVINE)||(facts[0]NIGHTfacts[other]DIVINE)))))returnfalse;}elseif(s.find(is not evil)!s.npos){if(!((facts[someone]DIVINEfacts[other]!EVIL)||(facts[someone]EVILfacts[other]EVIL)||(facts[someone]HUMAN((facts[0]DAYfacts[other]!EVIL)||(facts[0]NIGHTfacts[other]EVIL)))))returnfalse;}elseif(s.find(is not human)!s.npos){if(!((facts[someone]DIVINEfacts[other]!HUMAN)||(facts[someone]EVILfacts[other]HUMAN)||(facts[someone]HUMAN((facts[0]DAYfacts[other]!HUMAN)||(facts[0]NIGHTfacts[other]HUMAN)))))returnfalse;}elseif(s.find(is not lying)!s.npos){if(!((facts[someone]DIVINEfacts[other]DIVINE)||(facts[someone]DIVINEfacts[other]HUMANfacts[0]DAY)||(facts[someone]EVILfacts[other]EVIL)||(facts[someone]EVILfacts[other]HUMANfacts[0]NIGHT)||(facts[someone]HUMAN((facts[0]DAYfacts[other]!EVIL)||(facts[0]NIGHTfacts[other]!DIVINE)))))returnfalse;}}returntrue;}voiddfs(intdepth){if(depth6){if(matched()){if(accepted0){for(inti0;i6;i)result[i]facts[i];}else{for(inti0;i6;i)if(result[i]0facts[i]0result[i]!facts[i])result[i]0;}accepted;}}else{if(depth0){for(intj1;j2;j){facts[depth]j;dfs(depth1);facts[depth]0;}}else{if(presented[depth]){for(intj1;j3;j){facts[depth]j;dfs(depth1);facts[depth]0;}}elsedfs(depth1);}}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intn,cases0;string line;while(cinn,n0){statements.clear();memset(presented,0,sizeof(presented));cin.ignore(1024,\n);for(inti1;in;i){getline(cin,line);statements.push_back(line);for(charcA;cE;c)if(line.find(c)!line.npos)presented[c-A1]1;}accepted0;memset(facts,0,sizeof(facts));memset(result,-1,sizeof(result));dfs(0);coutConversation #cases\n;if(accepted0)coutThis is impossible.\n;elseif(accepted1){for(inti1;i6;i)if(result[i]0)cout(char)(Ai-1) is kinds[result[i]-1].\n;coutIt is ((result[0]1)?day:night).\n;}else{boolexistfalse;for(inti0;i6;i)if(result[i]0){existtrue;break;}if(!exist)coutNo facts are deducible.\n;else{for(inti1;i6;i)if(result[i]0)cout(char)(Ai-1) is kinds[result[i]-1].\n;if(result[0]0)coutIt is ((result[0]1)?day:night).\n;}}cout\n;}return0;}