P1039[NOIP2003提高组]侦探推理
sunxiaofan
·
·
个人记录
前言
做之前感觉挺简单的，亲自上手就感觉bug百出。自己花了半天的时间把代码调好了，后来有看了看jzx大佬的代码，幡然醒悟，于是又重新写了一遍用来理清思路。
题意
### 解题思路
#### 证词处理
由于所有的人名和证词都是字符串的形式，计算机无法直接读懂其含义，所以，我做的第一件事情就是将人名进行编号，以及将证词的含义转换为数字形式，这样可以方便后面的处理操作。
这一部分的代码如下，可以借助注释进行理解。（处理字符串时，使用char数组是个人习惯问题，其实string貌似会更加方便一些）
```cpp
int n,m,p;
char name[25][250];
struct node//存储证词信息。
{
char name[250],words[250];
}a[110];
//写到后面发现这个结构体完全没有用，因为在处理完证词的含义之后，语句原内容都可以丢弃了。
//整个结构体可以化简为两个char数组。我只是单纯懒得改了，化简工作留给大家了。
int speaker[110];//speaker[i]用于表示第i句证词的说话者是谁。
char s[20][100]={"I am guilty.","I am not guilty.","Today is Monday.","Today is Tuesday.",\
"Today is Wednesday.","Today is Thursday.","Today is Friday.","Today is Saturday.",\
"Today is Sunday."," is guilty."," is not guilty."};
//s数组用来存一些常见的语句。
struct meaning//存储证词的含义
{
bool flag;//flag为0，表示证词是关于罪犯的，flag为1，表示证词是关于日期的。
int dir;//flag为0，dir为正时，表示证词指出dir是罪犯，dir为负是表示-dir不是罪犯，dir为0证词无意义；
//flag为1时，表示今天星期dir
}mean[110];//mean[i]表示第i句证词的含义
int main()
{
scanf("%d%d%d",&m,&n,&p);
for(int i=1;i<=m;i++)scanf("%s",name[i]);//读入姓名，第i个姓名对应编号i
for(int i=1;i<=p;i++)//本循环进行证词的处理
{
scanf("%s",a[i].name);//读入第i句证词说话者的姓名
a[i].name[strlen(a[i].name)-1]='\0';
//scanf在读入时，会将证词中的“：”也读入姓名中，去掉“：”更方便。
getchar();//“：”和后面的证词之间还有一个空格，这里将空格处理了。
gets(a[i].words);//读取后面的证词
int l=strlen(a[i].words);
if(a[i].words[l-1]=='\n'||a[i].words[l-1]=='\r'||a[i].words[l-1]==' ')
a[i].words[l-1]='\0';
//评测机使用gets时，会将语句最后的换行符等读入。这里将换行符等去掉了。
for(int j=1;j<=m;j++)//这里在确定第i句证词是谁说的。
//使用stl中map会方便一些，但是我不知道怎么给char数组用map，求大佬看到时教教我。
{
if(strcmp(a[i].name,name[j])==0)
{
speaker[i]=j;
break;
}
}
//以下部分在确定证词的含义，建议结合meaning结构体的注释来看。
if(strcmp(a[i].words,s[0])==0)//如果说的话是"I am guilty."
{
mean[i].flag=0;
mean[i].dir=speaker[i];
continue;
}
if(strcmp(a[i].words,s[1])==0)//如果说的话是"I am not guilty."
{
mean[i].flag=0;
mean[i].dir=-speaker[i];
continue;
}
bool flag=0;
for(int j=2;j<=8;j++)//判断说的话是不是"Today is XXX."
{
if(strcmp(a[i].words,s[j])==0)
{
flag=1;
mean[i].flag=1;
mean[i].dir=j-1;
break;
}
}
if(flag==1)continue;
for(int j=1;j<=m;j++)//判断证词是不是在指引其他人是罪犯
{
string sa=string(name[j])+string(s[9]);//这里将char数组强制转换为string类型
//转换之后，两个string字符串可以通过"+"首尾连接起来。
//这里将第j人的名字和" is guilty."连接在一起。
if(string(a[i].words).compare(sa)==0)
{
mean[i].flag=0;
mean[i].dir=j;
break;
}
sa=string(name[j])+string(s[10]);
//这里将第j人的名字和" is not guilty."连接在一起。
if(string(a[i].words).compare(sa)==0)
{
mean[i].flag=0;
mean[i].dir=-j;
break;
}
}
}
}
```
#### 罪犯查找
处理完证词含义之后，就开始找罪犯了。如何寻找呢？这里提供两种思路。
##### 思路一
使用深度搜索的思想，分别假设每一位同学是否是说谎者，如果矛盾了，说明情况不合适，如果没有矛盾，再判断谁是罪犯。由于情况有些复杂，这里不做详细分析。
##### 思路二
枚举每一个人和每一个星期，作为假定的罪犯和今天是星期几。再判断每一句证词，如果某人的证词中指认的罪犯与假定的罪犯相同，说明他说了真话，也就永远说真话；如果不同，说明他说了假话，也就永远说假话。其他情况同理。
如果发现某人既说了真话，又说了假话，那就说明假定的罪犯和日期是错误的，直接返回即可。如果有超过$N$人说假话，或者超过$M-N$人说真话，也是不可能的，直接返回。
如果最后发现，假定某人是罪犯是可行的，那么这个人就是罪犯；如果多个人都可行，也就是多个人都有可能是罪犯，输出```Cannot Determine```;如果任何一种方案都不可行，即任何一个人都不可能成为罪犯，输出```Impossible```。
本部分代码如下：(结合注释理解更佳）
```cpp
int ans,liar[25];//liar[i]用于判断第i个玩家是否是说谎者.
//如果为1，说明是说谎者，如果为-1，说明不是说谎者。
void judge(int guilty,int today)//假设guilty号玩家是罪犯，今天是星期today，判断会不会产生矛盾。
{
memset(liar,0,sizeof(liar));//初始化赋值为0
int T=0,F=0;//说真话的人的数量和说谎话的人的数量
for(int i=1;i<=p;i++)
{
if(mean[i].dir==0)continue;//如果语句无意义，直接跳过
int isliar=0;//用于记录“根据本证词判断说话者是否撒谎”
if(mean[i].flag==0)//如果证词是在指认罪犯
if(mean[i].dir>0)//如果证词认为某人是凶手
if(mean[i].dir==guilty)isliar=-1;//证词中的凶手和假定的凶手一致，说明没有撒谎
else isliar=1;//不一致，得出说话者撒谎了
else if(mean[i].dir==-guilty)isliar=1;
//如果证词认为不是罪犯的人是假定的罪犯，得出说话者撒谎了
else isliar=-1;//否则，说话者没有撒谎
else if(mean[i].dir==today)isliar=-1;//如果证词说的是星期，且跟假定的一样，说明没有撒谎
else isliar=1;
if(liar[speaker[i]]==0)//如果说话者之前并没有被确定是不是说谎者
{
liar[speaker[i]]=isliar;//现在确定下来了。
if(isliar==1)F++;//确定的说谎者人数+1
else T++;
}
else if(liar[speaker[i]]!=isliar)return;//如果某人既说谎，又没有说谎，直接返回。
if(F>n||T>m-n)return;//说谎者多于n人或没说谎的人多于m-n人时，直接返回
}
if(ans&&ans!=guilty)//如果之前确定了一个罪犯了，这个罪犯又和现在的罪犯不是一个人
{
printf("Cannot Determine");
exit(0);//程序执行该语句时，会直接结束整个程序。
}
ans=guilty;//确定罪犯
}
int main()
{
for(int i=1;i<=m;i++)
for(int j=1;j<=7;j++)judge(i,j);//假定罪犯是i，今天是星期j，判断能否成立。
if(ans)printf("%s",name[ans]);//如果有罪犯，输出罪犯的名字
else printf("Impossible");//如果没有答案，输出 "Impossible"
}
```
### 完整AC代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,p;
char name[25][250];
struct node//存储证词信息。
{
char name[250],words[250];
}a[110];
//写到后面发现这个结构体完全没有用，因为在处理完证词的含义之后，语句原内容都可以丢弃了。
//整个结构体可以化简为两个char数组。我只是单纯懒得改了，化简工作留给大家了。
int speaker[110];//speaker[i]用于表示第i句证词的说话者是谁。
char s[20][100]={"I am guilty.","I am not guilty.","Today is Monday.","Today is Tuesday.",\
"Today is Wednesday.","Today is Thursday.","Today is Friday.","Today is Saturday.",\
"Today is Sunday."," is guilty."," is not guilty."};
//s数组用来存一些常见的语句。
struct meaning//存储证词的含义
{
bool flag;//flag为0，表示证词是关于罪犯的，flag为1，表示证词是关于日期的。
int dir;//flag为0，dir为正时，表示证词指出dir是罪犯，dir为负是表示-dir不是罪犯，dir为0证词无意义；
//flag为1时，表示今天星期dir
}mean[110];//mean[i]表示第i句证词的含义
int ans,liar[25];//liar[i]用于判断第i个玩家是否是说谎者.
//如果为1，说明是说谎者，如果为-1，说明不是说谎者。
void judge(int guilty,int today)//假设guilty号玩家是罪犯，今天是星期today，判断会不会产生矛盾。
{
memset(liar,0,sizeof(liar));//初始化赋值为0
int T=0,F=0;//说真话的人的数量和说谎话的人的数量
for(int i=1;i<=p;i++)
{
if(mean[i].dir==0)continue;//如果语句无意义，直接跳过
int isliar=0;//用于记录“根据本证词判断说话者是否撒谎”
if(mean[i].flag==0)//如果证词是在指认罪犯
if(mean[i].dir>0)//如果证词认为某人是凶手
if(mean[i].dir==guilty)isliar=-1;//证词中的凶手和假定的凶手一致，说明没有撒谎
else isliar=1;//不一致，得出说话者撒谎了
else if(mean[i].dir==-guilty)isliar=1;
//如果证词认为不是罪犯的人是假定的罪犯，得出说话者撒谎了
else isliar=-1;//否则，说话者没有撒谎
else if(mean[i].dir==today)isliar=-1;//如果证词说的是星期，且跟假定的一样，说明没有撒谎
else isliar=1;
if(liar[speaker[i]]==0)//如果说话者之前并没有被确定是不是说谎者
{
liar[speaker[i]]=isliar;//现在确定下来了。
if(isliar==1)F++;//确定的说谎者人数+1
else T++;
}
else if(liar[speaker[i]]!=isliar)return;//如果某人既说谎，又没有说谎，直接返回。
if(F>n||T>m-n)return;//说谎者多于n人或没说谎的人多于m-n人时，直接返回
}
if(ans&&ans!=guilty)//如果之前确定了一个罪犯了，这个罪犯又和现在的罪犯不是一个人
{
printf("Cannot Determine");
exit(0);//程序执行该语句时，会直接结束整个程序。
}
ans=guilty;//确定罪犯
}
int main()
{
scanf("%d%d%d",&m,&n,&p);
for(int i=1;i<=m;i++)scanf("%s",name[i]);//读入姓名，第i个姓名对应编号i
for(int i=1;i<=p;i++)//本循环进行证词的处理
{
scanf("%s",a[i].name);//读入第i句证词说话者的姓名
a[i].name[strlen(a[i].name)-1]='\0';
//scanf在读入时，会将证词中的“：”也读入姓名中，去掉“：”更方便。
getchar();//“：”和后面的证词之间还有一个空格，这里将空格处理了。
gets(a[i].words);//读取后面的证词
int l=strlen(a[i].words);
if(a[i].words[l-1]=='\n'||a[i].words[l-1]=='\r'||a[i].words[l-1]==' ')
a[i].words[l-1]='\0';
//评测机使用gets时，会将语句最后的换行符等读入。这里将换行符等去掉了。
for(int j=1;j<=m;j++)//这里在确定第i句证词是谁说的。
//使用stl中map会方便一些，但是我不知道怎么给char数组用map，求大佬看到时教教我。
{
if(strcmp(a[i].name,name[j])==0)
{
speaker[i]=j;
break;
}
}
//以下部分在确定证词的含义，建议结合meaning结构体的注释来看。
if(strcmp(a[i].words,s[0])==0)//如果说的话是"I am guilty."
{
mean[i].flag=0;
mean[i].dir=speaker[i];
continue;
}
if(strcmp(a[i].words,s[1])==0)//如果说的话是"I am not guilty."
{
mean[i].flag=0;
mean[i].dir=-speaker[i];
continue;
}
bool flag=0;
for(int j=2;j<=8;j++)//判断说的话是不是"Today is XXX."
{
if(strcmp(a[i].words,s[j])==0)
{
flag=1;
mean[i].flag=1;
mean[i].dir=j-1;
break;
}
}
if(flag==1)continue;
for(int j=1;j<=m;j++)//判断证词是不是在指引其他人是罪犯
{
string sa=string(name[j])+string(s[9]);//这里将char数组强制转换为string类型
//转换之后，两个string字符串可以通过"+"首尾连接起来。
//这里将第j人的名字和" is guilty."连接在一起。
if(string(a[i].words).compare(sa)==0)
{
mean[i].flag=0;
mean[i].dir=j;
break;
}
sa=string(name[j])+string(s[10]);
//这里将第j人的名字和" is not guilty."连接在一起。
if(string(a[i].words).compare(sa)==0)
{
mean[i].flag=0;
mean[i].dir=-j;
break;
}
}
}
for(int i=1;i<=m;i++)
for(int j=1;j<=7;j++)judge(i,j);//假定罪犯是i，今天是星期j，判断能否成立。
if(ans)printf("%s",name[ans]);//如果有罪犯，输出罪犯的名字
else printf("Impossible");//如果没有答案，输出 "Impossible"
}
```