ACM主席是谁.pptVIP

ACM主席是谁？ 新加入ACM的小艺不知道谁是主席，于是他就到处问ACM会员，希望能得到答案。可是ACM的人好象不太诚实，小艺问了几个人，他们的答案矛盾。但是小艺能知道他们当中有N个人始终在说谎。请你编程解决小艺的难题。 ACM主席是谁？ 小艺总共询问了M个人，其中知道有N个人说谎。相应的有M-N个人是说真话的人。（说谎的人可能只说慌，也可能说慌也说废话，也可能只说废话。也可能他没说话，但绝对不会说真话；说真话的人可能只说真话，也可能说真话也说废话，也可能只说废话，还可能不说话，但是绝不会说假话；） 不关键的话不计算,排除.不影响这个人. 根据他们的话推测谁可能是主席。ACM会员的有效对话如下（不在此列的话都认为是废话） 会员们的话含义 I am chairman. 我是主席. I am not chairman. 我不是主席. XXX is chairman. XXX 是主席. （Xxx 代表某个人的名字） XXX is not chairman. XXX 不是主席. （Xxx 代表某个人的名字） 注意每句话都使用句号结尾 （别忘了：）） 考查点 本题主要考查选手在字符串的处理能力和一些逻辑判断能力 注意两个部分: 1.字符串处理 2.逻辑判断能力 字符串部分 主要体现在对话的操作上 例:CHARLES: MIKE is chairman. 1.利用句号读入字符串 每行开始是某个会员的名宇，紧跟着一个冒号和一个空格，后面是一句话，均以句号‘.‘结尾，符合前表中所列格式 2.字符串比较 分成两段比较：名字,类型 3.字符串定义长度 尽量定长点,大数据随时可能出现,比如名字.. 逻辑部分 [分析]基本思路有两种： 一是可以穷举M个人中有N个人始终说假话的所有组合，据此出发，判断每句话的真伪，再推断谁是主席，但这样做运算量大； 二是可以穷举M个人中的任意一个是主席，由此再来判断每句话的真伪，推断谁说真话谁说假话，这样做运算量小得多。 这里采用后者。 有2点必须注意： 一，不能说找到某人是主席或可能是主席就完事了，还必须确保是否还有别人是主席或可能是主席； 二，某人的话可能前后矛盾，在给某人标记他是始终说真话还是始终说假话时，一定要考察他此前的诚信记录； 因此，对某人的诚信记录要有4种不同的区分， 可用0表示此人尚无有效记录（未说过真话也未说过假话），用1表示此人说真话，用2表示此人说假话，用3表示此人说的话与他前面的证词冲突； 如何判断最初穷举时设定的前提（某人是罪犯）是否是本题的一个解呢？如果有人的诚信记录为3，则肯定不是本题的解；但是也不能强求诚信记录为2的人的总数一定要等于n，而是只要诚信记录为2的人不超过n且诚信记录为1的人不超过m-n即可，因为诚信记录为0的人可能说真话也可能说假话，他们只是没有说话，或只说了废话。 判断流程 1依次假设每个人是主席. 2判断对话的真伪,一句一句判断 3每次判断:所有人一开始全属于上面说的0的情况(没说过话) 4若判断出是句废话,那么不作任何操作 5判断是句真话,那么0变1(说真话),2变3(真话假话都说过,矛盾 6判断是句假话,那么0变2(说假话),1变3(真话假话都说过.矛盾. 最后,若没出现矛盾且符合2的人不超过N,符合1的人不超过M-N则假设的这个人可能为主席,反之不可能为主席 题目总结 难点 1.字符串操作相当烦琐. 2.逻辑判断不能出漏洞,特别是出现特殊情况的判断要准确.需要思维缜密. 有关字符串题目都需要大家的耐心和细心 题目由NOI’P竞赛题改编 * * * * *