题目描述
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：
证词内容：
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
算法实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
/*大模拟问题*/ #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;} |
以上所述是小编给大家介绍的C++趣味算法之侦探推理，希望对大家有所帮助。在此也非常感谢大家对服务器之家网站的支持！
原文链接：https://blog.csdn.net/Hello_world_n/article/details/121630843
