题解 | #[NOIP2003]侦探推理#
题目描述
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：
证词中出现的其他话，都不列入逻辑推理的内容。 明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。 现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！
输入描述：
输入由若干行组成，第一行有二个整数，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）；M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证言的总数。接下来M行，每行是明明的一个同学的名字（英文字母组成，没有主格，全部大写）。 往后有P行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过250个字符。 输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。
输出描述：
如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出 Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出 Impossible。
示例
输入
3 1 5
MIKE
CHARLES
KATE
MIKE: I am guilty.
MIKE: Today is Sunday.
CHARLES: MIKE is guilty.
KATE: I am guilty.
KATE: How are you??
输出
MIKE
思路
让机器思考？开什么玩笑？看到这道题，我的第一反应是依稀记得学过的离散数学中的逻辑题，怎么做来着？通过各种推理符号的化简，好像还有个真值表可以完成，真值表好像更适合计算机吧~~ 总之，先进行字符串处理吧。。。
处理完一看，接下来咋整，真搞个矩阵吗，看看别人咋做吧。。原来是模拟，好有道理，就模拟普通人遇到这样的题目下意识怎么思考就完了。开整！
对输入进行预处理
首先，把所有人说的话收集起来，用结构体表示一位同学及他的发言，通过链表组织他所说的每句话，将每句话拆开成单词存入字符串数组，以便后续处理。
typedef struct Node
{
char word[NUM][LEN];
struct Node*next;
}Node,*List;
struct Cell
{
char name[LEN];
List testmony;
};
struct Cell stu[m];
for(int i=0;i<m;++i)scanf("%s",stu[i].name),stu[i].testmony=NULL;
for(char temp[LEN];scanf("%s",&temp)!=EOF;)
{
//查找当前发言的人处于结构体数组的位置
int i;
for(i=0;i<m;++i)
{
int j;
for(j=0;stu[i].name[j]==temp[j];++j);
if(temp[j]==':'&&!stu[i].name[j])break;
}
//维护链表
List now=stu[i].testmony;
if(!now)stu[i].testmony=now=malloc(sizeof(Node));
else
{
List pre;
while(now)pre=now,now=now->next;
pre->next=now=malloc(sizeof(Node));
}
now->next=NULL;
/*将证言以空格为分隔进行拆分
由于scanf(%s)读到换行符时会结束读取，不读入换行符，而是在缓冲区留下换行符
在下次调用scanf(%s)时会跳过空白字符，从第一个非空白字符开始读入，因此需要getchar()判断*/
int k,c;
for(k=0;(c=getchar())!='\n';++k)
{
ungetc(c,stdin);
scanf("%s",temp);
for(int t=0;now->word[k][t]=temp[t];++t);
}
now->word[k][0]=0;
}
模拟推理过程
题目条件是：有N个人始终说假话，其余的人始终说真，证词中出现的其他话，都不列入逻辑推理的内容；程序判断的可能结果有：能确定谁是罪犯、不止一个人可能是罪犯、没有人可能成为罪犯。
一般的推理过程是，先假设某个人是凶手，今天是周几，然后一遍一遍地判断，试图找出不符条件或者矛盾的，最糟糕的情况当然是要把情况都假设个遍才能得出结论。
我们普通人正常的推理都是图方便的，因此先判特例：
事实依据：
- 如果这位同学说话自相矛盾，那他肯定说谎了；他的那些证词取反就是事实，记录下来，可以作为我们进一步判断的依据。
- 如果同学的证词与我们已知的事实冲突，那他肯定说谎了，同样的，将他的证词都取反，作为事实记录。
判断假设真伪：
3. 如果我们的假设与已知的事实冲突，说明假设不成立，本轮判断无效。
4. 如果我们的假设与同学的证词产生矛盾（即部分证词为真，部分为假），说明假设不成立，本轮判断无效。
默认情况：
5. 如果我们的假设和同学的证词观点一致、相反、不相干，则猜测同学说真话、说谎、混沌。
在正常进行的一轮判断结尾，统计多少人说真话，多少说谎。如果还能符合题设条件，就认定该轮为一种可能情况，记下凶手。如果存在多种可能情况，输出“Cannot Determine”；
题目的限制条件也带来了一些便利之处，比如因为一个人不能即说真话又说假话，那么他就不会出现即认定一个人是凶手又认定同一个人不是凶手的情况，限制了输入情况。另外，在某位同学的证言自相矛盾（发生了情况1）的前提下，如果验证了假设与事实不冲突（情况3），就不可能再出现假设与证词产生矛盾（情况4）。
实现如下：
#include<stdio.h>
typedef struct Node//存储证词和指向下一句证词的指针
{
char word[6][11];
struct Node*next;
}Node,*List;
struct Cell//存储同学名字和证词链表
{
char name[201];
List testmony;
};
int main()
{
int m,n,p;
scanf("%d%d%d",&m,&n,&p);
struct Cell stu[m];
for(int i=0;i<m;++i)scanf("%s",stu[i].name),stu[i].testmony=NULL;//初始化，读入同学们的名字
for(char temp[201];scanf("%s",&temp)!=EOF;)//读入同学们的证词
{
int i;
for(i=0;i<m;++i)
{
int j;
for(j=0;stu[i].name[j]==temp[j];++j);//找到该名同学位于结构体数组的位置
if(temp[j]==':'&&!stu[i].name[j])break;
}
List now=stu[i].testmony;//初始化链表
if(!now)stu[i].testmony=now=malloc(sizeof(Node));
else
{
List pre;
while(now)pre=now,now=now->next;
pre->next=now=malloc(sizeof(Node));
}
now->next=NULL;
int k,c;
for(k=0;(c=getchar())!='\n';++k)//读入证词
{
ungetc(c,stdin);
scanf("%s",temp);
for(int t=0;now->word[k][t]=temp[t];++t);
}
now->word[k][0]=0;
}
char week[7]={}/*事实，星期情况*/,guilty[m],cont[m],today[m][7],taget[m][m];
memset(guilty,0,m);//目前了解的事实，与结构体数组次序一致，凶手情况：0--未知，1--确认，-1--否认
memset(cont,0,m);//证词是否矛盾情况：0--未知，1--确认
memset(today,0,m*7);//证词描述，星期情况：0--未知，1--确认
memset(taget,0,m*m);//证词描述，凶手情况：0--未知，1--确认，-1--否认
int result=-1;
List now;
for(int i=0;i<m;++i)
{
for(now=stu[i].testmony;now;now=now->next)
{
if(!strcmp(now->word[0],"I")&&!strcmp(now->word[1],"am"))
strcpy(now->word[0],stu[i].name),strcpy(now->word[1],"is");
if(!strcmp(now->word[0],"Today")&&!strcmp(now->word[1],"is"))
{
if(!strcmp(now->word[2],"Sunday."))
{
if(!cont[i])//如果本同学之前的证词说过今天不是星期天或者今天是星期1~6，则认为该同学说话自相矛盾
{
int j;
for(j=0;j<7&&!today[i][j];++j);
if(j!=7&&j!=0)cont[i]=1;
}
today[i][0]=1;
}
else if(!strcmp(now->word[2],"Monday."))
{
if(!cont[i])//重复逻辑
{
int j;
for(j=0;j<7&&!today[i][j];++j);
if(j!=7&&j!=1)cont[i]=1;
}
today[i][1]=1;
}
else if(!strcmp(now->word[2],"Tuesday."))
{
if(!cont[i])
{
int j;
for(j=0;j<7&&!today[i][j];++j);
if(j!=7&&j!=2)cont[i]=1;
}
today[i][2]=1;
}
else if(!strcmp(now->word[2],"Wednesday."))
{
if(!cont[i])
{
int j;
for(j=0;j<7&&!today[i][j];++j);
if(j!=7&&j!=3)cont[i]=1;
}
today[i][3]=1;
}
else if(!strcmp(now->word[2],"Thursday."))
{
if(!cont[i])
{
int j;
for(j=0;j<7&&!today[i][j];++j);
if(j!=7&&j!=4)cont[i]=1;
}
today[i][4]=1;
}
else if(!strcmp(now->word[2],"Friday."))
{
if(!cont[i])
{
int j;
for(j=0;j<7&&!today[i][j];++j);
if(j!=7&&j!=5)cont[i]=1;
}
today[i][5]=1;
}
else if(!strcmp(now->word[2],"Saturday."))
{
if(!cont[i])
{
int j;
for(j=0;j<7&&!today[i][j];++j);
if(j!=7&&j!=6)cont[i]=1;
}
today[i][6]=1;
}
else continue;
}
else if(!strcmp(now->word[1],"is")&&(!strcmp(now->word[2],"not")&&!strcmp(now->word[3],"guilty.")||!strcmp(now->word[2],"guilty.")))
{
int j;
for(j=0;strcmp(stu[j].name,now->word[0]);++j);
if(!strcmp(now->word[2],"not"))taget[i][j]=-1;
else
{
if(!cont[i])//如果本同学说过其他人是凶手，则认为该同学说话自相矛盾
{
int k;
for(k=0;k<m&&taget[i][k]!=1;++k);
if(k!=m&&k!=j)cont[i]=1;
}
taget[i][j]=1;
}
}
else continue;
}
//判断同学的证词是否与已知事实矛盾
for(int j=0,k=-1,l=-1;j<7&&!cont[i];++j)
{
if(week[j]&&today[i][j]&&week[j]!=today[i][j]||week[k]==1&&today[i][j]==1||week[j]==1&&today[i][l]==1)cont[i]=1;
if(week[j]==1)k=j;
if(today[i][j]==1)l=j;
}
for(int j=0,k=-1,l=-1;j<m&&!cont[i];++j)
{
if(guilty[j]&&taget[i][j]&&guilty[j]!=taget[i][j]||guilty[k]==1&&taget[i][j]==1||guilty[j]==1&&taget[i][l]==1)cont[i]=1;
if(guilty[j]==1)k=j;
if(taget[i][j]==1)l=j;
}
if(cont[i])//如果同学的证词自相矛盾或与事实矛盾，将之取反，即可作为事实
{
for(int j=0;j<7;++j)if(today[i][j])week[j]=-today[i][j];
for(int j=0;j<m;++j)if(taget[i][j])if((guilty[j]=-taget[i][j])==1)return printf("%s",stu[j].name),0;//如果能确认凶手，那一定是唯一的
}
}
for(int day=0;day<7;++day)
for(int guess=0;guess<m;++guess)
{
int j;//若本轮假设与事实冲突，跳过本轮
for(j=0;j<7&&!(week[j]==-1&&day==j||week[j]==1&&day!=j);++j);
if(j!=7)continue;
for(j=0;j<m&&!(guilty[j]==-1&&guess==j||guilty[j]==1&&guess!=j);++j);
if(j!=m)continue;
int lie=0,truth=0;
for(int i=0;i<m;++i)
{
if(cont[i]){++lie;continue;}//若同学证词矛盾，一定说谎
int T=0;
for(int j=0;j<7;++j)//若同学证词与假设矛盾，则跳过本轮
{
if(today[i][j]==1&&day==j)if(T==-1)goto fail;else T=1;
else if(today[i][j]==-1&&day==j||today[i][j]==1&&day!=j)if(T==1)goto fail;else T=-1;
}
for(int j=0;j<m;++j)
{
if(taget[i][j]==1&&guess==j||taget[i][j]==-1&&guess!=j)if(T==-1)goto fail;else T=1;
else if(taget[i][j]==-1&&guess==j||taget[i][j]==1&&guess!=j)if(T==1)goto fail;else T=-1;
}
if(T==-1)++lie;else if(T==1)++truth;
}
if(lie<=n&&truth<=m-n)//若正常进行且符合条件，则保存本次猜测
if(result==-1)result=guess;else if(result!=guess)return printf("Cannot Determine"),0;
fail:;
}
result==-1?printf("Impossible"):printf("%s",stu[result].name);//若猜想有且唯一，则输出凶手
return 0;
}
投递小红书等公司10个岗位 >
国家电网工作强度 101人发布