洛谷P1039侦探推理题解

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
string s[1005];
int fake[1005];
string name[1005];
string day[10]={"23333333","Today is Monday.","Today is Tuesday.","Today is Wednesday.","Today is Thursday.","Today is Friday.","Today is Saturday."};
int say[1005];
int err;
int pd(int who,int x)
{
    if(fake[who]&&fake[who]!=x)err=1;
    else fake[who]=x;
}
int main()
{
    int n,m,p;
    scanf("%d%d%d",&m,&n,&p);
    for(int i=1;i<=m;i++)
    {
        cin>>name[i]; 
    }
    for(int i=1;i<=p;i++)
    {
        string nm;
        cin>>nm;
        nm.erase(nm.end()-1);
        for(int j=1;j<=m;j++)
        {
            if(name[j]==nm)say[i]=j;//say[i]=j表示第i句话是j说的 
        }
        getline(cin,s[i]);//把这一行剩下的读进去 
        s[i].erase(s[i].begin());//把开头的空格去掉？ 
        s[i].erase(s[i].end()-1); //这一句话加上评测A，不加样例本地过。。。 
    }
    int tag=0;
    for(int xq=1;xq<=7;xq++)
    {
         
        for(int per=1;per<=m;per++)
        {
            err=0;
        memset(fake,0,sizeof(fake));
            for(int i=1;i<=p;i++)
            {
                if(s[i]=="I am guilty.")
                {
                    if(per==say[i])//如果是这个人说自己 
                    {
                        pd(say[i],1);//是成立的 
                    }
                    else
                    {
                        pd(say[i],-1); //否则不成立 
                    }
                }
                if(s[i]=="I am not guilty.")
                {
                    if(per!=say[i])//同理 
                    {
                        pd(say[i],1);
                    }
                    else
                    {
                        pd(say[i],-1);
                    }
                }
                for(int j=1;j<=7;j++)//再枚举一下星期几 
                {
                    if(s[i]==day[j])//第i句话说是星期j 
                    {
                        if(j==xq)//判断是不是这一天 
                        {
                            pd(say[i],1);
                        }
                        else
                        {
                            pd(say[i],-1);
                        }
                    }
                }
                for(int j=1;j<=m;j++)
                {
                    if(s[i]==name[j]+" is guilty.")//判断这句话是不是j说的 
                    {
                        if(per==j)//再判断是不是当前这个人 
                        {
                            pd(say[i],1);
                        }
                        else
                        {
                            pd(say[i],-1); 
                        }
                    }
                    if(s[i]==name[j]+" is not guilty.")
                    {
                        if(per!=j)//同理 
                        {
                            pd(say[i],1);
                        } 
                        else
                        {
                            pd(say[i],-1);
                        }
                    }
                }
            }
            int cnt1=0,cnt2=0;
            for(int i=1;i<=m;i++)
            {
                if(fake[i]==-1)//当前为说假话 
                {
                    cnt1++; 
                }
                if(fake[i]==0)//这个人无法判断 
                {
                    cnt2++;             
                }
            }
            if(err==0&&cnt1<=n&&cnt1+cnt2>=n)//没有矛盾并且说假话的人比n少并且说假话的人加上不确定的人数>=n(确保不确定的人中有说假话的人加上可以达到n 
            {
                if(tag&&tag!=per)//tag有过（保证不是第一个)并且tag和当前的人不是同一个 
                {
                    printf("Cannot Determine\n");//说明有多个，输出 
                    return 0;
                }
                else
                {
                    tag=per;//tag更新一下 
                }
            }
        }
    }
    if(tag==0)//tag始终没更新，找不到凶手了 
    {
        printf("Impossible\n");
        return 0;
    }
    cout<<name[tag];
    return 0;
}