集训队试题 - PDF Free Download

IOI 2012 中国信息学国家集训队命题答辩试题册教练 : 胡伟栋唐文斌中国计算机学会 2012 年 5 月

答辩顺序答辩顺序姓名所在学校试题名称 1 李超浙江省杭州学军中学拆弹计划 2 徐捷浙江省绍兴市第一中学字符串游戏 3 梁盾湖南省长沙市长郡中学字符串加密 4 艾雨青湖南省长沙市雅礼中学近似平均数 5 刘洪轩天津市南开中学电子对撞机 6 顾昱洲江苏省南京师范大学附属中学 JZPLCM 7 沈添笑湖南省长沙市雅礼中学生日蜡烛 8 卓亮福建省福州第一中学 Flare 9 王钦石黑龙江省哈尔滨市第三中学校能量棒 10 陈立杰浙江省杭州外国语学校 Color 11 伍一鸣湖南省长沙市雅礼中学 Binomial 12 钟沛林湖南省长沙市雅礼中学可见区域

拆弹计划拆弹计划命题人 : 李超资源限制时间限制 :3 秒内存限制 :512MB 关键字序的应用, 分治, 线段树问题描述 A 国和 B 国是两个超级大国, 长期处于冷战状态 A 国在 B 国中设有 N 个情报站, 编号为 1,2,3,,N, 第 i 个情报站的坐标是 (X i, Y i ) 但是,A 国的工作人员发现, 每个情报站里都被埋上了炸弹! 这些炸弹非常的特殊, 必须同时拆除且仅拆除其中的三个炸弹, 才能使所有炸弹都不爆炸拆除炸弹的总代价由两部分组成, 第一部分为情报站之间联络的代价, 第二部分为拆除炸弹所需要的代价其中, 联络的代价为要拆除炸弹的三个情报站的坐标的曼哈顿距离和, 在第 i 个情报站拆除炸弹的代价为 Z i 现在 A 国的指挥部门找到了你, 他想要知道, 使所有炸弹都不爆炸的最小花费代价是多少输入格式输入的第一行包含一个整数 N 接下来 N 行, 第 i+1 行有三个整数 X i, Y i, Z i, 表示第 i 个情报站的坐标与拆除炸弹的代价输出格式输出一行, 包含一个整数, 表示使所有炸弹都不爆炸的最小花费代价样例输入 4 1 1 1 1 2 2 2 1 3 2 3 4 第 3 页共 24 页

拆弹计划样例输出 10 样例解释选择编号为 1,2,3 的情报站拆除炸弹, 总花费为 (1+1+2)+(1+2+3)=10, 是所有花费中总花费最小的该数据中只有这一种选法数据规模与约定对于 30% 的数据,N 500 对于 50% 的数据,N 1000 对于 70% 的数据,N 15000 另有 10% 的数据, 在所有情报站拆除炸弹的花费代价均相同 ; 对于 100% 的数据,N 100000,0 X i, Y i, Z i 10 8 说明对于两个点 (X 0, Y 0 ), (X 1, Y 1 ), 它们的曼哈顿距离为 X 0 X 1 + Y 0 Y 1 第 4 页共 24 页

字符串游戏字符串游戏命题人 : 徐捷问题描述给定 N 个仅有 a ~ z 组成的字符串 a i, 每个字符串都有一个权值 v i, 有 M 次操作, 操作分三种 : Cv x v': 把第 x 个字符串的权值修改为 v'; Cs x a': 把第 x 个字符串修改成 a'; Q: 求出当前的最大权字符串集合, 使得这个集合中的字符串经过重新排列后满足除最后一个字符串外, 前一个字符串是后一个的前缀 ( 两个字符串相同也是前缀关系, 也可以一个字符串都不选 ) 前 50% 的数据可以接受离线算法, 后 50% 的数据要求在线算法数据规模与约定数据分两种,A 类数据可以用离线的方法来完成,B 类数据必须使用在线算法令 len= 输入数据中所有出现的字符串总长度编号数据类别数据范围 1 N, M 30, len 500 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 A B N, M 1000, len 10000 N 50000, M 10 5, len 2 10 6 N 50000, M 10 5, len 2 10 6 20 第 5 页共 24 页

字符串加密字符串加密命题人 : 梁盾问题描述 H 国开发了一种新的字符串的加密方式, 具体方法为将一个长度为 N 的由小写字母组成的字符串分成不超过 K 段, 分别将每一段翻转, 得到的新字符串即为加密以后的字符串 H 国为 I 国的敌国,I 国为了打败 H 国, 得到了一个加密以后的信息, 我们想知道这个字符串在加密以前的样子, 不过可能有多个答案, 我们只要知道字典序最小的答案就可以了输入格式第一行一个数 T, 表示数据组数对于每组数据, 第一行两个数 N, K 分别表示字符串的长度和被分成了 K 段第二行一个长度为 N 的字符串输出格式对于每组数据, 输出一个长度为 N 的字符串, 即加密前的可能的字典序最小的字符串样例输入 1 1 3 bacbadcba 样例输出 ababcabcd 第 6 页共 24 页

字符串加密数据规模与约定测试点编号数据组数 T 字符串长度 N 的规模分裂段数 K 的规模 1 ~ 2 1 N 300 3 ~ 6 1 N 2000 1 K 3 7 ~ 10 11 T 10 K = 1 12 1 N 100000 K = 2 13 ~ 16 1 K 100 17 ~ 20 1 K N 第 7 页共 24 页

近似平均数近似平均数命题人 : 艾雨青问题描述 Xi i 1 定义 N 个数 X1, X 2,..., X n( n 1) 的近似平均数为 n 1 对于给出的长度为 N 的一个序列 A, 要求回答 Q 个询问每个询问会给出 L, R(1 L R N), 请找出 a 与 b ( L a b R) 使得 n Aa, Aa 1,..., Ab 的近似平均数最大输入格式第一行两个正整数 N, Q 第二行 N 个数表示序列 S 接下来 Q 行, 每行两个数 L, R 输出格式对于每个询问回答一行, 用一个既约分数表示最大的几乎平均数若答案为整数 x, 输出 x/1 样例输入 3 2-2 -1-2 1 2 1 3 样例输出 -3/1-5/2 第 8 页共 24 页

近似平均数数据规模与约定对于所有数据 S i <=10 6 TEST N Q TEST N Q 1 =10 =10 11 =3*10^4 =10^4 2 =100 =100 12 =4*10^4 =10^4 3 =1000 =1000 13 =5*10^4 =10^4 4 =2000 =2000 14 =6*10^4 =2*10^4 5 =5000 =5000 15 =7*10^4 =2*10^4 6 =10^4 =5000 16 =8*10^4 =3*10^4 7 =10^4 =10^4 17 =9*10^4 =3*10^4 8 =2*10^4 =5000 18 =10^5 =10 9 =2*10^4 =10^4 19 =10^5 =3*10^4 10 =3*10^4 =5000 20 =10^5 =3*10^4 第 9 页共 24 页

电子对撞机电子对撞机命题人 : 刘洪轩资源限制时间限制 :3 秒内存限制 :256MB 问题描述 Q 国最近科学技术不断进步, 经过不懈努力,Q 国主席 QQ 终于在质子对撞机的基础上研发了新一代能量供给装置 : 电子对撞机这个设备呈长条状且对外封闭, 设备内部有 N 个带有一定能量的电子长条状的外形使得这些电子只能沿条形走向左右运动设备长度为 L, 左端位置为 0, 右端位置为 L 内部的电子速率恒定, 每一个单位时间在左右方向上移动一个单位长度, 而方向可能是向左或向右当两个电子相遇即运动到同一个点时, 它们之间会发生对撞, 对撞后它们的速率不变但运动方向反向设备的两个端点处 ( 即坐标为 0 和 L 的位置 ) 存在保护外壳, 当电子运动到端点时会和外壳发生碰撞, 碰撞后电子也会保持不变的速率但运动方向反向电子分为高能电子和低能电子, 电子之间对撞会产生能量, 低能电子和低能电子对撞会产生 1 个单位的能量, 低能电子和高能电子对撞会产生 4 个单位的能量, 高能电子和高能电子对撞会产生 25 个单位的能量, 电子和外壳碰撞不会产生能量设备内部还有 M 个能量接收器, 每个接收器可以接受从 A 到 B 的一个区间内 ( 包括两个端点 ) 的能量, 且接收器可以接受的范围没有交集若电子对撞的位置处于接收器的接受范围内, 对撞产生的能量会被接收器接受, 若对撞位置不在接收器上, 这些能量则会丢失这项技术的核心在于 : 对撞时电子的能量不会有损失, 所以电子对撞机可以一直不断地运行下去供给能量现在 QQ 已经制造出了第一批电子对撞机, 并测得了时刻为 0 时电子的位置和运动状态, 现在 QQ 想知道从时刻 0 到时刻 T( 包括 T) 总共接收到的能量, 于是这个任务交给了神犇你输入格式第一行四个整数 N, M, L, T, 分别表示电子个数, 能量接收器个数, 设备长度和时间之后 N 行每行 3 个整数,X i, P i, E i 分别表示第 i 个电子的位置, 运动方向和能量级别 P i 为 1 表示向右运动, 为 -1 表示向左运动 E i 为 0 表示低能电子, 为 1 表示高能电子之后 M 行每行 2 个整数,A i 和 B i, 表示接收器的接收范围输出格式仅一行, 包括一个整数, 表示总共接收到的能量数第 10 页共 24 页

电子对撞机样例输入 3 1 8 7 2 1 0 4-1 0 7 1 1 3 6 样例输出 5 样例说明 T=1 时, 在位置 3, 第一个电子和第二个电子对撞, 产生 1 的能量在位置 8, 第三个电子和右侧外壳碰撞 T=3.5 时, 在位置 5.5, 第二个电子和第三个电子对撞, 产生 4 的能量 T=4 时, 在位置 0, 第一个电子和左侧外壳碰撞 T=6 时, 在位置 8, 第三个电子和右侧外壳碰撞 T=6.5 时, 在位置 2.5, 第一个电子和第二个电子对撞, 产生 1 的能量, 由于在接收器范围外, 能量丢失最后结果为 1+4=5 个单位能量数据规模与约定输入保证开始时任意两个电子不处于同一个位置输入保证接收器的接受范围没有交集, 且所有接收器按坐标从小到大的顺序给出共 20 组数据, 满足如下条件 1 ~ 2 N <= 10 M <= 3 L <= 1000, T <= 100000 3 ~ 4 N <= 100 Ei = 0 L <= 1000000 5 ~ 6 N <= 1000 7 ~ 8 M = 1 且 9 ~ 10 N <= 100000 11~12 13~20 A1 = 0, B1 = L 2 <= N <= 1000000, 1 <= M <= 10, 2 <= L <= 100000000, 0 <= T <= 1000000000, 0 < X < L 0 <= A < B <= L 第 11 页共 24 页

JZPLCM JZPLCM 命题人 : 顾昱洲资源限制时间限制 :3 秒内存限制 : 以硬件资源为限问题描述给定一长度为 n 的正整数序列 a, 有 q 次询问, 每次询问一段区间内所有数的 lcm( 即最小公倍数 ) 由于答案可能很大, 输出答案模 1000000007 输入格式第一行, 两个整数,n, q, 分别表示数列长度和询问个数下面 n 行, 每行一个整数, 第 i 行的整数为 a i 下面 q 行, 每行两个整数 l, r, 表示询问下标 i 在 [l, r] 范围内的 a i 的 lcm 输出格式 q 行对于每个询问, 输出一行, 表示对应的答案样例输入 3 3 123 234 345 1 2 2 3 1 3 样例输出 9594 26910 1103310 第 12 页共 24 页

JZPLCM 数据规模与约定测试数据编号规模和约定 1, 2 n, q<=1000 3, 4 n, q<=5000 5, 6 n, q<=20000 7, 8 n, q<=30000 9, 10 n, q<=40000 11, 12 n, q<=50000 13, 14 n, q<=80000 15, 16 n, q<=100000 17, 18, 19, 20 n, q<=100000 数列 a 中每个数能表示为不超过 100 的素数的积对于所有测试点, 数列 a 中每个数满足 1<=ai<=1000000000 第 13 页共 24 页

生日蜡烛生日蜡烛命题人 : 沈添笑资源限制时间限制 :2 秒空间限制 :256M 问题描述小 A 的生日到了! 生日派对上, 大家送上了一份精心准备的大礼 : 生日蛋糕! 蛋糕上五颜六色的蜡烛闪闪发光随风摇曳小 A 很喜欢这个漂亮的蛋糕, 然而, 在吹蜡烛许愿的时候, 他却犯难了 : 烛火怎么也吹不灭! 原来, 这是大家要考考小 A 这份特制的蛋糕上共有 n 根蜡烛, 编号为 1~n, 相应的, 有 n 个开关, 第 i 根蜡烛由第 i 个开关控制此外, 第 i 根蜡烛还可能由至多一个其他的开关 j 控制, 当 i=1 时,j 可以是 2 ~ n 中的任意一个数, 当 i > 1 时,j < i 按下一个开关, 它所控制的蜡烛的状态就会发生改变 : 由亮变暗或由暗变亮小 A 知道每根蜡烛此时是亮是暗, 以及它由哪些开关控制, 他希望尽量少地按开关, 使所有的蜡烛熄灭不过, 参加聚会的 m 个同学并不打算就这样放过可怜的小 A, 他们会依次改变某个蜡烛的状态以及控制它的开关, 并询问小 A 此时最少要按多少次开关快来帮帮小 A 吧, 他会亲手切下第一块生日蛋糕送给你的! 输入格式第一行为一个正整数 n, 表示蜡烛和开关的个数接下来 n 行, 第 i 行描述第 i 根蜡烛每行包含两个整数, 第一个数 a i 为 0( 暗 ) 或 1( 亮 ), 代表蜡烛的状态, 第二个数 b i 为控制第 i 根蜡烛的另一个开关,b i =0 时表示第 i 根蜡烛只由第 i 个开关控制接下来一行为一个正整数 m, 表示参加派对的人数接下来 m 行, 每行包含三个整数 u v w, 代表第 u 根蜡烛的状态变为 v, 控制它的另一个开关变为 w 输出格式输出应有 m 行, 第 i 行一个整数 time i, 表示经过前 i 次修改后, 此时最少需按多少次开关, 才能使所有蜡烛熄灭若是无论如何都不能使所有蜡烛熄灭, 输出 -1 第 14 页共 24 页

生日蜡烛样例输入 4 1 3 1 0 0 1 1 2 3 1 0 3 4 1 3 3 0 2 样例输出 1 2 3 数据规模与约定 10% 的数据满足 :n m 10 20% 的数据满足 :n m 1000 另有 20% 的数据满足 : 控制蜡烛的开关不会更改, 即 w=b u, 且 b i =(i+n-2)%n+1 另有 30% 的数据满足 : 控制蜡烛的开关不会更改 100% 的数据满足 :n m 100000 第 15 页共 24 页

Flare Flare 命题人 : 卓亮问题描述这是一个很有趣的想法, 如果熊是蜜蜂, 他们会将他们的巢建在树下而且如此的话 ( 如果蜜蜂是熊 ), 我们就不用爬上楼梯了这是小熊维尼的一首充满抱怨的歌你是否曾经想过, 有些关于无向图的问题, 如果把边看成点, 点看成边, 会更容易解决? 这道题目正与此有关假设有一张无向图 G 0, 让我们对 G 0 执行一次简单变换, 来得到无向图 G 1 G 1 满足, 每个 G 1 的顶点和 G 0 的一条边一一对应,G 1 的一对顶点间有一条边, 当且仅当在 G 0 中的对应边有一个公共顶点可能与你猜测的不一样, 本题给出了 G 1, 求一个满足条件的 G 0 输入格式输入的第一行含两个数 n, m, 代表点数和边数接下来 m 行, 每行有两个数 a, b (1 <= a, b <= n), 表示 a, b 间有一条边保证每条边连接了两个不同的顶点, 每对顶点最多有一条边相连输出格式如果这样的 G 0 不存在, 输出 -1 否则, 输出 n 行, 每行两个数, 代表 G 0 的一条边的两个顶点 G 0 的第 i 条边对应于 G 1 的顶点 i 输出需要满足, 每条边连接了不同的顶点, 每对顶点间至多只有一条边你可以自行给顶点标号, 但顶点的标号需要是正整数, 而且不应超过 10^9 样例输入 3 3 1 2 1 3 2 3 样例输出 1 2 1 3 2 3 第 16 页共 24 页

Flare 提示样例的图是三角形 ( 三个点, 两两间均有边 ) 容易看到三角形简单变换后仍是三角形当然, 样例的解并不唯一数据规模与约定对 10% 的数据,1<= n <= 10 对 20% 的数据,1<= n <= 15 对 30% 的数据,1<= n <= 20 另有 5% 数据, 图为一条链 ;5% 的数据, 图为一个环 ;5% 的数据, 图为完全图 ;5% 的数据, 图的每个连通块为上述三种情形之一对 70% 的数据,1<= n <= 10^3 对 100% 的数据,1<= n;m <= 10^6 第 17 页共 24 页

能量棒能量棒命题人 : 王钦石关键字动态规划二分单调性问题描述小 W 是一个杰出的登山家一天, 他独自挑战一座神秘的山峰, 也许是受到了诅咒, 他不小心将背包掉落山崖他摸了摸口袋, 发现只剩下一根能量棒能量棒被分为 N 个格子, 每个格子上有一个正整数 A i, 作为一个登山家, 小 W 清楚他应该把能量棒分割成恰好 K 段使用, 且必须全部用完他也清楚使用一段 A 值和为 x 的能量棒可以获得 x 2 +B x + C 个单位的能量不过小 W 数学不好, 他不知道应该如何分割能量棒以获得最多的能量, 请你帮助小 W 解决这个问题输入格式第一行一个整数 T, 表示此测试点包含测试数据的组数 ; 每个测试数据包含两行 : 第一行四个整数 N, K, B, C, 用空格隔开, 如题目描述中所述 ; 第二行用空格隔开的 N 个整数, 分别表示每个格子的 A i 输出格式对于每个测试数据一行, 表示这个测试数据中最多所能获得的能量样例输入 2 3 2 3 2 1 2 3 3 2 3 2 2 3 1 样例输出 4 2 第 18 页共 24 页

能量棒数据规模与约定测试点编号 T N K 其他约定 1 <=10 <=2 2-4 <=100 <=100 1 5-8 <=5000 <=5000 9-10 <=100000 <=100 A 数列是某一 [1,v] 范围内等概率随机生成的 11-20 3 <=100000 <=100000 无对于全部的测试数据,1<=K<=N,ΣA i <=1.1 10 9, B, C <=10 9 第 19 页共 24 页

Color Color 命题人 : 陈立杰资源限制时间限制 :1 秒内存限制 :256MB 问题描述有 n 个球排成一行, 每个球有它的颜色, 我们每次随机取出两个球 a, b, 给 b 染上 a 的颜色, 求期望操作多少次可能使得所有的球颜色相同? 显然答案只跟每种颜色有几个球有关系, 我们只要给出每个颜色的球数量即可输出跟答案相对误差在 10-9 以内就算做正确输入格式第一行一个数 c 表示有 c 种颜色接下来 c 行给出一个颜色球数输出格式一行一个数表示答案数据规模与约定 10% n 5; 30% n 20; 40% n 25; 50% n 40; 80% n 10000; 100% n 10 10, c 10000 第 20 页共 24 页

Binomial Binomial 命题人 : 伍一鸣问题描述给定 n 和 p, 对于所有的 0 x < p x N, 求满足个数, 输出答案在 29 进制下的最后一位的 m 的输入格式仅一行包含两个正整数 n 和 p 输出格式仅一行, 为一个长度为 p 的字符串 s,s i 表示的 m 的个数除以 29 后的余数,s i 视为一个 29 进制的数字样例输入 20 4 样例输出 D440 数据规模与约定 5% 的数据 :n < 2000; 30% 的数据 :n < 10 8 ; 50% 的数据 :n < p 5, p 5000; 85% 的数据 :n < p 5, p 2 16 ; 100% 的数据 :n < p 10, p 2 16 (p 为质数 ) 第 21 页共 24 页

可见区域可见区域命题人 : 钟沛林问题描述在平面直角坐标系中有 n 条互不相交 ( 没有公共点 ) 且所在直线不会经过 (0,0) 的线段有一个人站在 (0,0), 他的视野是 360 度的但是他在某一个方向上的视野会被该方向上碰到的第一条线段所阻挡, 问他能看到的区域面积有多大 ( 数据保证是有限面积 ) 如下图 ( 样例 ), 可以看到的面积就是 11 为了加大难度, 他想知道, 在删除一条线段的情况下能看到最大多大的面积 ( 不保证是有限面积 ) 进一步, 他还想知道, 在删除两条线段的情况下能看到最大多大的面积 ( 不保证是有限面积 ) 输入格式第一行一个整数 n 表示线段条数接下来 n 行, 每行四个整数 x 1, y 1, x 2, y 2 表示一条线段两个端点的坐标输出格式第一行一个保留两位小数的实数, 表示可见区域的面积第二行两种可能, 如果删除一条线段以后能使得看到的区域有无限大输出 infinite, 否则输出一个保留两位小数的实数, 表示这种情况下能看到的最大面积第三行两种可能, 如果删除两条线段以后能使得看到的区域有无限大输出 infinite, 否则输出一个保留两位小数的实数, 表示这种情况下能看到的最大面积第 22 页共 24 页

可见区域样例输入 6-1 -1 0-1 0-2 1-1 -1 1 0 2 0 1 1 1 2-2 2 2-2 -2-2 2 样例输出 11.00 infinite infinite 数据规模与约定对于所有数据 1 <= n <= 50000 坐标的绝对值 <=10 3 area1.in 4-1 2 4 2 2 1 2-4 1-2 -4-2 -2-1 -2 4 area2.in 8-1 2 4 2 2 1 2-4 1-2 -4-2 -2-1 -2 4-3 6 12 6 6 3 6-12 3-6 -12-6 -6-3 -6 12 area3.in 12-1 2 4 2 2 1 2-4 1-2 -4-2 -2-1 -2 4-3 6 12 6 6 3 6-12 3-6 -12-6 -6-3 -6 12-9 18 36 18 第 23 页共 24 页

可见区域 18 9 18-36 9-18 -36-18 -18-9 -18 36 area4.in n<=10, 坐标的绝对值 <=10 删除某条线段后可看到无限区域 area5.in n<=1000 删除某条线段后可看到无限区域 area6.in n<=1000 删除某条线段后可看到无限区域 area7.in n<=50000 删除某条线段后可看到无限区域 area8.in n<=50000 删除某条线段后可看到无限区域 area9.in n<=50000 删除某条线段后可看到无限区域 area10.in n<=50000 删除某条线段后可看到无限区域 area11.in n<=200 删除两条线段后能看到无限区域 area12.in n<=1000 删除两条线段后能看到无限区域 area13.in n<=1000 删除两条线段后能看到无限区域 area14.in n<=50000 删除两条线段后能看到无限区域 area15.in n<=50000 删除两条线段后能看到无限区域 area16.in n<=50 area17.in n<=300 area18.in n<=50000 area19.in n<=50000 area20.in n<=50000 第 24 页共 24 页