tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 学科竞赛 >>

apio2015


2015 亚太地区信息学奥林匹克竞赛

APIO2015
竞赛时间:2015 年 5 月 9 日 9:00-14:00
题目名称 英文名称 每个测试点时限 内存限制 试题总分 巴厘岛的雕塑 sculpture 1秒 64 MB 100 雅加达的摩天楼 skyscraper 1秒 256MB 100 巴邻旁之桥 bridge 2秒 256 MB 100

2015 亚太地区信息学奥林匹克竞赛

巴厘岛的雕塑

巴厘岛的雕塑
【问题描述】 印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。 在这条主干道上一共有座雕塑,为方便起见,我们把这些雕塑从 1 到连 续地进行标号,其中第 座雕塑的年龄是 年。为了使这条路的环境更加优美, 政府想把这些雕塑分成若干组,并通过在组与组之间种上一些树,来吸引更多的 游客来巴厘岛。 下面是将雕塑分组的规则: 这些雕塑必须被分为恰好组,其中 ≤ ≤ ,每组必须含有至少一个雕 塑, 每个雕塑也必须属于且只属于一个组。同一组中的所有雕塑必须位于这条路 的连续一段上。 当雕塑被分好组后,对于每个组,我们首先计算出该组所有雕塑的年龄和, 然后计算将每组年龄和按位取或(即对上述年龄和按位取或) ,我们把按位取或 后得到的结果称为这一分组的最终优美度(颜值) 。 请问政府能得到的最小的最终优美度(颜值)是多少? 备注: 将两个非负数和 按位取或是这样进行计算的: 首先把 和 转换成二进制:设 是 的二进制位数, 是 的二进制位 数,为和 中的最大值。 的二进制表示为?1 , ?2 , … , 1 , 0 , 的二进 制表示为?1 , ?2 , … , 1 , 0 ,其中 和 分别是和 二进制表示下的第 位, 第 ? 1位是数的最高位,第 0 位是数的最低位。 与 按位取或后的结果是:(?1或?1 )(?2或?2 )…(1或1 )(0 或0 )。 其中: 0 或 0=0 0 或 1=1 1 或 0=1 1 或 1=1 【输入格式】 输入的第一行包含三个用空格分开的整数, 和。 第二行包含 个用空格分开的整数1 , 2 , … , 。 【输出格式】 输出一行一个数,表示最小的最终优美度。 【样例输入】 6 1 3 8 1 2 1 5 4

第2页

共8页

2015 亚太地区信息学奥林匹克竞赛

巴厘岛的雕塑

【样例输出】 11 【样例解释】 将这些雕塑分为 2 组,(8, 1, 2) 和 (1, 5, 4),它们的和是(11)和(10),最终优 美度是(11 或 10) = 11 。 (不难验证,这也是最终优美度的最小值。 ) 【数据规模和约定】 共有五部分数据(或称 5 个子任务) 。 第 1 部分数据占 9 分, 数据范围满足: 1 ≤ ≤ 20, 1 ≤ ≤ ≤ , 0 ≤ ≤ 1,000,000,000; 第 2 部分数据占 16 分, 数据范围满足: 1 ≤ ≤ 50, 1 ≤ ≤ ≤ min(20, ), 0 ≤ ≤ 10; 第 3 部分 数 据 占 21 分 ,数 据 范围 满足: 1 ≤ ≤ 100 , 1 ≤ ≤ ≤ min(20, ),0 ≤ ≤ 20; 第 4 部分数据占 25 分,数据范围满足:1 ≤ ≤ 100,1 ≤ ≤ ≤ ,0 ≤ ≤ 1,000,000,000; 第 5 部分数据占 29 分, 数据范围满足: 1 ≤ ≤ 2000, = 1, 1 ≤ ≤ , 0 ≤ ≤ 1,000,000,000。

第3页

共8页

2015 亚太地区信息学奥林匹克竞赛

雅加达的摩天楼

雅加达的摩天楼
【问题描述】 印尼首都雅加达市有座摩天楼,它们排列成一条直线,我们从左到右依次 将它们编号为 0 到 ? 1。除了这座摩天楼外,雅加达市没有其他摩天楼。 有只叫做 “doge” 的神秘生物在雅加达市居住, 它们的编号依次是 0 到 ? 1。编号为 的 doge 最初居住于编号为 的摩天楼。每只 doge 都有一种神秘的力 量,使它们能够在摩天楼之间跳跃,编号为 的 doge 的跳跃能力为 ( > 0) 。 在一次跳跃中,位于摩天楼而跳跃能力为的 doge 可以跳跃到编号为 ? (如 果0 ≤ ? < )或 + (如果 0 ≤ + < )的摩天楼。 编号为 0 的 doge 是所有 doge 的首领, 它有一条紧急的消息要尽快传送给编 号为 1 的 doge。任何一个收到消息的 doge 有以下两个选择: 1. 跳跃到其他摩天楼上; 2. 将消息传递给它当前所在的摩天楼上的其他 doge。 请帮助 doge 们计算将消息从 0 号 doge 传递到 1 号 doge 所需要的最少总跳 跃步数,或者告诉它们消息永远不可能传递到 1 号 doge。 【输入格式】 输入的第一行包含两个整数和, 接下来行, 每行包含两个整数 和 。 【输出格式】 输出一行,表示所需要的最少步数。如果消息永远无法传递到 1 号 doge, 输出?1。 【样例输入】 5 0 1 4 3 2 1 1

【样例输出】 5 【样例解释】 下面是一种步数为 5 的解决方案: 0 号 doge 跳跃到 2 号摩天楼,再跳跃到 4 号摩天楼(2 步) 。 0 号 doge 将消息传递给 2 号 doge。 2 号 doge 跳跃到 3 号摩天楼,接着跳跃到 2 号摩天楼,再跳跃到 1 号摩天
第4页 共8页

2015 亚太地区信息学奥林匹克竞赛

雅加达的摩天楼

楼(3 步) 。 2 号 doge 将消息传递给 1 号 doge。 【数据规模和约定】 共有五部分数据(或称 5 个子任务) 。所有数据都保证0 ≤ < 。 第 1 部分数据占 10 分, 数据范围满足: 1 ≤ ≤ 10, 1 ≤ ≤ 10, 2 ≤ ≤ 3; 第 2 部分数据占 12 分, 数据范围满足: 1 ≤ ≤ 100, 1 ≤ ≤ 100, 2 ≤ ≤ 2000; 第 3 部分数据占 14 分, 数据范围满足:1 ≤ ≤ 2000, 1 ≤ ≤ 2000,2 ≤ ≤ 2000; 第 4 部分数据占 21 分, 数据范围满足:1 ≤ ≤ 2000, 1 ≤ ≤ 2000,2 ≤ ≤ 30000; 第 5 部分数据占 43 分,数据范围满足:1 ≤ ≤ 30000,1 ≤ ≤ 30000, 2 ≤ ≤ 30000。

第5页

共8页

2015 亚太地区信息学奥林匹克竞赛

巴邻旁之桥

巴邻旁之桥
【问题描述】 一条东西走向的穆西河将巴邻旁市一分为二,分割成了区域和区域。 每一块区域沿着河岸都建了恰好 1,000,000,001 栋的建筑,每条岸边的建筑 都从 0 编号到 1,000,000,000。 相邻的每对建筑相隔 1 个单位距离, 河的宽度也是 1 个单位长度。区域中的 号建筑物恰好与区域中的 号建筑物隔河相对。 城市中有个居民。第 个居民的房子在区域 的 号建筑上,同时他的办公 室坐落在 区域的 号建筑上。一个居民的房子和办公室可能分布在河的两岸, 这样他就必须要搭乘船只才能从家中去往办公室, 这种情况让很多人都觉得不方 便。为了使居民们可以开车去工作,政府决定建造不超过 座横跨河流的大桥。 由于技术上的原因, 每一座桥必须刚好连接河的两岸, 桥梁必须严格垂直于河流, 并且桥与桥之间不能相交。 当政府建造最多 座桥之后, 设 表示第 个居民此时开车从家里到办公室的 最短距离。请帮助政府建造桥梁,使得1 + 2 + ? + 最小。 【输入格式】 输入的第一行包含两个正整数 和, 分别表示桥的上限数量和居民的数量。 接下来 行,每一行包含四个参数: , , 和 ,表示第 个居民的房子在 区域 的 号建筑上,且他的办公室位于 区域的 号建筑上。 【输出格式】 输出仅为一行,包含一个整数,表示1 + 2 + ? + 的最小值。 【样例输入 1】 1 B B A B B 5 0 1 5 2 1

A B B A A

4 3 7 6 7

【样例输出 1】 24 【样例输入 2】 2 B B A 5 0 A 4 1 B 3 5 B 7
第6页 共8页

2015 亚太地区信息学奥林匹克竞赛

巴邻旁之桥

B 2 A 6 B 1 A 7 【样例输出 2】 22 【样例说明】 下图是两个样例输入的图示说明:

下面是样例 1 可能的一组最优方案,粉色的区域表示一座桥。

下面是样例 2 的一组可能的最优方案。

第7页

共8页

2015 亚太地区信息学奥林匹克竞赛

巴邻旁之桥

【数据规模和约定】 共有五部分数据(或称 5 个子任务) 。 所 有 数 据 都 保 证 : 0 ≤ Si , Ti ≤ 1,000,000,000, 和 为字符 A 和 B 中的一个, 同一栋建筑内可能有超过 1 间房 子或办公室(或二者的组合,即房子或办公室同时大于等于 1) 。 第 1 部分数据占 8 分,数据范围满足:K = 1,1 ≤ ≤ 1000; 第 2 部分数据占 14 分,数据范围满足:K = 1,1 ≤ ≤ 100000; 第 3 部分数据占 9 分,数据范围满足:K = 2,1 ≤ ≤ 100; 第 4 部分数据占 32 分,数据范围满足:K = 2,1 ≤ ≤ 1000; 第 5 部分数据占 37 分,数据范围满足:K = 2,1 ≤ ≤ 100000。

第8页

共8页


推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com