洛谷 P1039 NOIp2003提高组 侦探推理 题解【模拟】【字符串】【枚举】

作者: wjyyy 分类: 字符串,枚举,解题报告 发布时间: 2018-10-31 19:27

点击量:42

 

    细节比较多的一道题。疯狂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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */