当前位置:首页 >> 学科竞赛 >>

NOIP2013提高组复赛试题


全国信息学奥林匹克联赛(NOIP2013)复赛

提高组 day2

CCF

全国信息学奥林匹克联赛(NOIP2013)复 赛

提高组 day1
1.转圈游戏 (circle.cpp/c/pas) 【问题描述】 n 个小伙伴(编号从 0 到 n-1)围坐一圈玩游戏。按照顺时针方向给 n

个位置编号,从 0 到 n-1。 最初, 第 0 号小伙伴在第 0 号位置, 第 1 号小伙伴在第 1 号位置, ……, 依此类推。 游戏规则如下:每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置,第 1 号位置小伙 伴走到第 m+1 号位置,……,依此类推,第 n ? m 号位置上的小伙伴走到第 0 号位置,第 n-m+1 号位置上的小伙伴走到第 1 号位置,……,第 n-1 号位置上的小伙伴顺时针走到第 m-1 号位 置。 现在,一共进行了 10^k 轮,请问 x 号小伙伴最后走到了第几号位置。 【输入】 输入文件名为 circle.in。 输入共 1 行,包含 4 个整数 n、m、k、x,每两个整数之间用一个空格隔开。 【输出】 输出文件名为 circle.out。 输出共 1 行,包含 1 个整数,表示 10k 轮后 x 号小伙伴所在的位置编号。

【输入输出样例】 circle.in 10 345

circle.out 5

【数据说明】 对于 30%的数据,0 <k < 7; 对于 80%的数据,0 <k < 107; 对于 100%的数据,1 <n< 1,000,000,0 <m<n,0 ≤ x ≤ n,0 <k< 109。

第 1 页共 5 页

全国信息学奥林匹克联赛(NOIP2013)复赛

提高组 day2

2.火柴排队 (match.cpp/c/pas) 【问题描述】 涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。现在将每盒中的火柴各自 排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为: 表示第一列火柴中第 i 个火柴的高度,bi 表示第二列火柴中第 i 个火柴的高度。 每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。 请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个最小交换次数 对 99,999,997 取模的结果。 【输入】 输入文件为 match.in。 共三行,第一行包含一个整数 n,表示每盒中火柴的数目。 第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。 第三行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。 【输出】 输出文件为 match.out。 输出共一行,包含一个整数,表示最少交换次数对 99,999,997 取模的结果。 【输入输出样例 1】 match.in 4 2314 3214 match.out 1 ,其中 ai

【输入输出样例说明】 最小距离是 0, 最少需要交换 1 次, 比如: 交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根 火柴。 【输入输出样例 2】 match.in 4 1342 1724 【输入输出样例说明】 最小距离是 10,最少需要交换 2 次,比如:交换第 1 列的中间 2 根火柴的位置,再交 换第 2 列中后 2 根火柴的位置。 【数据范围】 对于 10%的数据, 1 ≤ n ≤ 10; 对于 30%的数据,1 ≤ n ≤ 100; 对于 60%的数据,1 ≤ n ≤ 1,000;
第 2 页共 5 页

match.out 2

全国信息学奥林匹克联赛(NOIP2013)复赛

提高组 day2

对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤火柴高度≤ 231 ? 1。

3.货车运输 (truck.cpp/c/pas) 【问题描述】 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有 重量限制,简称限重。现在有 q 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的 情况下,最多能运多重的货物。 【输入】 输入文件名为 truck.in。 输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道路。 接下来 m 行每行 3 个整数 x、 y、 z, 每两个整数之间用一个空格隔开, 表示从 x 号城市到 y 号 城市有一条限重为 z 的道路。注意:x 不等于 y,两座城市之间可能有多条道路。 接下来一行有一个整数 q,表示有 q 辆货车需要运货。 接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货 物到 y 城市,注意:x 不等于 y。 【输出】 输出文件名为 truck.out。 输出共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货车不能 到达目的地,输出-1。

【输入输出样例】 truck.in 4 1 2 3 3 1 1 1 3 24 33 11 3 4 3

truck.out 3 -1 3

第 3 页共 5 页

全国信息学奥林匹克联赛(NOIP2013)复赛

提高组 day2

【数据说明】 对于 30%的数据,0 <n< 1,000,0 <m< 10,000,0 <q< 1,000; 对于 60%的数据,0 <n< 1,000,0 <m< 50,000,0 <q< 1,000; 对于 100%的数据,0 <n< 10,000,0 <m< 50,000,0 <q< 30,000,0 ≤ z ≤ 100,000。

CCF

全国信息学奥林匹克联赛(NOIP2013)复赛
1.积木大赛 (block.cpp/c/pas)

【题目描述】 春春幼儿园举办了一年一度的“积木大赛” 。今年比赛的内容是搭建一座宽度为 n 的大厦,大 厦可以看成由 n 块宽度为 1 的积木组成,第 i 块积木的最终高度需要是 ?i。 在搭建开始之前,没有任何积木(可以看成块高度为 0 的积木) 。接下来每次操作,小朋友 们可以选择一段连续区间[L,R],然后将第 L 块到第 R 块之间(含第 L 块和第 R 块)所有积木 的高度分别增加 1。 小 M 是个聪明的小朋友, 她很快想出了建造大厦的最佳策略, 使得建造所需的操作次数最少。 但她不是一个勤于动手的孩子,所以想请你帮忙实现这个策略,并求出最少的操作次数。 【输入】 输入文件为 block.in 输入包含两行,第一行包含一个整数 n,表示大厦的宽度。 第二行包含 n 个整数,第 i 个整数为 ?i。 【输出】 输出文件为 block.out 仅一行,即建造所需的最少操作数。 【输入输出样例】 block.in

block.out

第 4 页共 5 页

全国信息学奥林匹克联赛(NOIP2013)复赛

提高组 day2

5 2 3 4 12

5

【样例解释】 其中一种可行的最佳方案,依次选择 [1,5] [1,3] [2,3] [3,3] [5,5] 【数据范围】 对于 30%的数据,有 1 ≤ n ≤ 10; 对于 70%的数据,有 1 ≤ n ≤ 1000; 对于 100%的数据,有 1 ≤ n ≤ 100000,0 ≤ hi ≤ 10000。

2.花匠 (flower.cpp/c/pas) 【问题描述】 花匠栋栋种了一排花,每株花都有自己的高度。花儿越长越大,也越来越挤。栋栋决定把这 排中的一部分花移走,将剩下的留在原地,使得剩下的花能有空间长大,同时,栋栋希望剩下的 花排列得比较别致。 具体而言,栋栋的花的高度可以看成一列整数 ?1, ?2, … , ?n。设当一部分花被移走后, 剩下的花的高度依次为 g1, g2, … , gm,则栋栋希望下面两个条件中至少有一个满足:
m ,有 g2i>g2i+1; 2 2 m m 条件 B:对于所有的 1≤i≤ ,有 g2i<g2i-1,同时对于所有的 1≤i≤ ,有 g2i<g2i+1。 2 2

条件 A:对于所有的 1≤i≤

m

,有 g2i>g2i-1,同时对于所有的 1≤i≤

注意上面两个条件在 m = 1 时同时满足,当 m > 1 时最多有一个能满足。 请问,栋栋最多能将多少株花留在原地。 【输入】 输入文件为 flower.in。 输入的第一行包含一个整数,表示开始时花的株数。 第二行包含个整数,依次为 ?1, ?2, … , ?n,表示每株花的高度。 【输出】 输出文件为 flower.out。 输出一行,包含一个整数,表示最多能留在原地的花的株数。
第 5 页共 5 页

全国信息学奥林匹克联赛(NOIP2013)复赛

提高组 day2

【输入输出样例】 flower.in 5 53212

flower.out 3

【输入输出样例说明】 有多种方法可以正好保留 3 株花,例如,留下第 1、4、5 株,高度分别为 5、1、2,满足条件 B。 【数据范围】 对于 20%的数据,n ≤ 10; 对于 30%的数据,n ≤ 25; 对于 70%的数据,n ≤ 1000,0 ≤ ?n≤ 1000; 对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤ ?n≤ 1,000,000,所有的 ?n 随机生成,所有随机 数服从某区间内的均匀分布。

3.华容道 (puzzle.cpp/c/pas) 【问题描述】 小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次。于是,他想到用编程 来完成华容道:给定一种局面,华容道是否根本就无法完成,如果能完成,最少需要多少时间。 小 B 玩的华容道与经典的华容道游戏略有不同,游戏规则是这样的: 1. 在一个 n*m 棋盘上有 n*m 个格子,其中有且只有一个格子是空白的,其余 n*m-1 个 格子上每个格子上有一个棋子,每个棋子的大小都是 1*1 的; 2. 有些棋子是固定的,有些棋子则是可以移动的; 3. 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。游戏 的目的是把某个指定位置可以活动的棋子移动到目标位置。 给定一个棋盘,游戏可以玩 q 次,当然,每次棋盘上固定的格子是不会变的,但是棋盘上 空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 i 次玩的 时候,空白的格子在第 EXi 行第 EYi 列,指定的可移动棋子的初始位置为第 SXi 行第 SYi 列,目
第 6 页共 5 页

全国信息学奥林匹克联赛(NOIP2013)复赛

提高组 day2

标位置为第 TXi 行第 TYi 列。 假设小 B 每秒钟能进行一次移动棋子的操作,而其他操作的时间都可以忽略不计。请你告 诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。 【输入】 输入文件为 puzzle.in。 第一行有 3 个整数,每两个整数之间用一个空格隔开,依次表示 n、m 和 q; 接下来的 n 行描述一个 n*m 的棋盘,每行有 m 个整数,每两个整数之间用一个空格隔开,每 个整数描述棋盘上一个格子的状态,0 表示该格子上的棋子是固定的,1 表示该格子上的棋子可以 移动或者该格子是空白的。 接下来的 q 行,每行包含 6 个整数依次是 EXi、EYi、SXi、SYi、TXi、TYi,每两个整数之间 用一个空格隔开,表示每次游戏空白格子的位置,指定棋子的初始位置和目标位置。 【输出】 输出文件名为 puzzle.out。 输出有 q 行,每行包含 1 个整数,表示每次游戏所需要的最少时间,如果某次游戏无法完 成目标则输出?1。 【输入输出样例】 puzzle.in 3 4 2 0 1 1 1 0 1 1 0 0 1 0 0 3 2 1 2 2 2 1 2 2 2 3 2 puzzle.out 2 -1

【输入输出样例说明】 棋盘上划叉的格子是固定的,红色格子是目标位置,圆圈表示棋子,其中绿色圆圈表示目标 棋子。 1.第一次游戏,空白格子的初始位置是 (3, 2)(图中空白所示) ,游戏的目标是将初始位 置在(1, 2)上的棋子(图中绿色圆圈所代表的棋子)移动到目标位置(2, 2)(图中红色的格子) 上。 移动过程如下: 初始状态第一步之后第二步之后

2. 第二次游戏,空白格子的初始位置是(1, 2) (图中空白所示) ,游戏的目标是将初始位 置在(2, 2)上的棋子(图中绿色圆圈所示)移动到目标位置 (3, 2)上。
第 7 页共 5 页

全国信息学奥林匹克联赛(NOIP2013)复赛

提高组 day2

初始状态

要将指定块移入目标位置,必须先将空白块移入目标位置,空白块要移动到目标位置,必然 是从位置(2, 2)上与当前图中目标位置上的棋子交换位置,之后能与空白块交换位置的只有 当前图中目标位置上的那个棋子,因此目标棋子永远无法走到它的目标位置,游戏无法完成。 【数据范围】 对于 30%的数据,1 ≤ n, m ≤ 10,q = 1; 对于 60%的数据,1 ≤ n, m ≤ 30,q ≤ 10; 对于 100%的数据,1 ≤ n, m ≤ 30,q ≤ 500。

第 8 页共 5 页


相关文章:
NOIP2013提高组复赛试题
全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 CCF 全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day1 1.转圈游戏 (circle.cpp/c/pas) 【问题描述】 ...
NOIP2013提高组复赛试题day2
全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 CCF 全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 (请选手务必仔细阅读本页内容)一.题目概况中文题目...
NOIP历年复赛提高组试题(2004-2013)
2004~2013NOIP 复赛试题集(提高组) 第十届全国信息学奥林匹克分区联赛(NOIP2004)复赛试题(提高组 竞赛用时:3 小时) 1、津津的储蓄计划(Save.pas/dpr/c...
NOIP2013提高组复赛试题day1+day2
NOIP2013提高组复赛试题day1+day2_财会/金融考试_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档 NOIP2013提高组复赛试题day1+day2_财会/金融考试_...
NOIP2013提高组C++试题
NOIP2013提高组C++试题_电子/电路_工程科技_专业资料。第十九届全国青少年信息学...任何一个在(输入规模的)指数时间内能够解决的问题 CCF NOIP 复赛考试结束后,因...
NOIP2013初赛提高组c试题
NOIP2013初赛提高组c试题_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学...任何一个在(输入规模的)指数时间内能够解决的问题 CCF NOIP 复赛考试结束后,因...
NOIP2014提高组复赛试题day1+day2
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头...NOIP2012提高组day2试题 4页 2下载券 NOIP2013提高组复赛试题... 5页 免费...
NOIP2014提高组复赛试题(C语言版)
NOIP2014提高组复赛试题(C语言版)_其它课程_高中教育_教育专区。NOIP2014提高组复赛试题 C语言CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务...
NOIP2013信息学奥林匹克联赛初赛试题(提高组PASCAL)
NOIP2013信息学奥林匹克联赛初赛试题(提高组PASCAL)_学科竞赛_高中教育_教育专区...(输入规模的)指数时间内能够解决的问题 CCF NOIP 复赛考试结束后,因( 源程序...
更多相关标签:
noip提高组复赛试题 | noip2016提高组复赛 | noip2015提高组复赛 | noip2014提高组复赛 | noip2010提高组复赛 | noip2016复赛试题 | noip2012提高组复赛 | noip2013提高组复赛 |