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

NOIP2014提高组复赛试题


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

提高组 day1
(请选手务必仔细阅读本页内容)
一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 运行内存上限 二.?交源程序文件名 对于 C++语言 对于 C 语

言 对于 pascal 语言 rps.cpp rps.c rps.pas link.cpp link.c link.pas bird.cpp bird.c bird.pas 生活大爆炸版石头剪刀布 rps rps rps.in rps.out 1秒 10 10 有 联合权值 link link link.in link.out 1秒 10 10 有 全文比较(过滤行末空格及文末回车) 传统 128M 传统 128M 传统 128M 飞扬的小鸟 bird bird bird.in bird.out 1秒 20 5 有

三.编译命令(不包含任何优化开关) 对于 C++语言 对于 C 语言 对于 pascal 语言 g++ -o rps rps.cpp –lm gcc -o rps rps.c –lm fpc rps.pas g++ -o link link.cpp –lm gcc -o link link.c –lm fpc link.pas g++ -o bird bird.cpp –lm gcc -o bird bird.c –lm fpc bird.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.生活大爆炸版石头剪刀布 (rps.cpp/c/pas)
【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一 样,则不分胜负。在《生活大爆炸》第二季第 8 集中出现了一种石头剪刀布的升级版游戏。 升级版游戏在传统的石头剪刀布游戏的基础上,增加了两个新手势: 斯波克: 《星际迷航》主角之一。 蜥蜴人: 《星际迷航》中的反面角色。 这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。 表一 石头剪刀布升级版胜负关系 乙 甲对乙的 甲 结果 剪刀 石头 布 蜥蜴人 斯波克

剪刀

石头



蜥蜴人

斯波克



输 平

赢 输 平

赢 赢 输 平

输 输 赢 赢 平

现在, 小 A 和小 B 尝试玩这种升级版的猜拳游戏。 已知他们的出拳都是有周期性规律的, 但周期长度不一定相等。例如:如果小 A 以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为 6 的周期出拳,那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头 -剪刀-蜥蜴人-斯波克-??” ,而如果小 B 以“剪刀-石头-布-斯波克-蜥蜴人”长度为 5 的 周期出拳,那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克蜥蜴人-??” 已知小 A 和小 B 一共进行 N 次猜拳。每一次赢的人得 1 分,输的得 0 分;平局两人都得 0 分。现请你统计 N 次猜拳结束之后两人的得分。 【输入】 输入文件名为 rps.in。 第一行包含三个整数:N,NA,NB,分 别 表 示 共 进 行 N 次猜拳、小 A 出拳的周期 长度,小 B 出拳的周期长度。数与数之间以一个空格分隔。 第二行包含 NA 个整数,表示小 A 出拳的规律,第三行包含 NB 个整数,表示小 B 出拳的 规律。其中,0 表示“剪刀” ,1 表示“石头” ,2 表示“布” ,3 表示“蜥蜴人” , 4 表示“斯 波克” 。数与数之间以一个空格分隔。

【输出】 输出文件名为 rps.out。 输出一行, 包含两个整数,以一个空格分隔,分别表示小 A、小 B 的得分。 【输入输出样例 1】 rps.in 10 5 6 0 1 2 3 4 0 3 4 2 1 0 【输入输出样例 2】 rps.in 9 5 5 0 1 2 3 4 1 0 3 2 4 【数据说明】 对于 100%的数据,0 < N ≤ 4 4 rps.out 6 2 rps.out

200,0 < NA ≤

200, 0 < NB ≤ 200。

2.联合权值 (link.cpp/c/pas)
【问题描述】 无向连通图 G 有 n 个点, n-1 条边。 点从 1 到 n 依次编号, 编号为 i 的点的权值为 Wi , 每条边的长度均为 1。图上两点(u, v)的距离定义为 u 点到 v 点的最短距离。对于图 G 上的 点对(u, v),若它们的距离为 2,则它们之间会产生 Wu×Wv 的联合权值。 请问图 G 上所有可产生联合权值的有序点对中, 联合权值最大的是多少?所有联合权值 之和是多少? 【输入】 输入文件名为 link.in。 第一行包含 1 个整数 n。 接下来 n-1 行,每行包含 2 个用空格隔开的正整数 u、v,表示编号为 u 和编号为 v 的 点之间有边相连。 最后 1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i 个整数表示 图 G 上编号为 i 的点的权值为 Wi。 【输出】 输出文件名为 link.out。 输出共 1 行,包含 2 个整数,之间用一个空格隔开,依次为图 G 上联合权值的最大值和

所有联合权值之和。由于所有联合权值之和可能很大,输出它时要对 10007 取余。 【输入输出样例】 link.in 5 1 2 3 4 1 20 74 2 3 4 5 5 2 3 10 link.out

【样例说明】

本例输入的图如上所示,距离为 2 的有序点对有(1,3)、(2,4)、(3,1)、(3,5)、(4,2)、 (5,3)。其联合权值分别为 2、15、2、20、15、20。其中最大的是 20,总和为 74。 【数据说明】 对于 30%的数据,1<≤100; 对于 60%的数据,1<≤2000; 对于 100%的数据,1<≤200,000,0<Wi ≤10,000。

3. 飞扬的小鸟 (bird.cpp/c/pas)
【问题描述】 Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需 要不断控制点击手机屏幕的频率来调节小鸟的飞行高度,让 小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到 了水管或者掉在地上的话,便宣告失败。 为了简化问题,我们对游戏规则进行了简化和改编: 1. 游戏界面是一个长为 n,高 为 m 的二维平面,其中 有 k 个管道(忽略管道的宽度) 。 2. 小鸟始终在游戏界面内移动。小鸟从游戏界面最左 边任意整数高度位置出发, 到达游戏界面最右边时, 游戏完成。 3. 小鸟每个单位时间沿横坐标方向右移的距离为 1,竖直移动的距离由玩家控制。如 果点击屏幕,小鸟就会上升一定高度 X,每个单位时间可以点击多次,效果叠加; 如果不点击屏幕,小鸟就会下降一定高度 Y。小鸟位于横坐标方向不同位置时,上 升的高度 X 和下降的高度 Y 可能互不相同。 4. 小鸟高度等于 0 或者小鸟碰到管道时,游 戏 失 败 。小 鸟 高 度 为 m 时,无法 再上升。 现在,请你判断是否可以完成游戏。如果可以,输出最少点击屏幕数;否则,输出小鸟 最多可以通过多少个管道缝隙。 【输入】 输入文件名为 bird.in。 第 1 行有 3 个整数 n,m,k,分别表示游戏界面的长度,高度和水管的数量,每两个整 数之间用一个空格隔开; 接下来的 n 行,每行 2 个用一个空格隔开的整数 X 和 Y,依次表示在横坐标位置 0~n-1 上玩家点击屏幕后,小鸟在下一位置上升的高度 X,以及在这个位置上玩家不点击屏幕时, 小鸟在下一位置下降的高度 Y。 接下来 k 行,每行 3 个整数 P,L,H,每两个整数之间用一个空格隔开。每行表示一个 管道,其中 P 表示管道的横坐标,L 表示此管道缝隙的下边沿高度为 L,H 表示管道缝隙上 边沿的高度(输入数据保证 P 各不相同,但不保证按照大小顺序给出) 。 【输出】 输出文件名为 bird.out。 共两行。 第一行,包含一个整数,如果可以成功完成游戏,则输出 1,否则输出 0。 第二行,包含一个整数,如果第一行为 1,则输出成功完成游戏需要最少点击屏幕数, 否则,输出小鸟最多可以通过多少个管道缝隙。 【输入输出样例 1】

bird.in 10 10 6 3 9 9 9 1 2 1 3 1 2 1 1 2 1 2 1 1 6 2 2 1 2 7 5 1 5 6 3 5 7 5 8 8 7 9 9 1 3 1 6

bird.out

【输入输出样例 2】 bird.in 10 10 4 1 2 3 1 2 2 1 8 1 8 3 2 2 1 2 1 2 2 1 2 1 0 2 6 7 9 9 1 4 3 8 10 0 3 bird.out

【输入输出样例说明】 如下图所示,蓝色直线表示小鸟的飞行轨迹,红色直线表示管道。

【数据范围】 对于 30%的数据:5≤n≤10,5≤m≤10,k=0,保证存在一组最优解使得同一单位时间 最多点击屏幕 3 次; 对于 50%的数据:5≤n≤20,5≤m≤10,保证存在一组最优解使得同一单位时间最多点 击屏幕 3 次; 对于 70%的数据:5≤n≤1000,5≤m≤100; 对于 100%的数据:5≤n≤10000,5≤m≤1000,0≤k<n,0<X<m,0<Y<m,0<P<n,0≤L<H ≤m,L+1<H。

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

提高组 day2
(请选手务必仔细阅读本页内容)
一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 无线网路发射器选址 wireless wireless wireless.in wireless.out 1秒 10 10 有 寻找道路 road road road.in road.out 1秒 10 10 有 全文比较(过滤行末空格及文末回车) 解方程 equation equation equation.in equation.out 1秒 20 5 有

题目类型 运行内存上限 二.?交源程序文件名 对于 C++语言 对于 C 语言 对于 pascal 语言

传统 128M

传统 128M

传统 128M

wireless.cpp wireless.c wireless.pas

road.cpp road.c road.pas

equation.cpp equation.c equation.pas

三.编译命令(不包含任何优化开关) 对于 C++语言 对于 C 语言 对于 pascal 语言 g++ -o wireless wireless.cpp–lm gcc -o wireless wireless.c –lm fpc wireless.pas g++ -o road road.cpp –lm gcc -o road road.c –lm fpc road.pas g++ -o equation equation.cpp–lm gcc -o equation equation.c –lm fpc equation.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.无线网络发射器选址 (wireless.cpp/c/pas)
【问题描述】 随着智能手机的日益普及, 人们对无线网的需求日益增大。 某城市决定对城市内的公共 场所覆盖无线网。 假设该城市的布局为由严格平行的 129 条东西向街道和 129 条南北向街道所形成的网格 状, 并且相邻的平行街道之间的距离都是恒定值 1。 东西向街道从北到南依次编号为 0,1,2? 128,南北向街道从西到东依次编号为 0,1,2?128。 东西向街道和南北向街道相交形成路口, 规定编号为 x 的南北向街道和编号为 y 的东西 向街道形成的路口的坐标是(x, y) 。 在 某 些 路 口 存 在 一 定 数 量 的 公 共 场 所 。 由于政府财政问题, 只能安装一个大型无线网络发射器。 该无线网络发射器的传播范围 是一个以该点为中心,边长为 2*d 的正方形。传播范围包括正方形边界。 例如下图是一个 d = 1 的无线网络发射器的覆盖范围示意图。

现在政府有关部门准备安装一个传播参数为 d 的无线网络发射器, 希望你帮助他们在城 市内找出合适的安装地点,使得覆盖的公共场所最多。 【输入】 输入文件名为 wireless.in。 第一行包含一个整数 d,表示无线网络发射器的传播距离。 第二行包含一个整数 n,表示有公共场所的路口数目。 接下来 n 行,每行给出三个整数 x, y, k, 中间用一个空格隔开,分别代表路口的坐 标(x, y)以及该路口公共场所的数量。同一坐标只会给出一次。 【输出】 输出文件名为 wireless.out。 输出一行,包含两个整数,用一个空格隔开,分别表示能覆盖最多公共场所的安装地点 方案数,以及能覆盖的最多公共场所的数量。 【输入输出样例】 wireless.in 1 2 4 4 10 6 6 20 1 30 wireless.out

【数据说明】 对于 100%的数据,1 ≤ d ≤ 20,1 ≤ n ≤ 20, 0 ≤ x ≤ 128, 0 ≤ y ≤ 0 < k ≤ 1,000,000。

128,

2.寻找道路 (road.cpp/c/pas)
【问题描述】

在有向图 G 中,每条边的长度均为 1,现给定起点和终点,请你在图中找一条从起点到 终点的路径,该路径满足以下条件: 1.路径上的所有点的出边所指向的点都直接或间接与终点连通。 2.在满足条件 1 的情况下使路径最短。 注意:图 G 中可能存在重边和自环,题目保证终点没有出边。 请你输出符合条件的路径的长度。 【输入】 输入文件名为 road.in。 第一行有两个用一个空格隔开的整数 n 和 m,表示图有 n 个点和 m 条边。 接下来的 m 行每行 2 个整数 x、 y, 之间用一个空格隔开, 表示有一条边从点 x 指向点 y。 最后一行有两个用一个空格隔开的整数 s、t,表示起点为 s,终点为 t。 【输出】 输出文件名为 road.out。 输出只有一行,包含一个整数,表示满足题目描述的最短路径的长度。如果这样的路径 不存在,输出-1。 【输入输出样例 1】 road.in 3 1 2 1 2 2 1 3 -1 road.out

【输入输出样例说明】

如上图所示,箭头表示有向道路,圆点表示城市。起点 1 与终点 3 不连通,所以满足题 目描述的路径不存在,故输出-1。 【输入输出样例 2】 road.in road.out

6 1 1 2 2 4 3 1

6 2 3 6 5 5 4 5

3

【输入输出样例说明】

如上图所示,满足条件的路径为 1->3->4->5。注意点 2 不能在答案路径中,因为点 2 连了一条边到点 6,而点 6 不与终点 5 连通。 【数据说明】 对于 30%的数据,0< n ≤10,0< m ≤20; 对于 60%的数据,0< n ≤100,0< m ≤2000; 对于 100%的数据,0< n ≤10,000,0< m ≤200,000,0< x,y,s,t≤n,x≠t。

3.解方程 (equation.cpp/c/pas)

【问题描述】 已知多项式方程:

求这个方程在[1, m]内的整数解(n 和 m 均为正整数) 。 【输入】 输入文件名为 equation.in。 输入共 n+2 行。 第一行包含 2 个整数 n、m,每两个整数之间用一个空格隔开。 接下来的 n+1 行每行包含一个整数,依次为 a0,a1,a2,??,an。 【输出】 输出文件名为 equation.out。 第一行输出方程在[1, m]内的整数解的个数。 接下来每行一个整数,按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。 【输入输出样例 1】 equation.in 2 10 1 -2 1 1 1 equation.out

【输入输出样例 2】 equation.in 2 10 2 -3 1 2 1 2 equation.out

【输入输出样例 3】 equation.in 2 10 1 3 2 0 equation.out

【数据说明】 对于 30%的数据,0<n≤2,|ai|≤100,an≠0,m≤100; 100 对于 50%的数据,0<n≤100,|ai|≤10 ,an≠0,m≤100;

对于 70%的数据,0<n≤100,|ai|≤10 ,an≠0,m≤10000; 10000 对于 100%的数据,0<n≤100,|ai|≤10 ,an≠0,m≤1000000。

10000


相关文章:
NOIP2014提高组复赛试题day1+day2
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,...
NOIP2014提高组复赛试题
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,...
NOIP2014提高组复赛试题
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 ...
NOIP2014提高组复赛试题(C语言版)
NOIP2014提高组复赛试题(C语言版)_其它课程_高中教育_教育专区。NOIP2014提高组复赛试题 C语言CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务...
NOIP2014复赛提高组模拟试题
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 day1 CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一、题目概况 中文题目...
NOIP2014提高组复赛试题Day1
NOIP2014提高组复赛试题Day1_学科竞赛_高中教育_教育专区。CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况 ...
NOIP2014提高组复赛试题Day2
NOIP2014提高组复赛试题Day2_学科竞赛_高中教育_教育专区。CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day2 (请选手务必仔细阅读本页内容)一.题目概况 ...
NOIP2014提高组第二试题解
NOIP2014提高组第二试题解_IT认证_资格考试/认证_教育专区。NOIP2014提高组第二...NOIP2014提高组C++试题 10页 3下载券 NOIP2014提高组复赛试题... 6页 1...
NOIP2014提高组第一试题解
NOIP2014 提高组第一试题解【第一题】石头剪刀布 rps 【题目大意】 a 和 b...NOIP2014复赛提高组模拟... 5页 1下载券 NOIP2014提高组复赛试题... 13页...
NOIP历年复赛提高组试题(2006-2014)
2006~2014NOIP 复赛试题集(提高组) 第十二届全国信息学奥林匹克分区联赛(NOIP2006)复赛试题(提高组 竞赛用时:3 小时) 关于竞赛中不同语言使用限制的说明一...
更多相关标签:
noip提高组复赛试题 | noip2016提高组复赛 | noip2015提高组复赛 | noip2014提高组复赛 | noip2016复赛试题 | noip2010提高组复赛 | noip2012提高组复赛 | noip2013提高组复赛 |