当前位置:首页 >> 学科竞赛 >> NOIP2014提高组复赛试题

NOIP2014提高组复赛试题


CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 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 6 2 rps.out

【输入输出样例 2】 rps.in 9 5 5 0 1 2 3 4 1 0 3 2 4 4 4 rps.out

【数据说明】 对于 100%的数据,0 < N ≤ 200,0 < NA ≤ 200, 0 < NB ≤ 200。

2.联合权值 (link.cpp/c/pas) 【问题描述】 无向连通图 G 有 n 个点,n-1 条边。点从 1 到 n 依次编号,编号为 i 的点的权值为 Wi 离为 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 link.out ,每条边的长 度均为 1。图上两点(u, v)的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对(u, v),若它们的距

5 1 2 2 3 3 4 4 5 1 5 2 3 10

20 74

【样例说明】

本例输入的图如上所示,距离为 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. 2. 3. 游戏界面是一个长为 n, 高 为 m 的二维平面, 其中有 k 个管 道(忽略管道的宽度) 。 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整 数高度位置出发,到达游戏界面最右边时,游戏完成。 小鸟每个单位时间沿横坐标方向右移的距离为 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 bird.out

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

【输入输出样例 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 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, 路口公共场所的数量。同一坐标只会给出一次。 【输出】 输出文件名为 wireless.out。 输出一行,包含两个整数,用一个空格隔开,分别表示能覆盖最多公共场所的安装地点方案数,以及 能覆盖的最多公共场所的数量。 【输入输出样例】 wireless.in 1 2 4 4 10 6 6 20 1 30 wireless.out 中间用一个空格隔开,分别代表路口的坐标(x, y)以及该

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

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 2 1 2 2 1 1 3 -1 road.out

【输入输出样例说明】

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

6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 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; 10000 对于 70%的数据,0<n≤100,|ai|≤10 ,an≠0,m≤10000; 10000 对于 100%的数据,0<n≤100,|ai|≤10 ,an≠0,m≤1000000。


更多相关文档:

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提高组复赛试题Day1

NOIP2014提高组复赛试题Day1_学科竞赛_高中教育_教育专区。CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况 ...

NOIP2014提高组复赛试题Day2

NOIP2014提高组复赛试题Day2_学科竞赛_高中教育_教育专区。CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day2 (请选手务必仔细阅读本页内容)一.题目概况 ...

NOIP2014复赛提高组模拟试题

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

NOIP历年复赛提高组试题(2006-2014)

2006~2014NOIP 复赛试题集(提高组) 第十二届全国信息学奥林匹克分区联赛(NOIP2006)复赛试题(提高组 竞赛用时:3 小时) 关于竞赛中不同语言使用限制的说明一...

NOIP2014提高组第二试题解

NOIP2014提高组第二试题解_IT认证_资格考试/认证_教育专区。NOIP2014提高组第二...NOIP2014提高组C++试题 10页 3下载券 NOIP2014提高组复赛试题... 6页 1...

NOIP2013提高组复赛试题day2

NOIP2013提高组复赛试题day2_学科竞赛_高中教育_教育专区。全国信息学奥林匹克联赛...NOIP2014提高组复赛试题... NOIP2014提高组复赛试题...1/2 相关文档推荐 ...
更多相关标签:
noip提高组复赛试题 | noip2016提高组复赛 | noip2015提高组复赛 | noip2014提高组复赛 | noip2010提高组复赛 | noip2016复赛试题 | noip2012提高组复赛 | noip2013提高组复赛 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com