tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

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)

【题目描述】 春春幼儿园举办了一年一度的“积木大赛” 。今年比赛的内容是搭建一座宽度为的大 厦,大厦可以看成由块宽度为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:对于所有的1 ≤ ≤ 2 ,有2 > 2?1 , 同时对于所有的 1 ≤ < 2 ,有2 > 2+1 ;
条件 B:对于所有的1 ≤ ≤
2

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

,有2 < 2?1 ,同 时对于所有的1 ≤ < 2 ,有2 < 2+1 。



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 页


推荐相关:

NOIP2013提高组复赛试题day2

全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 CCF 全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 (请选手务必仔细阅读本页内容)一.题目概况中文题目...


NOIP2013提高组复赛试题day1+day2

NOIP2013提高组复赛试题day1+day2_财会/金融考试_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档 NOIP2013提高组复赛试题day1+day2_财会/金融考试_...


NOIP2013提高组复赛试题

全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 CCF 全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day1 1.转圈游戏 (circle.cpp/c/pas) 【问题描述】 ...


Noip 2013 提高组 Day2 解题报告

Noip 2013 提高组 Day2 解题报告_学科竞赛_高中教育_教育专区。Noip 2013 提高组 Day2 解题报告 Noip 2013 Day2 解题报告 --By GreenCloudS 第一题:积木大赛...


NOIP2014提高组复赛试题day1+day2

NOIP2014提高组复赛试题day1+day2_从业资格考试_资格考试/认证_教育专区。CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (...


Noip_2013_提高组_Day2_解题报告

Noip_2013_提高组_Day2_解题报告_计算机软件及应用_IT/计算机_专业资料。第二...NOIP2013提高组day2 5页 2下载券 NOIP2013提高组复赛Day2 5页 免费 ©...


学军中学NOIP2013提高组原创模拟题day2

学军中学NOIP2013提高组原创模拟题day2_IT/计算机_专业资料。学军中学noip模拟题 学军中学 NOIP2013 提高组原创模拟题 day2 测试时间:3.5 小时 中文题目名称 ...


CCF NOIP2013 解题报告&心得

第5 页共5 页 全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 3.货车运输 (truck.cpp/c/pas) 【问题描述】 A 国有 n 座城市,编号从 1 到 n,...


NOIP2014提高组复赛试题(C语言版)

CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day2 (请选手务必仔细阅读本页内容)一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 ...


NOIP2013复赛模拟8解题报告

NOIP2013复赛模拟8解题报告_学科竞赛_高中教育_教育...NOIP2008 模拟试题 1(4P24)普及组 1.报数(read....2:=time2+monthday[i]*60*24; if (getyearday...

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