暂时未完成qwq
[NOIP2003 提高组] 侦探推理
（这道题思路很简单，但是细节一大堆qwq，调吐了QAQ
这个题一共就20个人，星期一共就有7种可能，100句证词，所以可以直接暴力枚举，看一看假设第 $i$ 个人是罪犯（guilty），今天是星期 $j$ ,那么一共有几个人说了谎话。
然后就好了awa…………
了吗……
这道题的难点其实一直都不是思路，因为思路十分的简单,这道题最恶心的地方是它的细节QAQ
下面我来分别说一下它的啸细节：
part1：输入部分：
首先是输入，这是整道题最恶心的地方，一不小心就会出一些及其难调的BUG。
虽然说白了就是依托答辩分讨
输入一行，然后还要让程序弄明白输入的意思，就是要判断它到底是哪一种证词（一共5种）。然后因为它是字符串，所以总是会爆一些奇奇怪怪的错误qwq
然后我这里处理的方式是分为5种分别判断（虽然说白了就3种：说某个人是，某个人不是，今天是星期几），判断的方法就是让除了 $ “XXX”$ 以外的就直接字符匹配。
数组定义：
bool kk[25];//这个一会说是怎么回事qwq，这是另外一个坑
int n,m,p,num,bh,nnn,sl;//基本变量
string s,ls_name,ls_p,day;
//用于字符匹配
string duib[13]={"","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday",
"I am guilty.",
"I am not guilty.",
"is guilty.",
"is not guilty.",
"Today is "};
//用于映射
map<string,int>name;
map<int,string>name_out;
map<string,int>dd;
map<int,bool>zy;
//who：谁说的
//bh：1/2/3 说某个人是罪犯/说某个人不是罪犯/说今天是星期几
struct node{
int who,bh,name,today;
}q[105];
main函数内：
cin>>n>>m>>p;
for(int i=1;i<=n;i++) cin>>s,name[s]=i,name_out[i]=s;//输入名字，然后把名字映射成编号
for(int i=1;i<=7;i++) dd[duib[i]]=i;//把日期映射成编号
for(int i=1;i<=p;i++)
{
s=read();
get_name(s);
get_p(s);
nnn++,q[nnn].who=name[ls_name],q[nnn].bh=0;
if(pd(1,ls_p)) q[nnn].bh=1,q[nnn].name=name[ls_name];
else if(pd(2,ls_p)) q[nnn].bh=2,q[nnn].name=name[ls_name];
else if(pd(3,ls_p)) q[nnn].bh=1,q[nnn].name=name[ls_name];
else if(pd(4,ls_p)) q[nnn].bh=2,q[nnn].name=name[ls_name];
else if(pd(5,ls_p)) q[nnn].bh=3,q[nnn].today=dd[day];
if(!q[nnn].bh) nnn--;
else kk[q[nnn].who]=1;
}
……
…………
…………
……………………
……
………………
啊吧啊吧啊吧啊吧……
最后,完整代码：
#include<bits/stdc++.h>
using namespace std;
string read()
{
string s="";
char g=getchar();
while(!((g>='a'&&g<='z')||(g>='A'&&g<='Z'))) g=getchar();
while((g>='a'&&g<='z')||(g>='A'&&g<='Z')||(g==' ')||(g==':')||(g=='.'))
{
s+=g;
g=getchar();
}
return s;
}
bool kk[25];
int n,m,p,num,bh,nnn,sl;
string s,ls_name,ls_p,day;
string duib[13]={"","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday",
"I am guilty.",//8
"I am not guilty.",//9
"is guilty.",//10
"is not guilty.",//11
"Today is "};//12
map<string,int>name;
map<string,int>dd;
map<int,string>name_out;
map<int,bool>zy;
struct node{
int who,bh,name,today;
}q[105];
bool pd(int lx,string s)
{
if(lx==1||lx==2) return ((bool)(s==duib[lx+7]));
else if(lx==3||lx==4)
{
int i=0; ls_name="";
while(s[i]!=' '&&i<s.length()) ls_name+=s[i],i++;
if((!name.count(ls_name))||
duib[lx+7].length()+ls_name.length()+1!=s.length())
return 0;
bool kk=1;
for(i=0;i<duib[lx+7].length()&&i+ls_name.length()+1<s.length();i++)
kk&=((bool)(s[i+ls_name.length()+1]==duib[lx+7][i]));
return kk;
}
else
{
bool kk=1;
for(int i=0;i<duib[12].length();i++)
kk&=((bool)(s[i]==duib[12][i]));
if(!kk) return kk;
day="";
for(int i=duib[12].length();i<s.length()-1;i++) day+=s[i];
return 1;
}
}
void get_name(string s){ls_name="";for(int i=0;i<s.length();i++){if(s[i]==':') break;ls_name+=s[i];}}
void get_p(string s){ls_p="";for(int i=ls_name.length()+2;i<s.length();i++) ls_p+=s[i];}
int main()
{
cin>>n>>m>>p;
for(int i=1;i<=n;i++) cin>>s,name[s]=i,name_out[i]=s;
for(int i=1;i<=7;i++) dd[duib[i]]=i;
for(int i=1;i<=p;i++)
{
s=read();
get_name(s);
get_p(s);
nnn++,q[nnn].who=name[ls_name],q[nnn].bh=0;
if(pd(1,ls_p)) q[nnn].bh=1,q[nnn].name=name[ls_name];
else if(pd(2,ls_p)) q[nnn].bh=2,q[nnn].name=name[ls_name];
else if(pd(3,ls_p)) q[nnn].bh=1,q[nnn].name=name[ls_name];
else if(pd(4,ls_p)) q[nnn].bh=2,q[nnn].name=name[ls_name];
else if(pd(5,ls_p)) q[nnn].bh=3,q[nnn].today=dd[day];
if(!q[nnn].bh) nnn--;
else kk[q[nnn].who]=1;
}
for(int i=1;i<=n;i++)
if(kk[i]==0)
sl++;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=7;j++)
{
zy.clear();
int nn=0,ck=1;
for(int k=1;k<=nnn;k++)
{
if(q[k].bh==1)
{
if(q[k].name==i)
{
if(!zy.count(q[k].who)) zy[q[k].who]=1;
else if(zy.count(q[k].who)&&zy[q[k].who]==0)
{
ck=0;
break;
}
}
else
{
if(!zy.count(q[k].who)) zy[q[k].who]=0,nn++;
else if(zy.count(q[k].who)&&zy[q[k].who]==1)
{
ck=0;
break;
}
}
}
else if(q[k].bh==2)
{
if(q[k].name!=i)
{
if(!zy.count(q[k].who)) zy[q[k].who]=1;
else if(zy.count(q[k].who)&&zy[q[k].who]==0)
{
ck=0;
break;
}
}
else
{
if(!zy.count(q[k].who)) zy[q[k].who]=0,nn++;
else if(zy.count(q[k].who)&&zy[q[k].who]==1)
{
ck=0;
break;
}
}
}
else
{
if(q[k].today==j)
{
if(!zy.count(q[k].who)) zy[q[k].who]=1;
else if(zy.count(q[k].who)&&zy[q[k].who]==0)
{
ck=0;
break;
}
}
else
{
if(!zy.count(q[k].who)) zy[q[k].who]=0,nn++;
else if(zy.count(q[k].who)&&zy[q[k].who]==1)
{
ck=0;
break;
}
}
}
}
if(nn<=m&&nn+sl>=m&&ck)
{
num++;
bh=i;
break;
}
}
}
if(num==1) cout<<name_out[bh]<<'\n';
else if(num==0) cout<<"Impossible\n";
else if(num>1) cout<<"Cannot Determine\n";
return 0;
}