[NOIP2003 提高组] 侦探推理（C++，字符串）

题目描述

明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：

证词中出现的其他话，都不列入逻辑推理的内容。

明明所知道的是，他的同学中有 $N$ 个人始终说假话，其余的人始终说真。

现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！

输入格式

输入由若干行组成。

第一行有三个整数，$M,N$ 和 $P$。$M$ 是参加游戏的明明的同学数，$N$ 是其中始终说谎的人数，$P$ 是证言的总数。

接下来 $M$ 行，每行是明明的一个同学的名字（英文字母组成，没有空格，全部大写）。

往后有 $P$ 行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过 $250$ 个字符。

输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。

输出格式

如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出 Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出 Impossible。

样例 #1

样例输入 #1

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??

样例输出 #1

MIKE

提示

对于 $100\%$ 数据，满足 $1\le M\le 20$，$0\le N\le M$，$1\le P\le 100$。

【题目来源】

NOIP 2003 提高组第二题

解题思路：

这道题其实并不难，考察的是最基本的模拟和枚举

模拟侦探推理的过程，关键在于找出矛盾的证词

枚举每一个可能的罪犯和一周中的七天，然后判断是否符合条件

下面的代码虽然很繁琐但是思路是很清晰的，大致思路如下：

枚举每一个人、每一天，然后开始推理

每轮开始假设每个人都是未知状态-1，说真话的人是1，说假话的人是0

（1）对于每一句话进行判断，根据现有条件判断这句话是真话还是假话

（2）判断说话人的状态

（3）如果状态是未知状态，则赋予其状态，并累加说真话（假话）的人数

（4）如果状态是已知的，那么判断其说的话是否与状态相矛盾（如说假话的人说了真话），如果矛盾，那么本轮推理结束，把end_index标志赋值为true

结束了？当然没有

思路很好想，但本题易错点并不在这里，而是在于从字符串中提取信息，要不然这篇题解也不会以字符串为标题了

首先最重要的一点是绝对不要假设字符串会以某种顺序出现

比如说你是这么处理字符串的：把每一个单词输入后装到容器里面，然后如果容器中的第一个单词是I，第三个单词不是guilty，那么你认为这句话是I am not guilty.

但这就错了

输入的数据甚至可能不是单词，如I am not guity.

然后，你不能假设字符串中出现了Name is guilty.就判断这句话说的是Name是罪犯

因为玩家们的名字可能是这样的A、AA、AAA、AAAA…

那么A is guilty.和AA is guilty.中均含有A is guilty.

你就又输出错误答案了

当然，还有就是你不能认为他们说的话不是废话

比如，一个人可以说How are you?、What's your name?

甚至一个人可能不会说话

所以一个人的状态在每轮推理结束后仍然可能是-1，也就是未定状态，你可以把他归于任何一类之中

所以判断一轮推断是否有效是根据说真话的人 <= m - n && 说假话的人 <= n

最后再说一点就是换行符的问题

Linux中的换行符和Windows的换行符是不同的，要注意判题系统是什么操作系统

Linux下的换行符是\r，而Windows下的换行符是\r + \n

这会导致什么问题呢？

要知道，对于Linux的getchar()来说，Windows的换行符是两个字符，也就会导致靠getchar()判断循环终止条件的代码的崩溃

以上就是错误点啦~（都是我错的QAQ）

p.s.：关于代码中的sentence结构体中的info数组

对于人：info[0]是人的索引，info[1]是这句话对此人是否为罪犯的判断

对于日期：info[0]是0（固定），info[1]是这句话对日期的判断

最后，AC代码入戏

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <string.h>
using namespace std;
const int max_m = 20;int m, n, p;
map<string, int>name2index;//name to index
struct sent { int info[2]; };
vector<sent>sents[max_m + 1];//index to sentences
map<string, int>week2index;//week to index
int states[max_m + 1];void get_sent(int index) {string s;sent sentence;getline(cin, s);//读入句子for (map<string, int>::iterator it = week2index.begin(); it != week2index.end(); it++) {//日期类型if (s.find(it->first) != -1) {sentence.info[0] = 0;sentence.info[1] = it->second;sents[index].push_back(sentence);return;}}if (s.find("I am guilty.") != -1) {//罪人指定一sentence.info[0] = index;sentence.info[1] = 1;sents[index].push_back(sentence);return;}else if (s.find("I am not guilty.") != -1) {sentence.info[0] = index;sentence.info[1] = 0;sents[index].push_back(sentence);return;}int ret, ret2;if ((ret = s.find(" is guilty.")) != -1) {//罪人指定二ret2 = s.rfind(' ', ret - 1);sentence.info[0] = name2index[s.substr(ret2 + 1, ret - 1)];sentence.info[1] = 1;sents[index].push_back(sentence);return;}else if ((ret = s.find(" is not guilty.")) != -1) {ret2 = s.rfind(' ', ret - 1);sentence.info[0] = name2index[s.substr(ret2 + 1, ret - 1)];sentence.info[1] = 0;sents[index].push_back(sentence);return;}
}void init_week() {week2index.insert(pair<string, int>("Today is Monday.", 1));week2index.insert(pair<string, int>("Today is Tuesday.", 2));week2index.insert(pair<string, int>("Today is Wednesday.", 3));week2index.insert(pair<string, int>("Today is Thursday.", 4));week2index.insert(pair<string, int>("Today is Friday.", 5));week2index.insert(pair<string, int>("Today is Saturday.", 6));week2index.insert(pair<string, int>("Today is Sunday.", 7));
}int main() {init_week();cin >> m >> n >> p;string name;for (int i = 1; i <= m; i++) {cin >> name;name2index.insert(pair<string, int>(name, i));}for (int i = 1; i <= p; i++) {cin >> name;name = name.substr(0, name.size() - 1);get_sent(name2index[name]);}int cnt = 0, cnt2 = 0, find = 0;bool end_index = false;for (int guilty = 1; guilty <= m; guilty++) {//假设罪犯for (int day = 1; day <= 7; day++) {//假设日期cnt = 0;//说假话的人数cnt2 = 0;//说真话的人数memset(states + 1, -1, sizeof(int) * max_m);//初始化未知身份end_index = false;//开始推断for (int i = 1; i <= m && !end_index; i++) {//遍历每一个人for (int j = 0; j < int(sents[i].size()); j++) {//遍历这个人说过的话if (sents[i][j].info[0]) {//关于人if (sents[i][j].info[1]) {//xx是罪犯if (guilty != sents[i][j].info[0]) {//假话if (states[i] != -1) {//身份已知if (states[i] != 0) {end_index = true;//与已知矛盾，假设错误，本轮推断结束break;}}else {//身份未知states[i] = 0;//标记说假话的身份cnt++;//说假话人数++}}else {//真话if (states[i] != -1) {//身份已知if (states[i] != 1) {end_index = true;//与已知矛盾，假设错误，本轮推断结束break;}}else {//身份未知states[i] = 1;//标记说真话身份cnt2++;//说真话的人++}}}else {//xx不是罪犯if (guilty == sents[i][j].info[0]) {//假话if (states[i] != -1) {//身份已知if (states[i] != 0) {end_index = true;//与已知矛盾，假设错误，本轮推断结束break;}}else {//身份未知states[i] = 0;//标记说假话的身份cnt++;//说假话人数++}}else {//真话if (states[i] != -1) {//身份已知if (states[i] != 1) {end_index = true;//与已知矛盾，假设错误，本轮推断结束break;}}else {//身份未知states[i] = 1;//标记说真话的身份cnt2++;//说真话的人++}}}}else {//关于日期if (day != sents[i][j].info[1]) {//假话if (states[i] != -1) {//身份已知if (states[i] != 0) {end_index = true;//与已知矛盾，假设错误，本轮推断结束break;}}else {//身份未知states[i] = 0;//标记说假话的身份cnt++;//说假话人数++}}else {//真话if (states[i] != -1) {//身份已知if (states[i] != 1) {end_index = true;//与已知矛盾，假设错误，本轮推断结束break;}}else {//身份未知states[i] = 1;//标记说真话的身份cnt2++;//说真话的人++}}}}}//一轮推断完成if (cnt <= n && cnt2 <= m - n && !end_index) {//推断出凶手if (find == 0)find = guilty;else if (find != guilty) {//推断出多个凶手cout << "Cannot Determine" << endl;return 0;}}}}//结论if (find) {for (map<string, int>::iterator it = name2index.begin(); it != name2index.end(); it++) {if (it->second == find) {cout << it->first << endl;}}}else cout << "Impossible" << endl;//未推断出凶手return 0;
}