洛谷 P1039 NOIp2003提高组 侦探推理 题解【模拟】【字符串】【枚举】
点击量：646
细节比较多的一道题。疯狂stl……
题目描述
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：
证词内容 证词含义 I am guilty. 我是罪犯 I am not guilty. 我不是罪犯 XXX is guilty. XXX是罪犯（XXX表示某个同学的名字） XXX is not guilty. XXX不是罪犯 Today is XXX. 今天是XXX（XXX表示星期几，是Monday Tuesday Wednesday Thursday Friday Saturday Sunday 其中之一） 证词中出现的其他话，都不列入逻辑推理的内容。
明明所知道的是，他的同学中有\(N\)个人始终说假话，其余的人始终说真。
现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！
输入输出格式
输入格式：
输入由若干行组成，第一行有三个整数，\(M(1\le M\le 20)\)、\(N(1\le N\le M)\)和\(P(1\le P\le 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
题解：
这个题数据范围比较小，考虑枚举，但是枚举谁说真话谁说假话也比较耗时，但是我们发现日期只有一天，罪犯也只有一个，考虑枚举罪犯是谁，和今天是星期几。
在读入每一句话时，把这一句的主人（即冒号前的人）对应到它的编号，这里推荐使用std::map，然后判断种类，如果语句不合法就不读这句话，并用gets()把这一行读完进入下一句。如果发现第一个单词是人名，则用\(\tt map\)找到它的编号，然后看它是肯定句还是否定句。对于每一个点开一个vector用来存它说过的合法的话，区分一下这句话是说人的信息还是日期，如果说人的信息还需要对应到对象，这里最好把\(\tt “I”\)转化为自己的名字。
接着就可以枚举罪犯和日期了，因为有的人自始至终都没有说过一句合法的话，这样的人既可能说真话也可能说假话，我们用一个变量\(ran\)来存有多少个这样的人，剩下的人根据它第一句话来确定它是说真话还是说假话。如果一个人前后矛盾，即前面说真话后面说假话，那么这次枚举就不合法，可以直接跳到下次枚举去。
在一次成功的枚举中，我们得知了有多少人说假话，有多少人不确定，假设说假话的人有\(cnt\)个，并有\(ran\)个人不确定，那么当要求说假话的人数在\([cnt,cnt+ran]\)范围内就合法。
如果一个罪犯被多次确定，是不会对答案造成额外影响的，但是当确定一个罪犯时发现前面已经确定一个人了，此时就要输出Cannot Determine了。当程序结束时还没有找到一个罪犯，则输出Impossible。找到罪犯了输出名字即可。
stl还是非常方便的，std::string用来存名字并进行字符串处理；std::map用来映射人名；std::vector用来存每个人说的话。不过这个题有一个比较坑的地方，必须要确定一个人说的一句话每个单词都合法后，才能把这整句话当作合法的。&&一定要注意单词后面的冒号和句号！
Code：
#include<iostream>
#include<map>
#include<vector>
#include<cstdio>
using namespace std;
map<string,int> per;//存人名
string nm[25];
map<string,int> day;//映射日期
struct sta
{
int u;//u表示主语
bool to;//0表示罪犯，1表示日期
bool is;//表示肯定或否定
sta(int u,bool to,bool is)
{
this->u=u;
this->to=to;
this->is=is;
}
sta(){}
};
vector<sta> v[25];
char asdfghjkl[1000];//用来读废掉的语句
int main()
{
int n,m,p;
cin>>n>>m>>p;
string s;
for(int i=1;i<=n;++i)
{
cin>>s;
per[s]=i;
nm[i]=s;
}
per["Today"]=n+1;
day["Monday."]=1;//句号是因为答案
day["Tuesday."]=2;
day["Wednesday."]=3;
day["Thursday."]=4;
day["Friday."]=5;
day["Saturday."]=6;
day["Sunday."]=7;
for(int i=1;i<=p;++i)
{
cin>>s;
s=s.substr(0,s.size()-1);//自动去掉
int t=per[s];
cin>>s;
int u=per[s];
if(u<=n)//表示人名
{
cin>>s;
if((u&&s!="is")||(!u&&s!="am"))
{
gets(asdfghjkl);
continue;
}
if(!u)
u=t;
cin>>s;
if(s=="not")
{
cin>>s;
if(s=="guilty.")
v[t].push_back(sta(u,0,0));
}
else if(s=="guilty.")
v[t].push_back(sta(u,0,1));
}
else if(u==n+1)//表示日期
{
cin>>s;
if(s!="is")
continue;
cin>>s;
if(day[s])
v[t].push_back(sta(day[s],1,1));
}
else
gets(asdfghjkl);
}
string ans="";
//枚举谁是罪犯
for(int i=1;i<=n;++i)
{
//枚举今天星期几
for(int j=1;j<=7;++j)
{
int flag=0,cnt=n,ran=0;//ran表示波动范围
for(int k=1;!flag&&k<=n;++k)
{
vector<sta>::iterator it=v[k].begin();
if(!v[k].size())
{
++ran;
continue;
}
sta tmp=*it;
bool rea;
if(tmp.to)
rea=(tmp.u==j);
else
rea=((tmp.u==i)^(!tmp.is));
++it;
for(;!flag&&it!=v[k].end();++it)
{
if(it->to)
{
if(rea!=(it->u==j))
flag=1;
}
else
{
if(rea==((it->u==i)^it->is))
flag=1;
}
}
cnt-=rea;
}
if(!flag&&cnt>=m&&cnt-ran<=m)
{
if(ans=="")
ans=nm[i];
else if(ans!=nm[i])
{
cout<<"Cannot Determine"<<endl;
return 0;
}
}
}
}
if(ans=="")
cout<<"Impossible"<<endl;
else
cout<<ans<<endl;
return 0;
}
说点什么