社区讨论

本地过洛谷wa80,求帮忙

P1039[NOIP 2003 提高组] 侦探推理参与者 6已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mi6tid6n
此快照首次捕获于
2025/11/20 10:34
4 个月前
此快照最后确认于
2025/11/20 10:34
4 个月前
查看原帖
CPP
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int m,n,p,ans=-1,killer,day,op[30],is[30],nw[30];char c;// op 0 ?  1  true  2  not true     is 0 ? 1 true 2 not true
string tp[30];
vector<int>pdp[30],pdnp[30],pdd[30];
map<string,int>name;
bool pp(string a,string b)
{
    for(int i=0;i<min(a.length(),b.length());i++)
        if(a[i]!=b[i])return 0;
    return 1;
}
void get(string s)
{
    string a,b,c;int who;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]==':')
        {
            a=s.substr(0,i);
            b=s.substr(i+2,s.length()-i-1);
            break;
        }
    }
    who=name[a];
    if(pp(b,"I am guilty.")){if(is[who]==-1){puts("Impossible");exit(0);}is[who]=1;return;}
    if(pp(b,"I am not guilty.")){if(is[who]==1){puts("Impossible");exit(0);}is[who]=-1;return;}
    for(int i=0;i<b.length();i++)
    {
        if(b[i]==' ')
        {
            a=b.substr(0,i);
            b=b.substr(i+1,s.length()-i);
            break;
        }
    }
    if(name[a]&&pp(b,"is guilty.")){pdp[who].push_back(name[a]);return;}
    if(name[a]&&pp(b,"is not guilty.")){pdnp[who].push_back(name[a]);return;}
    for(int i=0;i<b.length();i++)
    {
        if(b[i]==' ')
        {
            c=b.substr(0,i);
            b=b.substr(i+1,s.length()-i);
            break;
        }
    }
    if(pp(a,"Today")&&pp(c,"is"))
    {
        if(pp(b,"Monday.")){pdd[who].push_back(1);return;}
        if(pp(b,"Tuesday.")){pdd[who].push_back(2);return;}
        if(pp(b,"Wednesday.")){pdd[who].push_back(3);return;}
        if(pp(b,"Thursday.")){pdd[who].push_back(4);return;}
        if(pp(b,"Friday.")){pdd[who].push_back(5);return;}
        if(pp(b,"Saturday.")){pdd[who].push_back(6);return;}
        if(pp(b,"Sunday.")){pdd[who].push_back(7);return;}
    }
    return;
}
bool check()
{
    memset(nw,0,sizeof nw);
    for(int i=1;i<=m;i++)
    {
        if(is[i]!=0)
        {
            if(i==killer)
            {
                if(is[i]==1)nw[i]=1;
                else if(is[i]==-1)nw[i]=-1;
            }
            else
            {
                if(is[i]==1)nw[i]=-1;
                else if(is[i]==-1)nw[i]=1;
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<pdd[i].size();j++)
        {
            if(pdd[i][j]==day)
            {
                if(nw[i]==-1)return 0;
                else nw[i]=1;
            }
            else
            {
                if(nw[i]==1)return 0;
                else nw[i]=-1;
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<pdp[i].size();j++)
        {
            if(pdp[i][j]==killer)
            {
                if(nw[i]==-1)return 0;
                else nw[i]=1;
            }
            else
            {
                if(nw[i]==1)return 0;
                else nw[i]=-1;
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<pdnp[i].size();j++)
        {
            if(pdnp[i][j]==killer)
            {
                if(nw[i]==1)return 0;
                else nw[i]=-1;
            }
            else
            {
                if(nw[i]==-1)return 0;
                else nw[i]=1;
            }
        }
    }
    int cnt1=0,cnt2=0;
    for(int i=1;i<=m;i++)
    {
        if(nw[i]==-1)cnt1++;
        else if(nw[i]==0)cnt2++;
    }
    if(cnt1<=n&&cnt1+cnt2>=n)return 1;
    return 0;
}
int main()
{
    cin>>m>>n>>p;
    for(int i=1;i<=m;i++)
        cin>>tp[i],name[tp[i]]=i;	
    for(int i=1;i<=p;i++)
    {
        string s="";
        while((c=getchar())!=EOF)
        {
            if(c!='\n')s+=c; 	
            if(c=='\n'&&s.length()>=3)break;
        }
        if(s.length()>=10)get(s);
    }
    for(int i=1;i<=m;i++)
    {
        killer=i;
        for(int j=1;j<=7;j++)
        {
            day=j;
            if(check()&&ans==-1||ans==killer)ans=killer;
            else if(check()&&ans!=-1&&ans!=killer){puts("Cannot Determine");return 0;}
        }
    }
    if(ans==-1)puts("Impossible");
    else cout<<tp[ans];	
}

回复

7 条回复,欢迎继续交流。

正在加载回复...