如何建设影视网站首页,购物网站开发语言,汨罗网站建设,网站个人备案做论坛此题难度为#xff1a;提高/省选-
作者为#xff1a;CCF_NOI
题目描述
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中#xff0c;于是他召集了一群同学玩推理游戏。游戏的内容是这样的#xff0c;明明的同学们先商量好由其中的一个人充当罪犯#xff08;在明…此题难度为提高/省选-
作者为CCF_NOI
题目描述
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中于是他召集了一群同学玩推理游戏。游戏的内容是这样的明明的同学们先商量好由其中的一个人充当罪犯在明明不知情的情况下明明的任务就是找出这个罪犯。接着明明逐个询问每一个同学被询问者可能会说 证词中出现的其他话都不列入逻辑推理的内容。
明明所知道的是他的同学中有 NN 个人始终说假话其余的人始终说真。
现在明明需要你帮助他从他同学的话中推断出谁是真正的凶手请记住凶手只有一个
输入格式
输入由若干行组成。
第一行有三个整数M,NM,N 和 PP。MM 是参加游戏的明明的同学数NN 是其中始终说谎的人数PP 是证言的总数。
接下来 MM 行每行是明明的一个同学的名字英文字母组成没有空格全部大写。
往后有 PP 行每行开始是某个同学的名宇紧跟着一个冒号和一个空格后面是一句证词符合前表中所列格式。证词每行不会超过 250250 个字符。
输入中不会出现连续的两个空格而且每行开头和结尾也没有空格。
输出格式
如果你的程序能确定谁是罪犯则输出他的名字如果程序判断出不止一个人可能是罪犯则输出 Cannot Determine如果程序判断出没有人可能成为罪犯则输出 Impossible。
输入输出样例
输入 #1
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??
输出#1
MIKE
说明/提示
对于 100\%100% 数据满足 1≤M≤200≤N≤M1≤ P≤100。
解析加代码
//可以用map存人名对应的下标 //我们枚举每一个人i假设i是罪犯
//然后枚举今天是星期几用day表示
//然后判断有没有矛盾//如何判断
//进行每一次判断的时候先使所有人的状态不确定也就是不知道他们会说真话假话
//TF[a]-1是不确定TF[a]1是说真话TF[a]0是说假话
//T是说真话的人数F是说假话的人数
//设罪犯为 i
//设flag为这句话是真话还是假话flag1是真话flag0是假话
//id是说这句话的人
//枚举每一句话
// 看一下id以前的状态如果状态不确定TF-1就TF[id]flag
// 否则如果和以前状态一样(TF[id]flag)就没有矛盾
// TF[id]!flag就是出现了矛盾(因为一个人始终直说一种话)判断不出来了直接return去枚举下一个人是罪犯
//如果Fn或者Tm-n了也就是说假话的人数超过了题目中给的人数矛盾return
//如果找到了不止一个罪犯输出Cannot Determine直接exit(0) //怎么知道这句话是真话假话
//①如果话里有 I am guilty.
// 那么看一下id是不是i不是的话就是在说假话
//②话里有I am not guilty
// 看一下id是不是i不是的话就是在说真话否则就是假话
//③话里有xxx is guilty
// 如果xxx是i的话就是真话否则是假话
//④话里有xxx is not guilty
// 如果xxx不是i的话就是真话否则是假话
//⑤话里有Today is XXX
// 如果xxx与day一样就是真话否则是假话#includeiostream
#includecstdio
#includecstring
#includemap
#includealgorithm
using namespace std;string S[10]
{Today is Sunday.,Today is Monday.,Today is Tuesday.,Today is Wednesday.,Today is Thursday.,Today is Friday.,Today is Saturday.,
};int m,n,p;
int T,F,ans;
int TF[25];
struct Sen
{int id;string s;
}sen[105];
mapstring,int ma;bool judgeTF(int id,bool flag) //看一下有没有冲突return 1 表示有冲突
{if(TF[id]-1) //状态不确定 {TF[id]flag; //赋状态 if(flag) //说真话的人数 T;else //说假话的人数 F;}elsereturn TF[id]!flag; //和之前的一不一样一样返回0不一样返回1 if(Fn||Tm-n) //说假话的人比n多或者是说真话的人比m-n多 return 1;return 0;
}void judge(int id,string day)
{memset(TF,-1,sizeof(TF)); //所有人都不知道说的是真话假话 TF0; //说真话、假话人数置0 string tmp;for(int i1;ip;i){int possen[i].s.find(I am guilty.); //pos为-1则没说这句话 if(~pos){if(judgeTF(sen[i].id,sen[i].idid)) //因为我们假设了id是罪犯所以不是id的人就不是罪犯就是在说假话return;}possen[i].s.find(I am not guilty);if(~pos){if(judgeTF(sen[i].id,sen[i].id!id))return;}possen[i].s.find( is guilty.);if(~pos){tmpsen[i].s;tmp.erase(pos,11);if(judgeTF(sen[i].id,ma[tmp]id))return;}possen[i].s.find( is not guilty.);if(~pos){tmpsen[i].s;tmp.erase(pos,15);if(judgeTF(sen[i].id,ma[tmp]!id))return;}possen[i].s.find(Today is );if(~pos){if(judgeTF(sen[i].id,sen[i].sday))return;}}if(ansans!id) //找到了不止一个罪犯 {puts(Cannot Determine); //不能确定 exit(0);}ansid; //id是罪犯
}string s[25],name,a;
int main()
{scanf(%d%d%d,m,n,p);for(int i1;im;i){cins[i];ma[s[i]]i; //存名字标号 }for(int i1;ip;i){cinname; //输入说话者 name.erase(name.length()-1,1); //把后边的冒号搞掉 getline(cin,a);a.erase(0,1); //把前边的空格搞掉 if(a[a.length()-1]\n||a[a.length()-1]\r) //把坑爹的换行符搞掉 a.erase(a.length()-1,1);sen[i].idma[name]; //存说话者 sen[i].sa; //存说话内容 }for(int i1;im;i) //假设第i个人是罪犯 for(int j0;j7;j) //假设今天是S[j]天 judge(i,S[j]);if(!ans) //找不到罪犯 puts(Impossible);elsecouts[ans]; //罪犯名字 return 0;
}
成功图片
