P1106侦探推理
描述
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：
证词中出现的其他话，都不列入逻辑推理的内容。
明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。
现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！
格式
输入格式
输入由若干行组成，第一行有二个整数，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）；M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证言的总数。接下来M行，每行是明明的一个同学的名字（英文字母组成，没有主格，全部大写）。往后有P行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过250个字符。
输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。
输出格式
如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出 Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出 Impossible。
样例1
限制
每个测试点1s
提示
有说一句话的末尾无空格的么？..
来源
NOIP2003第二题
解析：直接枚举凶手是谁，今天星期几，然后判断是否合法即可。根据合法的情况数，得到答案。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define max_m 20
#define max_p 100
#define max_len 250
using namespace std;
int m,n;
char name[max_m+20][max_len+20];
struct tnode{int x,xq;
bool y[max_m+20];
}person[max_m+20];
char zy[5][30]={"I am guilty.","I am not guilty.","is guilty.","is not guilty.","Today is "};
char day[8][20]={"-_-||","Monday.","Tuesday.","Wednesday.","Thursday.","Friday.","Saturday.","Sunday."};
int lz[5]={12,16,10,14,9};
int ld[8]={0,7,8,10,9,7,9,7};
int ln[max_m+20];
bool used[max_m+20],f[max_m+20];
bool jia[max_m+20];
void readdata()
{
int i,j,k,p,len,l,r;
char s[max_len+20];
scanf("%d%d%d\n",&m,&n,&p);
for(i=1;i<=m;i++)gets(name[i]),ln[i]=strlen(name[i]);
for(i=1;i<=m;i++)person[i].x=person[i].xq=0;
for(i=1;i<=p;i++)
{
gets(s),len=strlen(s);
for(r=0;r<len && s[r]!=':';r++);
for(j=1;j<=m;j++)
if(strncmp(name[j],s,r)==0)break;
if(j>m || used[j])continue;
l=r+2,r=l;
//check 0
if(strncmp(zy[0],s+l,lz[0])==0)
{
if(person[j].y[j] && (person[j].x!=0 && person[j].x!=j))used[j]=1;
person[j].x=j;
f[j]=1;
continue;
}
//check 1
if(strncmp(zy[1],s+l,lz[1])==0)
{
if(person[j].x==j)used[j]=1;
person[j].y[j]=1;
f[j]=1;
continue;
}
//注意有人叫 Today 的情况
//check 4
if(strncmp(zy[4],s+l,lz[4])==0)
{
for(l+=lz[4],k=1;k<=7;k++)
if(strncmp(s+l,day[k],ld[k])==0)break;
if(k<=7)
{
if(person[j].xq!=0 && person[j].xq!=k)used[j]=1;
person[j].xq=k;
f[j]=1;
continue;
}
}
for(;r<len && s[r]!=' ';r++);
for(k=1;k<=m;k++)
if(ln[k]==r-l && strncmp(name[k],s+l,r-l)==0)break;
if(k>m)continue;
l=r+1;
//check 2
if(strncmp(s+l,zy[2],lz[2])==0)
{
if(person[j].y[k] || (person[j].x!=0 && person[j].x!=k))used[j]=1;
person[j].x=k;
f[j]=1;
continue;
}
//check 3
if(strncmp(s+l,zy[3],lz[3])==0)
{
if(person[j].x==k)used[j]=1;
person[j].y[k]=1;
f[j]=1;
}
}
}
int get(int xx,int yy)
{
memset(jia,0,sizeof(jia));
int i,j,k,sum=0;
for(i=1;i<=m;i++)if(!used[i] && f[i])
{
if(person[i].x!=0 && person[i].x!=xx)
{
jia[i]=1,sum++;
continue;
}
if(person[i].xq!=0 && person[i].xq!=yy)
{
jia[i]=1,sum++;
continue;
}
if(person[i].y[xx])
jia[i]=1,sum++;
}
for(i=1;i<=m;i++)if(jia[i])
{
if(person[i].x==xx || person[i].xq==yy)return 30;
for(j=1;j<=m;j++)if(j!=xx && person[i].y[j])return 30;
}
return sum;
}
void work()
{
int i,j,k,s1,s2,ans=0;
for(s1=0,i=1;i<=m;i++)if(!f[i])s1++;
for(i=1;i<=m;i++)if(!used[i])
for(j=1;j<=7;j++)
{
s2=get(i,j);
if(s2<=n && n<=s2+s1)
{
if(ans!=0)
{
printf("Cannot Determine\n");
return;
}
ans=i;
break;
}
}
if(ans==0)printf("Impossible\n");
else printf("%s\n",name[ans]);
}
int main()
{
readdata();
work();
return 0;
}