NOIP 2003 侦探原理 大模拟+枚举
发布日期:2021-10-02 10:57:37
浏览次数:33
分类:技术文章
本文共 3929 字,大约阅读时间需要 13 分钟。
题目大意:有一些小孩闲着没事玩游戏,他们M个人中有N个人肯定说假话,剩下的人肯定说实话,有一个人是罪犯,求这个罪犯。
他们会说出如下的话:
证词内容 | 证词含义 |
I am guity | 我是罪犯 |
I am not guity. | 我不是罪犯 |
Xxx is guity | Xxx 是罪犯( Xxx 表示某个同学的名字) |
XXX is not guity | Xxx 不是罪犯 |
Today is XXX | 今天是 Xxx ( Xxx 表示星期几 |
思路很简单,就是枚举今天是那一天和罪犯是谁就行。但这个题有很多巨坑。
巨坑1:上面的表格是错的。。(我直接从oj粘下来的,注意他的“guity”的拼写是错的,一定要复制“guilty”)
巨坑2:测试数据里有个人叫“ I ” 的人。。(还好没有叫Today的人。。)
巨坑3:如果你把一个句子判断完了,要看看后面还有没有字符。如果有的话,该句作废。。。
废话不多说,上CODE:
#include#include #include #include #define MAX 300using namespace std;const char weekdays[10][20] = {"","Monday.","Tuesday.","Wednesday.","Thursday.","Friday.","Saturday.","Sunday."};struct Complex{ int effect; int weekday; int from,person; bool opt; Complex() { weekday = 0; effect = 0; }}info[MAX];int points,lies,sens;char src[MAX][50];char temp[MAX];inline void Work(char *s,int pos);inline void GetString(char *&s,char *aim);inline bool Check(int guilty,int week);inline bool Lie(Complex information,int guilty);int main(){ cin >> points >> lies >> sens; for(int i = 1;i <= points; ++i) scanf("%s",src[i]); getchar(); for(int i = 1;i <= sens; ++i) { fgets(temp,1000,stdin); Work(temp,i); } bool found = false; int ans = -1; for(int i = 1;i <= points; ++i) { bool temp = false; for(int j = 1;j <= 7; ++j) { if(Check(i,j)) temp = true; } if(temp && !found) ans = i,found = true; else if(temp) { printf("Cannot Determine"); return 0; } } if(ans == -1) printf("Impossible"); else printf("%s",src[ans]); return 0;}inline void Work(char *s,int pos){ char temp[MAX]; GetString(s,temp); temp[strlen(temp) - 1] = '\0'; for(int i = 1;i <= points; ++i) if(!strcmp(temp,src[i])) info[pos].from = i; GetString(s,temp); if(!strcmp(temp,"Today")) { info[pos].effect = 1; GetString(s,temp); GetString(s,temp); for(int i = 1;i <= 7; ++i) if(!strcmp(temp,weekdays[i])) info[pos].weekday = i; if(*s != '\0' && *s != '\n') info[pos].effect = 0; } else if(!strcmp(temp,"I")) { info[pos].effect = 2; info[pos].person = info[pos].from; GetString(s,temp); if(!strcmp(temp,"is")) { int p = 0; for(int i = 1;i <= points; ++i) if(!strcmp("I",src[i])) p = i; info[pos].person = p; } GetString(s,temp); if(!strcmp(temp,"not")) info[pos].opt = false,GetString(s,temp); else if(!strcmp(temp,"guilty.")) info[pos].opt = true; else info[pos].effect = 0; if(*s != '\0' && *s != '\n') info[pos].effect = 0; } else { int p = 0; for(int i = 1;i <= points; ++i) if(!strcmp(temp,src[i])) p = i; if(p) { info[pos].effect = 2; info[pos].person = p; GetString(s,temp); GetString(s,temp); if(!strcmp(temp,"not")) info[pos].opt = false,GetString(s,temp); else if(!strcmp(temp,"guilty.")) info[pos].opt = true; else info[pos].effect = 0; if(*s != '\0' && *s != '\n') info[pos].effect = 0; } }}inline void GetString(char *&s,char *aim){ sscanf(s,"%s",aim); s += strlen(aim) + 1;}inline bool Check(int guilty,int week){ static int status[MAX]; memset(status,-1,sizeof(status)); for(int i = 1;i <= sens; ++i) { if(info[i].effect == 1) { if(info[i].weekday != week) { if(status[info[i].from] == 1) return false; else status[info[i].from] = 0; } else { if(status[info[i].from] == 0) return false; else status[info[i].from] = 1; } } else if(info[i].effect == 2) { if(!Lie(info[i],guilty)) { if(status[info[i].from] == 1) return false; else status[info[i].from] = 0; } else { if(status[info[i].from] == 0) return false; else status[info[i].from] = 1; } } } int cnt = 0; for(int i = 1;i <= points; ++i) if(!status[i]) cnt++; if(cnt > lies) return false; for(int i = 1;i <= points; ++i) if(status[i] == -1) cnt++; if(cnt < lies) return false; return true;}inline bool Lie(Complex information,int guilty){ if(information.opt) { if(information.person != guilty) return false; else return true; } else { if(information.person == guilty) return false; else return true; }}
转载地址:https://blog.csdn.net/jiangyuze831/article/details/39177331 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年03月26日 08时15分08秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
线性代数matlab应用,线性代数中的MATLAB应用
2019-04-21
matlab算kappa系数,[转载]Kappa系数的计算及应用
2019-04-21
基于matlab的三相整流,基于MATLAB的三相整流电路的仿真研究
2019-04-21
aide 可以用php.么,Linux加密安全—AIDE工具
2019-04-21
鸿蒙合作的app,华为发布鸿蒙OS元服务,超300家应用合作伙伴加入
2019-04-21
微信和鸿蒙系统谁大,腾讯工程师引发众怒!太嚣张,网友:怪不得鸿蒙系统没有微信...
2019-04-21
android pop,android下popwindow +Spinner问题
2019-04-21
html属性id和name,html标签中id和name的区别
2019-04-21
css3实现缺角四边形_CSS3实现缺角矩形,折角矩形以及缺角边框
2019-04-21
ds18b20触摸没反应_求助DS18B20读不出正确的数据
2019-04-21
委以重用的意思_第三章 委以重用
2019-04-21
go get 代码找不到_Go 语言基于 channel 实现的并发安全的字节池
2019-04-21
c++ map底层实现原理_红黑树TreeSet原理HashSet底层原理Map集合遍历
2019-04-21