双层枚举嫌疑犯与当日是星期几,统计真话与假话是否满足题意
注意 fake<=N&&fake+neutral>=N 即假话数量不大于N,假话加上没用的废话数量不小于N
(注意OJ上的数据存在问题:冒号后跟一个空格,CHARLES的话最后的句号‘.’应为半角,非全角)
可用样例输入:
MIKE
CHARLES
KATE
MIKE: I am guilty.
MIKE: Today is Sunday.
CHARLES: MIKE is guilty.
KATE: I am guilty.
KATE: How are you??
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> Par;
typedef pair<int,Par> Pr;
int M,N,P,ans,f[];
char s1[],s2[],s3[];
string dayStr[]={
"Monday"
,"Tuesday"
,"Wednesday"
,"Thursday"
,"Friday"
,"Saturday"
,"Sunday"
};
vector<string> name;
map<string,int> mp;
Pr prd[];
inline int readDigit(){
int x=;char c=getchar();
while(!isdigit(c))c=getchar();
for(;isdigit(c);c=getchar())x=x*+c-'';
return x;
}
inline void readName(){
char c;int i=;
while((c=getchar())!='\n')s1[i++]=c;
s1[i]='\0';
}
inline void readSubj(){
char c;int i=;
while((c=getchar())!=' ')s2[i++]=c;
s2[i-]='\0';
}
inline void readWords(){
char c;int i=;
while((c=getchar())!='\n')s3[i++]=c;
s3[i]='\0';
}
int main(){
int i,j,day,gty,fake,neutral,subid;
string sd;
bool jd,prim;
M=readDigit();
N=readDigit();
P=readDigit();
for(i=;i<M;i++){
readName();
name.push_back(s1);
mp[s1]=i;
}
for(i=;i<P;i++){
readSubj();
readWords();
sd=s3;
subid=mp[s2];
if(sd=="I am guilty.")
prd[i]=Pr(,Par(subid,subid));
else if(sd=="I am not guilty.")
prd[i]=Pr(,Par(subid,subid));
else{
jd=false;
for(j=;!jd&&j<;j++)
if(sd=="Today is "+dayStr[j]+"."){
prd[i]=Pr(,Par(subid,j));
jd=true;
break;
}
for(j=;!jd&&j<M;j++){
if(sd==name[j]+" is guilty."){
prd[i]=Pr(,Par(subid,j));
jd=true;
break;
}
else if(sd==name[j]+" is not guilty."){
prd[i]=Pr(,Par(subid,j));
jd=true;
break;
}
}
if(!jd)
prd[i]=Pr(,Par(,));
}
}
for(jd=false,day=;day<;day++){
for(gty=;gty<M;gty++){
memset(f,,sizeof f);
prim=true;
for(i=;i<P;i++){
if(prd[i].first==){
if(prd[i].second.second==gty){
if(!f[prd[i].second.first])
f[prd[i].second.first]=;
else if(f[prd[i].second.first]==){
prim=false;
break;
}
}
else{
if(!f[prd[i].second.first])
f[prd[i].second.first]=;
else if(f[prd[i].second.first]==){
prim=false;
break;
}
}
}
else if(prd[i].first==){
if(prd[i].second.second!=gty){
if(!f[prd[i].second.first])
f[prd[i].second.first]=;
else if(f[prd[i].second.first]==){
prim=false;
break;
}
}
else{
if(!f[prd[i].second.first])
f[prd[i].second.first]=;
else if(f[prd[i].second.first]==){
prim=false;
break;
}
}
}
else if(prd[i].first==){
if(prd[i].second.second==day){
if(!f[prd[i].second.first])
f[prd[i].second.first]=;
else if(f[prd[i].second.first]==){
prim=false;
break;
}
}
else{
if(!f[prd[i].second.first])
f[prd[i].second.first]=;
else if(f[prd[i].second.first]==){
prim=false;
break;
}
}
}
}
if(!prim)
continue;
neutral=fake=;
for(i=;i<M;i++)
if(f[i]==)
neutral++;
else if(f[i]==)
fake++;
if(fake<=N&&fake+neutral>=N){
if(!jd){
jd=true;
ans=gty;
}
else if(jd&&ans!=gty){
puts("Cannot Determine");
return ;
}
}
}
}
if(jd)
puts(name[ans].data());
else
puts("Impossible"); return ;
}