IOI2013与博弈论_王康宁.pptx

"IOI2013与博弈论_王康宁.pptx" 本资源摘要信息共分为两个部分，分别是 Problem 1: 洞穴(cave) 和 Problem 2: 机器人(robots)。这两个问题都是 IOI2013 的比赛题目。 Problem 1: 洞穴(cave) 问题描述：某系统由 N 道连续的门和 N 个开关组成。每个开关都有“上”和“下”两种状态，其中有且只有一种状态是正确的。如果一个开关处于正确的状态，它所对应的门就会打开；如果它处于错误的状态，与之对应的门就会关闭。不同的开关有不同的正确状态，但你并不知道哪个开关在哪种状态下是正确的。你的任务是确定每个开关的正确状态是什么，以及门和开关之间的对应关系。 解决方案：可以使用二分查找的方法，每次可以减少一半的可能选择。这样做需要约 N*log2N 次询问，符合题中要求。 Problem 2: 机器人(robots) 问题描述：有一共 N 个玩具，整数 W[i] 表示这个玩具的重量，整数 S[i] 表示这个玩具的体积。有 A 个弱机器人，每个弱机器人有一个重量限制 X[i)，它只能拿起重量严格小于 X[i] 的玩具，与玩具的体积大小没关系。有 B 个小机器人，每个小机器人有一个体积限制 Y[i)，它只能拿起体积严格小于 Y[i] 的玩具，与玩具的重量大小没有关系。你的任务是确定 Marita 的机器人是否可以将所有的玩具都收拾好，如果是，那么最少用多少时间可以收拾好。 解决方案：可以使用二分答案的方法，这样只需检验 m 分钟内是否可以把所有玩具收拾好。将每个玩具 i 与坐标 (W[i]:重量, S[i]:体积) 对应，这样每个弱机器人可以收拾某一横坐标以左的玩具，每个小机器人可以收拾某一纵坐标以下的玩具。从右至左添加这些玩具，一旦某一时刻某个弱机器人可以收拾当前玩具，则它可以收拾之后的所有玩具。因此我们应尽量保留弱机器人，即优先使用小机器人。选择小机器人时，当然应该优先选择可以收拾当前玩具的小机器人中，Y[i] 值最小的一个。 这两个问题都是 IOI2013 的比赛题目，都是关于博弈论和算法的应用。解决这两个问题需要使用二分查找和贪心策略等算法技巧。