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

NOIP2013提高组复赛试题day2


全国信息学奥林匹克联赛(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) 【题目描述】 春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为 n 的大厦, 大厦可以看成由 n 块宽度为 1 的积木组成,第 i 块积木的最终高度需要是 ?i。 在搭建开始之前,没有任何积木(可以看成块高度为 0 的积木)。接下来每次操作,小朋友 们可以选择一段连续区间[L,R],然后将第 L 块到第 R 块之间(含第 L 块和第 R 块)所有积木的 高度分别增加 1。 小 M 是个聪明的小朋友,她很快想出了建造大厦的最佳策略,使得建造所需的操作次数最 少。但她不是一个勤于动手的孩子,所以想请你帮忙实现这个策略,并求出最少的操作次数。 【输入】 输入文件为 block.in 输入包含两行,第一行包含一个整数 n,表示大厦的宽度。 第二行包含 n 个整数,第 i 个整数为 ?i。 【输出】 输出文件为 block.out 仅一行,即建造所需的最少操作数。 【输入输出样例】 block.in 5 23412 block.out 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,则栋栋希望下面两个条件中至少有一个满足: 条件 A:对于所有的 1≤i≤
m m ,有 g2i > g2i-1,同时对于所有的 1≤i≤ ,有 g2i > g2i+1; 2 2
第 2 页共 5 页

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

提高组 day2

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

m m ,有 g2i < g2i-1,同时对于所有的 1≤i≤ ,有 g2i < g2i+1。 2 2

注意上面两个条件在 m = 1 时同时满足,当 m > 1 时最多有一个能满足。 请问,栋栋最多能将多少株花留在原地。 【输入】 输入文件为 flower.in。 输入的第一行包含一个整数,表示开始时花的株数。

第二行包含个整数,依次为 ?1, ?2, … , ?n,表示每株花的高度。
【输出】 输出文件为 flower.out。 输出一行,包含一个整数,表示最多能留在原地的花的株数。 【输入输出样例】 flower.in 5 5 3 2 1 2

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 列,目
第 3 页共 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)上。 初始状态

第 4 页共 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。

第 5 页共 5 页


相关文章:
Noip 2013 提高组 Day2 解题报告
Noip 2013 提高组 Day2 解题报告_学科竞赛_高中教育_教育专区。Noip 2013 提高组 Day2 解题报告 Noip 2013 Day2 解题报告 --By GreenCloudS 第一题:积木大赛...
NOIP2014提高组复赛试题day1+day2
NOIP2014提高组复赛试题day1+day2_从业资格考试_资格考试/认证_教育专区。CCF ...NOIP2013提高组复赛试题... 4页 免费 NOIP2014普及组复赛试题... 6页 免费 ...
Noip_2013_提高组_Day2_解题报告
(n)的时间复杂度,当然是顺利 AC 了,代码如 下: 2.这道题明显可以用类似...NOIP2013提高组day2 5页 2下载券 NOIP2013提高组复赛Day2 5页 免费 ©...
NOIP2015提高组复赛试题Day1+Day2纯Word版
NOIP2015提高组复赛试题Day1+Day2纯Word版_学科竞赛_高中教育_教育专区。NOIP2015提高组复赛试题Day1+Day2纯Word版 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组...
学军中学NOIP2013提高组原创模拟题day2
学军中学NOIP2013提高组原创模拟题day2_IT/计算机_专业资料。学军中学noip模拟题 学军中学 NOIP2013 提高组原创模拟题 day2 测试时间:3.5 小时 中文题目名称 ...
历届noip提高组复赛试题
历届noip提高组复赛试题_学科竞赛_高中教育_教育专区。NOI’95 “同创杯”全国...样例 输入 30000-2-20000-228800-16-25000-16 输出 30000=11011010101110000(...
NOIP2015提高组复赛试题Day1
NOIP2015提高组复赛试题Day1_学科竞赛_高中教育_教育专区。NOIP2015提高组复赛...2 秒 10 10 20 10 10 5 有有有 全文比较(过滤行末空格及文末回车) 传统...
noip2015提高组复赛试题答案
noip2015提高组复赛试题答案_IT认证_资格考试/认证_教育专区。全国信息学奥林...第2页共6页 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 2.信息传递...
NOIP2013初赛提高组c试题
NOIP2013初赛提高组c试题_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学...个节点,则其中至多有( A. 1006 B. 1007 C. 1023 )个节点有 2 个子节点...
NOIP2014提高组复赛试题
NOIP2014提高组复赛试题_学科竞赛_高中教育_教育专区。CCF 全国信息学奥林匹克...CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day2 1.无线网络发射器...
更多相关标签: