社区讨论
本地过洛谷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 条回复,欢迎继续交流。
正在加载回复...