nbhkdz.com冰点文库

NOIP2014

时间:2014-11-14


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

提高组 day1

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

提高组 day1
(请选手务必仔细阅读本页内容)
一.题目概况
中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 运行内存上限 传统 128M 生活大爆炸版 石头剪刀布 rps rps rps.in rps.out 1秒 10 10 有 link link link.in link.out 1秒 10 10 有 全文比较(过滤行末空格及文末回车) 传统 128M 传统 128M bird bird bird.in bird.out 1秒 20 5 有 联合权值 飞扬的小鸟

二.提交源程序文件名
对于 C++语言 对于 C 语言 对于 pascal 语言 rps.cpp rps.c rps.pas link.cpp link.c link.pas bird.cpp bird.c bird.pas

三.编译命令(不包含任何优化开关)
对于 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 页共 7 页

全国信息学奥林匹克联赛(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 的得分。

第 2 页共 7 页

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

提高组 day1

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

rps.out 6 2

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

rps.out 4 4

【数据说明】 对于 100%的数据,0 < N ≤ 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,则它们之间会产生 ! × ! 的联合权值。 请问图 G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权 值之和是多少? 【输入】 输入文件名为 link.in。 第一行包含 1 个整数 n。 接下来 n-1 行,每行包含 2 个用空格隔开的正整数 u、v,表示编号为 u 和编号为 v 的点 之间有边相连。 最后 1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i 个整数表示 图 G 上编号为 i 的点的权值为 Wi。 【输出】 输出文件名为 link.out。 输出共 1 行,包含 2 个整数,之间用一个空格隔开,依次为图 G 上联合权值的最大值 和所有联合权值之和。由 于 所 有 联 合 权 值 之 和 可 能 很 大 , 输 出 它 时 要 对 10007 取 余 。
第 3 页共 7 页

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

提高组 day1

【输入输出样例】 link.in 5 1 2 2 3 3 4 4 5 1 5 2 3 10

link.out 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 < ! ≤ 10,000。

第 4 页共 7 页

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

提高组 day1

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,则输出成功完成游戏需要最少点击屏幕数, 否则,输出小鸟最多可以通过多少个管道缝隙。

第 5 页共 7 页

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

提高组 day1

【输入输出样例 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

bird.out 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

bird.out 0 3

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

第 6 页共 7 页

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

提高组 day1

【数据范围】 对于 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。

第 7 页共 7 页


赞助商链接

noip2014普及组复赛题解

noip2014普及组复赛题解_财会/金融考试_资格考试/认证_教育专区。noip2014普及组复赛题解 余姚中学 罗方炜 余姚中学 罗方炜 1. 珠心算测验 注意看清题意:其中有...

NOIP2014 题解

NOIP2014 题解_IT/计算机_专业资料。NOIP2014 题解 D1T1 : 生活大爆炸版石头剪刀布(rps) 100% : 模拟。另一种方法,可以先求出 na,nb 的最小公倍数 l,...

NOIP2014提高组复赛试题

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

Noip2014初赛提高组C试题及答案(完整版)

Noip2014初赛提高组C试题及答案(完整版)_IT认证_资格考试/认证_教育专区。Noip2014 初赛提高组试题及答案(完整版) 提高组 C 语言试题 一、单项选择题(每题 1.5...

NOIP2014提高组第一试题解

NOIP2014 提高组第一试题解【第一题】石头剪刀布 rps 【题目大意】 a 和 b 石头剪刀布游戏,每个人一共有五种方式,相互之间的胜负关系给出,a 和 b 出拳的...

NOIP2014初赛普及组C++题目及答案

NOIP2014初赛普及组C++题目及答案_学科竞赛_高中教育_教育专区。本文是noip2014年普及组c++的题目及答案,有需要的可以下载学习。第二十届全国青少年信息学奥林匹克...

noip2014普及组初赛试题

noip2014普及组初赛试题_学科竞赛_初中教育_教育专区。noip2014普及组初赛试题 第二十届全国青少年信息学奥林匹克联赛初赛普及组 pascal 语言试题 1、以下哪个是面向...

NOIP2014普及组复赛试题解答2

NOIP2014普及组复赛试题解答2_IT认证_资格考试/认证_教育专区。NOIP2014普及组复赛试题 螺旋矩阵 解答 NOIP2014 普及组复赛试题解答 3. 螺旋矩阵 【问题描述】 一...

NOIP2014初赛普及组试题_C++

NOIP2014初赛普及组试题_C++_学科竞赛_初中教育_教育专区。NOIP2014初赛普及组试题 第二十届全国青少年信息学奥林匹克联赛初赛 普及组 C++语言试题 一、快单项选择题...

noip2014初赛普及组Pascal试题及答案

noip2014初赛普及组Pascal试题及答案_学科竞赛_初中教育_教育专区。noip2014初赛普及组Pascal试题及答案 第二十届全国青少年信息学奥林匹克联赛初赛 普及组 Pascal 语言...