[NOIP2003 提高组] 侦探推理(C++,字符串)

2023-10-06 23:59

本文主要是介绍[NOIP2003 提高组] 侦探推理(C++,字符串),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

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

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

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

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

输入格式

输入由若干行组成。

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

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

往后有 P P P 行,每行开始是某个同学的名宇,紧跟着一个冒号和一个空格,后面是一句证词,符合前表中所列格式。证词每行不会超过 250 250 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 % 100\% 100% 数据,满足 1 ≤ M ≤ 20 1\le M\le 20 1M20 0 ≤ N ≤ M 0\le N\le M 0NM 1 ≤ P ≤ 100 1\le P\le 100 1P100

【题目来源】

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是罪犯

因为玩家们的名字可能是这样的AAAAAAAAAA

那么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;
}

这篇关于[NOIP2003 提高组] 侦探推理(C++,字符串)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/154740

相关文章

MySQL常用字符串函数示例和场景介绍

《MySQL常用字符串函数示例和场景介绍》MySQL提供了丰富的字符串函数帮助我们高效地对字符串进行处理、转换和分析,本文我将全面且深入地介绍MySQL常用的字符串函数,并结合具体示例和场景,帮你熟练... 目录一、字符串函数概述1.1 字符串函数的作用1.2 字符串函数分类二、字符串长度与统计函数2.1

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发;同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符

C# $字符串插值的使用

《C#$字符串插值的使用》本文介绍了C#中的字符串插值功能,详细介绍了使用$符号的实现方式,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录$ 字符使用方式创建内插字符串包含不同的数据类型控制内插表达式的格式控制内插表达式的对齐方式内插表达式中使用转义序列内插表达式中使用

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()?它的作用是什么?类比一下:二、join()的作用总结三、join()怎么

详解MySQL中JSON数据类型用法及与传统JSON字符串对比

《详解MySQL中JSON数据类型用法及与传统JSON字符串对比》MySQL从5.7版本开始引入了JSON数据类型,专门用于存储JSON格式的数据,本文将为大家简单介绍一下MySQL中JSON数据类型... 目录前言基本用法jsON数据类型 vs 传统JSON字符串1. 存储方式2. 查询方式对比3. 索引

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被