题解：P1039 [NOIP 2003 提高组] 侦探推理

Lan_yan · 2025-04-26 15:03:51 · 题解

很像小学学某思的奥数题。

但是我们的计算机可没有所谓机灵的脑袋，那就枚举所有情景。

模拟每个人是罪犯和今天的日期，模拟每一句话，发现始终说谎的人数。

如果有人真假话都说或者大于 N 个直接跳过该情景。

如果发现和前面情景推定的凶手不同或者有多个凶手可能性即输出 Cannot Determine。

如果所有情景都没有凶手即输出 Impossible。

否则即输出名字。

这边输入与判断建议用 string，容易发现 string 比较好比较，插入也很方便。

假设该字符串为 y，删除最后一个字符用 y.erase(y.length()-1,1);。

Code

#include<bits/stdc++.h>
using namespace std;
int num[25],rub[105];
int n,m,p,wer=0,tf[21];
string name[21];
string bish[105],ans[21];
void dat(int x,int y)
{
    int i,j,t=0,f=0;
    for(i=0;i<p;i++)
    {
        int flag;
        if(bish[i]=="Today is Monday.")
        {
            if(y==1)flag=1;
            else flag=0;
            if(tf[rub[i]]==-1)tf[rub[i]]=flag;
            if(tf[rub[i]]!=flag)return;
        }
        if(bish[i]=="Today is Tuesday.")
        {
            if(y==2)flag=1;
            else flag=0;
            if(tf[rub[i]]==-1)tf[rub[i]]=flag;
            if(tf[rub[i]]!=flag)return;
        }
        if(bish[i]=="Today is Wednesday.")
        {
            if(y==3)flag=1;
            else flag=0;
            if(tf[rub[i]]==-1)tf[rub[i]]=flag;
            if(tf[rub[i]]!=flag)return;
        }
        if(bish[i]=="Today is Thursday.")
        {
            if(y==4)flag=1;
            else flag=0;
            if(tf[rub[i]]==-1)tf[rub[i]]=flag;
            if(tf[rub[i]]!=flag)return;
        }
        if(bish[i]=="Today is Friday.")
        {
            if(y==5)flag=1;
            else flag=0;
            if(tf[rub[i]]==-1)tf[rub[i]]=flag;
            if(tf[rub[i]]!=flag)return;
        }
        if(bish[i]=="Today is Saturday.")
        {
            if(y==6)flag=1;
            else flag=0;
            if(tf[rub[i]]==-1)tf[rub[i]]=flag;
            if(tf[rub[i]]!=flag)return;
        }
        if(bish[i]=="Today is Sunday.")
        {
            if(y==7)flag=1;
            else flag=0;
            if(tf[rub[i]]==-1)tf[rub[i]]=flag;
            if(tf[rub[i]]!=flag)return;
        }
        if(bish[i]=="I am guilty.")
        {
            if(rub[i]==x)flag=1;
            else flag=0;
            if(tf[rub[i]]==-1)tf[rub[i]]=flag;
            if(tf[rub[i]]!=flag)return;
        }
        if(bish[i]=="I am not guilty.")
        {
            if(rub[i]!=x)flag=1;
            else flag=0;
            if(tf[rub[i]]==-1)tf[rub[i]]=flag;
            if(tf[rub[i]]!=flag)return;
        }
        for(j=0;j<m;j++)
        {
            string d=name[j]+" is guilty.";
            if(d==bish[i])
            {
                if(j==x)flag=1;
                else flag=0;
                if(tf[rub[i]]==-1)tf[rub[i]]=flag;
                if(tf[rub[i]]!=flag)return;
            }
        }
        for(j=0;j<m;j++)
        {
            string d=name[j]+" is not guilty.";
            if(d==bish[i])
            {
                if(j!=x)flag=1;
                else flag=0;
                if(tf[rub[i]]==-1)tf[rub[i]]=flag;
                if(tf[rub[i]]!=flag)return;
            }
        }
    }
    for(i=0;i<m;i++)
    {
        if(tf[i]==1)t++;
        if(tf[i]==0)f++;
    }
    if(f>n||t>m-n)return;
    ans[wer++]=name[x];
}
int main()
{
    int i,j;
    scanf("%d%d%d",&m,&n,&p);
    for(i=0;i<m;i++)
        cin>>name[i];
    for(i=0;i<p;i++)
    {
        string x,y;
        cin>>x;
        x.erase(x.length()-1,1);
        for(j=0;j<m;j++)
            if(name[j]==x)rub[i]=j;
        getline(cin,y);
        y.erase(0,1);
        if(y[y.length()-1]=='\n'||y[y.length()-1]=='\r')
            y.erase(y.length()-1,1);
        bish[i]=y;
    }
    for(i=0;i<m;i++)
    {
        for(j=1;j<=7;j++)
        {
            memset(tf,-1,sizeof(tf));
            dat(i,j);
        }
    }
    if(wer<1)
    {
        printf("Impossible");
        return 0;
    }
    string lan=ans[0];
    for(i=1;i<wer;i++)
    {
        if(ans[i]!=lan)
        {
            printf("Cannot Determine");
            return 0;
        }
    }
    cout<<lan;
    return 0;
}

如果你想要珍惜自己的生命这边建议直接跳过该题。