LUOGU P1039 侦探推理 (字符串+模拟)

传送门

解题思路

　　一道%你神题，\(string\)好强大啊。。首先枚举一个周几，再枚举一个罪犯是谁，然后判断的时候就是枚举所有人说的话。定义\(fAKe[i]\)表示第\(i\)个人说的是真话还是假话还是未知。然后如果遇到\(xx is guilty\)或\(I am guilty\)之类的话，就看枚举的罪犯是否为这个人。如果说的是\(Today is xxx\)，就看当前枚举的星期是否为这一天。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<string>

#include<map>

using namespace std;

const int MAXN = 25;

int n,m,p,fAKe[MAXN],w[205],ans,now,err;

string name[MAXN],say[205];

string day[10]={"","Today is Sunday.","Today is Monday.","Today is Tuesday.","Today is Wednesday."

                ,"Today is Thursday.","Today is Friday.","Today is Saturday."};

map<string,int> mp;

void solve(int x,int y){

    if(!fAKe[x]) fAKe[x]=y;

    else if(fAKe[x] && fAKe[x]!=y) err=1;

}

int main(){

    scanf("%d%d%d",&m,&n,&p);

    for(int i=1;i<=m;i++) cin>>name[i],mp[name[i]]=i;

    for(int i=1;i<=p;i++){

        string nm;cin>>nm;

        nm.erase(nm.end()-1);w[i]=mp[nm];

        getline(cin,say[i]);say[i].erase(say[i].begin());

		say[i].erase(say[i].end()-1);

    }

    for(int td=1;td<=7;td++)

        for(int chp=1;chp<=m;chp++){ //枚举罪犯

            err=0;int who,cnt,pp;

            memset(fAKe,0,sizeof(fAKe));

            for(int i=1;i<=p;i++){

                who=w[i];

                if(say[i]=="I am guilty.") solve(who,who==chp?1:-1);

                if(say[i]=="I am not guilty.") solve(who,who==chp?-1:1);

                for(int j=1;j<=7;j++)

                    if(say[i]==day[j]) {solve(who,j==td?1:-1);break;}

                for(int j=1;j<=m;j++){

                    if(say[i]==name[j]+" is guilty.") solve(who,chp==j?1:-1);

                    if(say[i]==name[j]+" is not guilty.") solve(who,chp==j?-1:1);

                }

            }

            cnt=pp=0;

            for(int i=1;i<=m;i++) {

                if(!fAKe[i]) pp++;

                if(fAKe[i]==-1) cnt++;

            }

            if(err || cnt>n || cnt+pp<n) continue;

            if(ans && ans!=chp) {

                puts("Cannot Determine");

                return 0;

            }

            ans=chp;

        }

    if(ans) cout<<name[ans];

    else puts("Impossible");

    return 0;

}