《答案只有一个》由会员分享，可在线阅读，更多相关《答案只有一个（25页珍藏版）》请在金锄头文库上搜索。
1、答案只有一个浅谈问答式交互问题交互式问题的分类分类依据：库函数和选手程序的关系博弈式交互问答式交互博弈式交互问答式交互问答式交互的逻辑模型最后的答案发现之旅我们的目标把题目做对，拿到分数。不管用什么方法，在题目允许的情况下完成此题把题目做好。用较好的方法把交互式题目做得简洁、漂亮。用合适的方法，找出那唯一可能的解。探讨这一类问题的解决策略。触类旁通，争取为其它问题提供灵感。我们的工具解决问题的两种思路思路一：“筛”法一言以蔽之：减少答案的不确定性 ！提问的选择范围：可能降低问题不确定性的所有问题。如何选择提出的问题：随机选择；平均信息量最大的;选最坏情况下筛去最多的；古老的分类学界：动物界门：
2、节肢动物门纲：昆虫纲目：双翅目科：蝇科 属：蝇属 种：家蝇结论：这是一只苍蝇！思路二：构造法构造一种提问题的序列，或者一种生成该序列的算法，按照这样的序列提问，找出唯一的符合题目意思的答案。这是一种“一开始就有计划的提问方式”。两种方法的比较筛法问题规模：不能太大当前可能为答案的各个元素之间的逻辑关系不明显思维难度：小实现难度：大往往不能准确估计最坏情况下提问次数构造法问题规模：任意当前可能为答案的各个元素之间有明显的逻辑关系思维难度：往往不小实现难度：往往不大往往可以准确估计最坏情况下提问次数实战：进入问题之旅要素题目的模型交互的方法评分的标准地下城市和太空站之谜模型相似交互方式相似推论：解
3、题策略相似？事实上：解题策略不相似！评分方式不相似！地下城市：M太空站：32768地下城市和太空站之谜的启示不同的评分标准，将决定不同的解题策略的使用！以不同的标准来评判不同的算法，优劣自然不同！多数派一个学校有奇数个学生，分成两个不相交的团体：多数派和少数派请你确定一个一定属于多数派的学生。交互规则：给出学生编号，得到两个学生是不是同一个团体的信息。评分：在m次提问后得到正确答案，一共有n个人。你的得分是min(n-m,0)的线性函数。警告：测试库迫使你进入最坏的情况，并且一旦你给出的学生可能属于少数派，我们就生成一个这样的例子作为本轮的测试数据。多数派问题的解法一N=11少多解法一的分析得
4、分：1优点：简单，并且找出了每一个学生属于哪个团体。缺点：过于简单，没有优化。虽然找出了每一个学生属于哪个团体，但是题目并没有要求我们这样做。灵机一动：不找出每个学生属于哪个集合，仅确定一个属于多数派的学生！多数派问题解法二多数派问题解法二不同组相同组调皮的小孩ABB=星星队A=星星队星星队月亮队否否月亮队月亮队是是星星队星星队是是星星队裁判否是月亮队裁判是否小结灿烂星河IOI2000 中等硬度IOI2002 Rods冬令营 2002 太空站之谜冬令营 2001 猜单词游戏NOI 2002 调皮的小孩CEOI2001 多数派CEOI2001 ChainIPSC 2002 Chamber of SecretsPOI Ulam的游戏大浪淘沙千淘万漉虽辛苦，吹尽黄沙始到金！
