©2020-2024 ioDraw All rights reserved,
Privacy Policy
侦探推理
题目描述
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：
证词内容：
I am guilty.
I am not guilty.
XXX is guilty.
XXX is not guilty.
Today is XXX
证词含义：
我是罪犯
我不是罪犯
xxx 是罪犯（ xxx 表示某个同学的名字）
xxx 不是罪犯
今天是xxx （ xxx 表示星期几，是 Monday Tuesday wednesday Thursday Fnday Saturday 其中之一）
证词中出现的其他话，都不列入逻辑推理的内容。明明所知道的是，他的同学中有 N
个人始终说假话，其余的人始终说真。现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！
输入描述
输入若干行。
第一行有三个整数，M（1 ≤ M ≤ 20）、N（1 ≤ N ≤ M）和P（1 ≤ P ≤ 100）；M 是参加游戏的明明的同学数，N
是其中始终说谎的人数，P 是证言的总数。
接下来 M 行，每行是明明的一个同学的名字（英文字母组成，没有主格，全部大写）。
往后有 P 行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过 250 个字符。
输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。
输出描述
如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出 Cannot
Determine；如果程序判断出没有人可能成为罪犯，则输出 Impossible。
输入输出样例
输入
3 1 5
MIKE
CHARLES
KATE
MIKE: I am guilty.
MIKE: Today is Sunday.
CHARLES: MIKE is guilty.
KATE: I am guilty.
KATE: How are you??
输出
MIKE
运行限制
最大运行时间：1s
最大运行内存：128M
/* 大模拟问题 */ #include <bits/stdc++.h> using namespace std; //m：总人数 n：始终说谎人数
p：说话的总数 int m, n, p; //judge[i]：第i句话是真是假，真1假-1不清楚0 w[i]：第i局话是编号多少的的人说的 int
judge[21], w[200]; //err：矛盾标记 nx：当前可能的罪犯 int err, nx; //name[i]：所有人名字（编号为1~m）
say[i]：所有人说的话 day[i]：所有星期几名字 string name[100], say[200]; string day[10] = {"0",
"Today is Sunday.", "Today is Monday.", "Today is Tuesday.", "Today is
Wednesday.", "Today is Thursday.", "Today is Friday.", "Today is Saturday.", };
//sset函数标记一个人说话真假 void sset(int who, int x) { if (judge[who] == -x) err = 1;
//如果一个人既说真话又说假话，则矛盾 else judge[who] = x; } int main() { cin >> m >> n >> p; for
(int i = 1; i <= m; i++) { cin >> name[i]; } for (int i = 1; i <= p; i++) {
string nm; cin >> nm; //输入说这句话人的名字 nm.erase(nm.end() - 1);
//删除nm中冒号，便于判断这句话编号多少的的人说的 for (int j = 1; j <= m; j++) { if (name[j] == nm)
w[i] = j; } getline(cin, say[i]); say[i].erase(say[i].begin());
//删除say[i]中的起始空格 } for (int td = 1; td <= 7; td++) { //暴力枚举今天是星期几 for (int px =
1; px <= m; px++) { //暴力枚举罪犯编号是几号 err = 0; //清除标记 memset(judge, 0,
sizeof(judge)); //初始化为不清楚真假 //依次判断每一句说的话 for (int i = 1; i <= p; i++) { int who
= w[i]; //说这句话人的编号 //如果一个人是罪犯，并且说自己是罪犯，则说的就是真话，否则就是假话 if (say[i] == "I am
guilty.") sset(who, px == who ? 1 : -1); //如果一个人不是罪犯，并且说自己不是罪犯，则说的就是真话，否则就是假话
if (say[i] == "I am not guilty.") sset(who, px != who ? 1 : -1);
//如果一个人说今天是星期几，说对了就是真话，说错了就是假话 for (int j = 1; j <= 7; j++) { if (say[i] ==
day[j]) sset(who, j == td ? 1 : -1); } //如果一个人说其他人不是罪犯，说对了就是真话，说错了就是假话 for (int
j = 1; j <= m; j++) { if (say[i] == name[j] + " is guilty.") sset(who, j == px
? 1 : -1); if (say[i] == name[j] + " is not guilty.") sset(who, j != px ? 1 :
-1); } } int cnt = 0; //说假话的人数 int no = 0; //不清楚真假的的人数 for (int i = 1; i <= m;
i++) { if (judge[i] == -1) //假 cnt++; if (judge[i] == 0) //不清楚 no++; }
//如果出现Impossible的情况，err = 1，出现矛盾 //如果cnt<=n<=cnt+no,即假设合理 if (!err && cnt <= n
&& cnt + no >= n) { if (nx && nx != px) { //如果出现了两个合理的罪犯 cout << "Cannot
Determine"; return 0; } else { nx = px; } } } } if (!nx) cout << "Impossible";
else cout << name[nx]; return 0; }