IOI2009 试题讨论.


78 views
Uploaded on:
Description
IOI2009 试题讨论. 清华大学 高逸涵. 题目一览. Day 1 Archery 较难 Hiring 中等 POI 简单 Raisins 简单. Archery. 在一场射箭比赛中,比赛规则如下: 有 N 个靶位排成一排,每一轮每个靶位上两位选手进行比赛,编号小的选手一定胜出。 在 2 到 N 号靶位上的胜者移动到编号减一的靶位,负者不移动 在 1 号靶位上的胜者不移动,负者移动到 N 号靶位 初始时其他 2N-1 个选手已经排好顺序,你可以选择一个位置插队,然后按照顺序每两个选手对应一个靶位。
Transcripts
Slide 1

IOI2009 试题讨论 清华大学 高逸涵

Slide 2

题目一览 Day 1 Archery 较难 Hiring 中等 POI 简单 Raisins 简单

Slide 3

Archery 在一场射箭比赛中,比赛规则如下: 有 N 个靶位排成一排,每一轮每个靶位上两位选手进行比赛,编号小的选手一定胜出。 在 2 到 N 号靶位上的胜者移动到编号减一的靶位,负者不移动 在 1 号靶位上的胜者不移动,负者移动到 N 号靶位 初始时其他 2N-1 个选手已经排好顺序,你可以选择一个位置插队,然后按照顺序每两个选手对应一个靶位。 比赛一共进行 R 轮,你希望在 R 轮之后排位尽量高,在此前提下插入的位置应尽量靠后。

Slide 4

Archery (cont\'d) 数据规模 2 <= N <= 200,000 2N <= R <= 1000,000,000 60% 的数据中, N 不超过 5,000 20% 的数据中, N 不超过 200

Slide 5

算法讨论 请同学们踊跃发言!

Slide 6

算法讨论 (cont\'d) 简单分析后,似乎可以发现,经过一定轮之后,选手的位置会呈现一种循环的状态。

Slide 7

算法讨论 (cont\'d) 一旦选手们的位置进入这种状态,经过若干轮之后的位置就可以通过数学计算直接得出。 那么首先要解决的问题是 是否在有限轮之后一定能到达这种状态? 如果是,至多经过多少轮?

Slide 8

算法讨论 (cont\'d) 定理:经过一定轮(不超过 2N )之后,比赛一定会进入循环。 证明:我们只需证明在 1 号选手到达一号靶位之后 N 轮之内会进入循环即可。设 2~N+1 号选手为 A 类选手,其余为 B 类选手,并假设所有靶位排成一个圈,那么当 A 类选手和 B 类选手相遇时, A 类选手一定向左移动。

Slide 9

算法讨论 (cont\'d) 所以我们考虑一个 B 类选手,如果他在某一轮没有进行移动,我们可以认为他以后也不会再移动了。 假设 N 轮之后还有 B 类选手在移动,那么他一定移动了 N 轮,也就是说他一定经过了某一个靶位,上面没有 B 类选手,这就导致了矛盾。

Slide 10

算法一 (cont\'d) 枚举插队位置,模拟 2N 轮比赛,直到比赛进入循环,然后计算最终位置。 算法复杂度: O(N^3) 绝大多数选手第一时间想到的算法 只能得到 20 分

Slide 11

算法二 根据待插入的选手的实力,可以分为三种情况分别进行处理: 如果待插入选手本身就是最强的,那么显然可以直接插入队尾。 如果实力介于 2 和 N+1 之间,那么需要找到一个合适的位置插入,使得开始循环后处于一个适当的位置使得最后结束的位置尽量靠前。 如果实力比 N+1 还要弱,那么选择一个合适的位置插入使得循环开始后的静止位置尽量靠前

Slide 12

算法二 (cont\'d) 对于选手实力介于 2 和 N+1 之间的情况,选手会不停地循环,因此我们只需要计算出 2N 轮之后的哪一轮这个选手在一号靶位进行比赛即可。 如果我们能够快速模拟一号靶位上的比赛进行情况,那么整个问题也就迎刃而解。

Slide 13

算法二 (cont\'d) 考虑每一轮从二号靶位晋级到一号靶位的选手: 第一轮,是二号靶位上的胜者 第二轮,是上轮二号靶位上的败者和三号靶位上的胜者中的较强的一个。 第三轮,是 … 简而言之,就是在这一轮能够到达二号靶位的所有选手除去之前已经晋级的选手外的最强者

Slide 14

算法二 (cont\'d) 可以利用堆来进行维护。 如果注意到对于任意两个选手,如果他们都比我们要考虑的选手强或者弱,那么他们两个之间的比赛胜负不影响最终结果。 因此可以将所有选手分为三类,每类选手之间没有差别。 可以直接维护这两类选手的个数,这样每次只需要进行常数次运算。

Slide 15

算法二 (cont\'d) 如果选手实力比 N+1 号选手还要弱,那么他最终会停留在某个靶位直到比赛结束。 可以首先确定 2N 号选手的最终停留位置,然后确定 2N-1 号选手的最终停留位置,依次进行下去直到得到结果。

Slide 16

算法三 注意到,上述算法可以在模拟的同时计算出选手一共多少次从 1 号靶位移动到 N 号靶位的次数(设这一数字为 T ),结合选手的最终的位置(设这一数字为 X ),如果我们用 X-N*T 来表示模拟结果的话,我们可以认为选手每移动一次就会使结果减 1 。然后如果我们直观地观察模拟算法,就会发现它的结果关于初始位置是单调的,这样我们就可以利用二分检索算法解决问题。

Slide 17

算法三 (cont\'d) 二分检索流程: 计算从 1 号靶位开始的最终位置 计算从 N 号靶位开始的最终位置 二分查找每一个比 N 的倍数大的最小的最终位置 从上述选出的开始位置中选出一个最好的作为答案 容易证明总复杂度为 O(NlogN) 。

Slide 18

Hiring 你需要从 N 个工人中雇佣一些工人。每个工人期望的最低工资为 Sk 美元,技术等级是 Qk 。要求雇佣的工人中支付给每个工人的工资与他的技术等级成正比,并且满足他们期望的最低工资。 你手上有 W 美元 , 希望能雇佣尽可能多的工人,并且总预算不超过 W 美元。如果有多种方案,输出所雇佣工人总工资最少的方案。

Slide 19

Hiring (cont\'d) 数据规模 half 的测试数据, N ≤ 5000 。 所有的测试数据, 1 ≤ N ≤ 500000 ,, 1≤ Sk ≤ 20000 , 1≤ Qk ≤ 20000 , 1≤ W ≤ 10000000000 。

Slide 20

算法讨论 每个工人只有两种属性,期望的最低工资为 Sk 美元,技术等级 Qk 。 设我们要雇佣的工人集合为 K 。由于题目中要求雇佣的工人的工资与技术等级成正比,我们可以将这个比值设出来,不妨设为 p ,那么依据题目条件,对于 k ∈ K ,有 Qk × p ≥ Sk 。 p=max { Sk/Qk | k ∈ K }

Slide 21

算法讨论 (cont\'d) 将所有工人按照 Sk/Qk 排序,从小到大枚举 p 的值,然后在所有可选的工人中选取 Qk 最小的若干个。 注意到,如果一个工人在 p 较小时可以选取但没有被选取,那么他在 p 变大时也不会再被选取。 因此可以利用堆进行维护。

Slide 22

算法讨论 (cont\'d) 上述算法还有优化的余地,可以不使用任何高级数据结构解决问题,进而降低编程复杂度。 这个问题留给同学思考。

Slide 23

Raisins 有一块 N×M 的巧克力,需要将其分成 1×1 的小块。每次可以将一块巧克力用横向或纵向的切割线分为独立的两块。每一块 1×1 的巧克力上都有若干葡萄干,每次切割一块巧克力需要花费的葡萄干数目与该巧克力上葡萄干的数量相等。 给定每块 1×1 的巧克力上的葡萄干数目,求总花费最少的分割方案。

Slide 24

Raisins 动态规划 一个子矩形可以用 4 个数来描述,枚举切割线的位置来进行状态转移。 时间复杂度: O(N 2 M 2 (N+M)) 空间复杂度: O(N 2 M 2 )

Slide 25

ICPC 题目讨论

Slide 26

Decrypt Messages 计算方程 x^q=a(mod p) 的所有解 1<=q<=10 , p 是质数, 2< p ≤1000000007

Slide 27

Decrypt Messages 如果对于某个正整数 a(1<a<p) , a 1 ,a 2 ,a 3 ,… … ,a p-1 模 p 取遍 1,… … ,p-1 的所有数,则称 a 为 p 的一个原根。 如果我们找到了 p 的一个原根 m ,设 x=m y ,a=m z , 则原方程转化为 m ya =m z (mod p) ,又由原根的性质,上述方程等价于 ya=z(mod p-1)

Slide 28

Decrypt Messages 对于一般的质数,它的原根个数一般是非常之多的 所以我们可以逐一枚举并检验这些数是否是原根 一个数 a 是原根当且仅当 a 1 ,… … ,a p-2 都不 mod p=1 所以我们只需要检验 a b 是否 mod p=1 ,其中 b 为 p-1 的约数

Slide 29

Jiajia\'s Robot 在平面上有两条线段(两条线段不退化为点,至多有一个交点),一个机器人能够射出两道互相垂直的射线,如果这两条射线分别能和这两条线段相交,则这个机器人可以定位,求平面上所有可定位的点构成区域的面积。

Slide 30

Jiajia\'s Robot 简单的画几个图可以猜测结论为四个圆的面积并减去四个圆的面积交。 证明可以从简单的情况开始讨论 如果其中一个线段退化成了点,情况是什么样子,然后推广到两个线段的情况。

Slide 31

Exciting Time 维护一个宽度为 (1<=W<=30000) 的俄罗斯方块游戏,一共有 N(1<=N<=30000) 块掉下来,计算最后的分数以及每一列的最终高度。

Slide 32

Wires 给定平面上四个点,允许添加至多 3 个点,使得这些点的最小生成树最小。

Slide 33

The Number of Sequence Pair 给定两个序列 A = {a[1], a[2], … , a[n]}, B = {b[1], b[2], … , b[n]} ,序列 A , B 的和为 {a[1] + b[1], a[1] + b[2], … , a[2] + b[1], … , a[n] + b[n]} 一共 N*N 项如果这 N*N 项两两不同并且都在 1 和 N*N 之间,那么称这两个序列 A , B 是配对的。 给定 N ,求有多少个本质不同的序列对。我们认为将一个序列对整体加 X ,并将另一个序列整体减 X 得到的新序列对和原序列对是本质相同的

Slide 34

Mission Impossible 给定一个有向图,某一些点有和外部连接的边,每一个节点都有至少一个入度和出度,将它分为若干块,使得每一块的所有输入边都和所有输出边之间有路径相连,并且要求答案是极小的,即不存在若干个块,把他们合并为一块之后仍旧满足题目要求。 1<=N<=10000

Slide 35

.:tsli

Recommended
View more...