算法合集之《浅谈问答式交互问题》3.ppt

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