nbhkdz.com冰点文库

NOIP2013第十九届全国青少年信息学奥林匹克联赛复赛试题提高组


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

提高组 day2

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

提高组 day2
(请选手务必仔细阅读本页内容)
一.题目概况
中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目

每个测试点分值 附加样例文件 结果比较方式 题目类型 运行内存上限 积木大赛 block block block.in block.out 1秒 10 10 有 传统 128M 花匠 flower flower flower.in flower.out 1秒 10 10 有 全文比较(过滤行末空格及文末回车) 传统 128M 传统 128M 华容道 puzzle puzzle puzzle.in puzzle.out 1秒 20 5 有

二.提交源程序文件名
对于 C++语言 对于 C 语言 对于 pascal 语言 block.cpp block.c block.pas flower.cpp flower.c flower.pas puzzle.cpp puzzle.c puzzle.pas

三.编译命令(不包含任何优化开关)
对于 C++语言 对于 C 语言 对于 pascal 语言 g++ -o block block.cpp -lm gcc -o block block.c -lm fpc block.pas g++ -o flower flower.cpp –lm gcc -o flower flower.c –lm fpc flower.pas g++ -o puzzle puzzle.cpp -lm gcc-o puzzle puzzle.c -lm fpc puzzle.pas

注意事项:
1、文件名(程序名和输入输出文件名)必须使用英文小写。 2、C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+, 2.71GHz,内存 2G,上述时限以此配置为准。 4、只提供 Linux 格式附加样例文件。 5、特别提醒:评测在 NOI Linux 下进行。

第 1 页共 5 页

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

提高组 day2

1.积木大赛
(block.cpp/c/pas)

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

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

第 2 页共 5 页

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

提高组 day2

2.花匠
(flower.cpp/c/pas) 【问题描述】 花匠栋栋种了一排花,每株花都有自己的高度。花儿越长越大,也越来越挤。栋栋决定 把这排中的一部分花移走,将剩下的留在原地,使得剩下的花能有空间长大,同时,栋栋希 望剩下的花排列得比较别致。 具体而言,栋栋的花的高度可以看成一列整数?1 , ?2 , … , ? 。设当一部分花被移走后, 剩下的花的高度依次为1 , 2 , … , ,则栋栋希望下面两个条件中至少有一个满足: 条件 A:对于所有的,2 > 2?1 ,且2 > 2+1 ; 条件 B:对于所有的,2 < 2?1,且2 < 2+1 。 注意上面两个条件在 = 1时同时满足,当 > 1时最多有一个能满足。 请问,栋栋最多能将多少株花留在原地。 【输入】 输入文件为 flower.in。 输入的第一行包含一个整数,表示开始时花的株数。 第二行包含个整数,依次为?1 , ?2 , … , ? ,表示每株花的高度。 【输出】 输出文件为 flower.out。 输出一行,包含一个整数,表示最多能留在原地的花的株数。 【输入输出样例】 flower.in 5 5 3 2 1 2

flower.out 3

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

第 3 页共 5 页

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

提高组 day2

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 列,目标位置为第 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 0 0 0 3 1 4 1 1 1 2 2 2 1 1 0 1 2 1 0 0 2 2 2 2 3 2

puzzle.out 2 -1

第 4 页共 5 页

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

提高组 day2

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

O O O O O

O O O O O

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

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

第 5 页共 5 页


第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析

第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:2013 ...任何一个在(输入规模的)指数时间内能够解决的问题 5.CCF NOIP 复赛考试结束后...

2013年第十九届全国青少年信息学奥林匹克联赛提高组初赛试题

2013年第十九届全国青少年信息学奥林匹克联赛提高组初赛试题_自我管理与提升_求职...NOIP2013 初赛提高组 Pascal 语言试题 第 3 页,共 11 页 5.CCF NOIP 复赛...

2013第十九届全国青少年信息学奥林匹克联赛初赛提高组(C++)

2013 第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:...任何一个在(输入规模的)指数时间内能够解决的问题 5.CCF NOIP 复赛考试结束后...

第十九届(2013年)全国青少年信息学奥林匹克联赛初赛_答案

第十九届(2013年)全国青少年信息学奥林匹克联赛初赛_答案_学科竞赛_初中教育_教育专区。第十九届(2013 年)全国青少年信息学奥林匹克联赛初赛 答案 普及组 Pascal 语...

NOIP2013第十九届信息学奥林匹克竞赛全国联赛提高组参考答案

NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛 提高组参考答案一、单项选择题(共 15 题,每题 1.5 分,共计 22.5 分) 1 2 3 4 5 6 7 8 A A B ...

第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析

第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:2013 ...任何一个在(输入规模的)指数时间内能够解决的问题 5.CCF NOIP 复赛考试结束后...

2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题

2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题_高中教育_教育专区。...D. 20. CCF NOIP 复赛全国统一评测时使用的系统软件是( )。 A. NOI ...

NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛试题解析

NOIP2013 第十九届全国青少年信息学奥林匹克联赛 初赛(提高组)试题解析一、单选题(15*1.5) 1、A,一个字节有 8 个 bit,32 位整型变量占用 4 个字节,故选 A...

2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题

2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题_学科竞赛_初中教育_教育...D. 20. CCF NOIP 复赛全国统一评测时使用的系统软件是( )。 A. NOI ...