P1039 侦探推理（洛谷）
2024-10-09 08:23:54
昨天做了一个非常神奇的题，告诉我们做题之前一定要好好检测评测姬！
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：
证词中出现的其他话，都不列入逻辑推理的内容。 明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。 现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！ 输入格式
输入由若干行组成，第一行有三个整数，M(1≤M≤20)、N(1≤N≤M)和P(1≤P≤100)；M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证言的总数。 接下来M行，每行是明明的一个同学的名字（英文字母组成，没有空格，全部大写）。 往后有P行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过250个字符。 输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。 输出格式
如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出 "Cannot Determine"；如果程序判断出没有人可能成为罪犯，则输出 "Impossible"。 输入输出样例
输入 #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
哎呀呀，这个题看起来好难的样子，让计算器斯烤，他怕不是把我当成了神？
（神明的声音响起）“人类啊，你直接遍历日期和罪犯，如果合理就完事了对吧，有多个罪犯的情况就去处理啊，只需要O(7M(P+2M))的效率（应该）就可以了。真是愚蠢的人类……”
哎呀神明显灵了！但貌似神明说的明显不够缜密啊。我再来补充一下吧。
如果有一个人说真话了又说假话了，他是说真话的还是说假话的呢？
比如我们设定今天周1，他自己是凶手。但他说今天周2，他自己是凶手，他是说真话的还是说假话的?
虽然这种情况存在，但有这种情况的时候肯定假设错误了。不知道为啥的同学肯定没好好看题……
明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。
所以说，如果有个人在这次的设定中既说真话又说假话，那我们就可以换一个假设了（与题目描述不符）。
继续继续
会不会有一些狡诈的同学只说废话？
答案是会的（我下载数据看了）
对于这种人怎么办呢？他可能是说假话的人设，也可能是说真话的。
有个大侦探说过:“排除所有不可能，剩下的再不可思议，也是可能。”但这个情况并不是不可能……
我们把他看成可能，如果能确定凶手都是可能，也就是说，如果我们确定说假话的人数在n以下，而且说谎人数+不确定人数>n。这个情况就是合理的。
我们就可以把凶手标记一下。如果下次遇到不同的凶手，就可以说没有解了。
当然我之前想过会不会有同学叫“罪犯”，他说我是罪犯是说我叫“罪犯”，而不是我是犯罪者的意思？
或者叫周一周二周三……
真的有
但题目很友善（不友善没法做了），姓名全是大写，说话内容全是小写（good）。
所以大家不要胡思乱想了。
接下来就是讲解模拟的时候了：
本人把他的证词分为了1，2，3三种类型。
类型1是说周几的，用rq(日期)表记
类型2是说罪犯是谁，用zfbh(罪犯编号)表记
类型3是说谁不是罪犯，用zfbh(罪犯编号)标记
（没错他俩一样，我懒得定义新变量了，反正都是和罪犯有关）
然后开始写判断，判断周几简单粗暴
（嘻嘻打表真香）
判断类型2和3也是打表啦（快乐）
然后就是一些和谐的模拟，就是判断和你设定的相符不相符，然后做一些简单处理，我写在注释里吧。
好啦好啦，看看我写的很长很长的代码吧：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
struct hehe
{
long long lx,bh,rq,zfbh;//这个是证言情况的数组,lx是类型,zfbh是罪犯编号,rq是日期,bh是证人编号。
}sz[205];
string pdrq[10]={" ","Today is Monday.","Today is Tuesday.","Today is Wednesday.","Today is Thursday.","Today is Friday.","Today is Saturday.","Today is Sunday."};//打表判断周几
long long n,m,p,bqc,sjhd,xs,bcl;//bqc是不清楚的意思,表示有多少人一直说胡话。sjhd是说假话的,这个名字很清楚吧。
string name,zname,s[100];
string zy;
map<string,int>ys;
map<string,int>mp;
int main()
{
cin>>m>>n>>p;
for(int i=1;i<=m;i++)
{
cin>>s[i];//读入名字
mp[s[i]]=i;//本名字的编号为i
}
for(int i=1;i<=p;i++)
{
cin>>name;//输入名字,他输入证言是“名字+：+空格+证言+回车 ”我为什么打回车先按下不表,等等再说。
zname="";
for(int j=0;j<name.length()-1;j++)
{
zname+=name[j];//zname才是name,name是名字+:
}
sz[i].bh=mp[zname];
getline(cin,zy);//带空格我选getline。
zy.erase(zy.end()-1);//截取，就是删掉后面的回车（评测姬和我的情况不一样导致的）
for(int j=1;j<=7;j++)
{
if(zy==" "+pdrq[j])//他在说日期哎
{
sz[i].lx=1;//lx为1
sz[i].rq=j;//日期为j
}
}
int bj=0;
if(zy==" I am guilty.")//他在说罪犯哎
{
sz[i].zfbh=mp[zname];
sz[i].lx=2;
}else if(zy==" I am not guilty.")//他在说清白的人哎
{
sz[i].zfbh=mp[zname];
sz[i].lx=3;
}else
{
for(int j=1;j<=m;j++)
{
if(zy==" "+s[j]+" is guilty.")//他在说罪犯哎
{
sz[i].zfbh=j;
sz[i].lx=2;
}else if(zy==" "+s[j]+" is not guilty.")//他在说清白的人哎
{
sz[i].zfbh=j;
sz[i].lx=3;
}
}
}
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=7;j++)//暴力枚举罪犯编号和日期
{
bcl=0;
for(int u=1;u<=m;u++)//初始化
{
ys[s[u]]=0;
}
for(int u=1;u<=p;u++)
{
if(sz[u].lx==1)//判断证言类型
{
if(sz[u].rq==j)
{
if(ys[s[sz[u].bh]]==0)
{
ys[s[sz[u].bh]]=1;
}else if(ys[s[sz[u].bh]]!=1)//前后不符，就是也说真话也说假话(后面的差不多一样，不写了)
{
bcl=1;
}
}else
{
if(ys[s[sz[u].bh]]==0)
{
ys[s[sz[u].bh]]=-1;
}else if(ys[s[sz[u].bh]]!=-1)
{
bcl=1;
}
}
}else if(sz[u].lx==2)
{
if(sz[u].zfbh==i)
{
if(ys[s[sz[u].bh]]==0)
{
ys[s[sz[u].bh]]=1;
}else if(ys[s[sz[u].bh]]!=1)
{
bcl=1;
}
}else
{
if(ys[s[sz[u].bh]]==0)
{
ys[s[sz[u].bh]]=-1;
}else if(ys[s[sz[u].bh]]!=-1)
{
bcl=1;
}
}
}else if(sz[u].lx==3)
{
if(sz[u].zfbh!=i)
{
if(ys[s[sz[u].bh]]==0)
{
ys[s[sz[u].bh]]=1;
}else if(ys[s[sz[u].bh]]!=1)
{
bcl=1;
}
}else
{
if(ys[s[sz[u].bh]]==0)
{
ys[s[sz[u].bh]]=-1;
}else if(ys[s[sz[u].bh]]!=-1)
{
bcl=1;
}
}
}
}
if(bcl==1)//这个设定是不合理的。
{
continue;
}
bqc=0;
sjhd=0;
for(int u=1;u<=m;u++)//判断说谎的人和不确定的人。
{
if(ys[s[u]]==0)
{
bqc++;
}
if(ys[s[u]]==-1)
{
sjhd++;
}
}
if(sjhd<=n&&bqc+sjhd>=n)//合理
{
if(xs!=i&&xs!=0)//之前有过不一样的凶手，也就是说凶手可能有多个，不符合题目描述，退出。
{
cout<<"Cannot Determine"<<endl;
exit(0);
}
xs=i;//这是唯一的凶手
}
}
}
if(xs==0)//根本没有凶手
{
cout<<"Impossible"<<endl;
exit(0);
}
cout<<s[xs];//输出
return 0;
}
这个题真是恶心啊，就说到这里吧（是的结束了）。
最新文章
- actionlib的身世之谜
- C Primer Plus_第三章_数据和C_复习题与编程练习
- HDU 2719 The Seven Percent Solution
- 修改session的存储机制
- hdu 1542 Atlantis 段树区，并寻求，，，尼玛真坑人数据，不要打开一小阵！
- vue使用resource发送ajax请求
- zend framework 1 安装教程
- Less的模式匹配
- decorator（修饰器）的业务应用
- SQLServer修改表数据
- java入门--学习地址
- mysql导入自定义函数不成功的解决方法
- SpringBoot处理静态资源的两种方式
- sql 中，如何获取两个日期之前月数、周数、天数
- 【git】gitignore
- CVPR2019 | Mask Scoring R-CNN 论文解读
- 2017-2018-2 20155224『网络对抗技术』Exp8：Web基础
- (转)Maven学习-处理资源文件
- R语言缺点
- iOSCocoaPods的安装使用和常见问题