题解 P1039 【侦探推理】

wjyyy

2019-01-02 18:50:05

Solution

**我的博客:[传送门](https://www.wjyyy.top/2305.html)** ## 题解: 这个题数据范围比较小,考虑枚举,但是枚举谁说真话谁说假话也比较耗时,但是我们发现日期只有一天,罪犯也只有一个,考虑枚举罪犯是谁,和今天是星期几。 在读入每一句话时,把这一句的主人(即冒号前的人)对应到它的编号,这里推荐使用`std::map`,然后判断种类,如果语句不合法就不读这句话,并用`gets()`把这一行读完进入下一句。如果发现第一个单词是人名,则用`std::map`找到它的编号,然后看它是**肯定句**还是**否定句**。对于每一个点开一个`vector`用来存它说过的**合法**的话,区分一下这句话是说人的信息还是日期,如果说人的信息还需要对应到对象,这里最好把`I`转化为自己的名字。 接着就可以枚举罪犯和日期了,因为有的人自始至终都没有说过一句合法的话,这样的人既可能说真话也可能说假话,我们用一个变量$ran$来存有多少个这样的人,剩下的人根据它第一句话来确定它是说真话还是说假话。如果一个人前后矛盾,即前面说真话后面说假话,那么这次枚举就不合法,可以直接跳到下次枚举去。 在一次成功的枚举中,我们得知了有多少人说假话,有多少人不确定,假设说假话的人有$cnt$个,并有$ran$个人不确定,那么当要求说假话的人数在$[cnt,cnt+ran]$范围内就合法。 如果一个罪犯被多次确定,是不会对答案造成额外影响的,但是当确定一个罪犯时发现前面已经确定一个人了,此时就要输出`Cannot Determine`了。当程序结束时还没有找到一个罪犯,则输出`Impossible`。找到罪犯了输出名字即可。 `stl`还是非常方便的,`std::string`用来存名字并进行字符串处理;`std::map`用来映射人名;`std::vector`用来存每个人说的话。不过这个题有一个比较坑的地方,必须要确定一个人说的一句话**每个单词**都合法后,才能把这整句话当作合法的。`&&`一定要注意单词后面的冒号和句号! ## Code: 以前以为码量很大,但是只要注意细节,条理清晰,$\sout{130}$~~行~~是很容易写出来的。 ```cpp #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; } ```