当前位置：文档之家 › NOIP2014提高组复赛试题day1day2

NOIP2014提高组复赛试题day1day2

  • 格式：doc
  • 大小：229.50 KB
  • 文档页数：11

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

提高组dayl

1.生活大爆炸版石头剪刀布

(rps.cpp/c/pas)

【问题描述】

石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。如果两个人出拳样，则不分胜负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势：

斯波克：《星际迷航》主角之一。

蜥蜴人：《星际迷航》中的反面角色。

这五种手势的胜负关系如表一所示，表中列出的是甲对乙的游戏结果。

表一石头剪刀布升级版胜负关系

、甲对乙的一“甲'、结果 男力 石头 布 蜥蜴人 斯波克

男力 平 输 赢 赢 输

石头

平 输 赢 输

布

平 输 赢

蜥蜴人

平 赢

斯波克

平

现在，小A和小B尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，

但周期长度不一定相等。例如：如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为

6的周期出拳，那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头

-剪刀-蜥蜴人-斯波克-……”，而如果小B以“剪刀-石头-布-斯波克-蜥蜴人”长度为5的周期出拳，那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……”

已知小A和小B一共进行N次猜拳。每一次赢的人得1分，输的得0分；平局两人都得0分。现请你统计N次猜拳结束之后两人的得分。

【输入】

输入文件名为rps.in。

第一行包含三个整数：N,NANB分别表示共进行N次猜拳、小A出拳的周期长度，小B出拳的周期长度。数与数之间以一个空格分隔。 第二行包含NA个整数，表示小A出拳的规律，第三行包含NB个整数，表示小B出拳的规律。其中，0表示“剪刀”，1表示“石头”，2表示“布”，3表示“蜥蜴人”，4表示“斯波克”。数与数之间以一个空格分隔。

【输出】

输出文件名为rps.out。

输出一行，包含两个整数，以一个空格分隔，分别表示小A、小B的得分。

【输入输出样例1】

rps.in rps.out

1056 62

01234

034210

【输入输出样例2】

rps.in rps.out

955 44

01234

10324

【数据说明】

对于100%勺数据，0

2.联合权值

（link.cpp/c/pas）

【问题描述】

无向连通图G有n个点，n-1条边。点从1至ijn依次编号，编号为i的点的权值为Wi,每条边的长度均为1。图上两点（u,v）的距离定义为u点到v点的最短距离。对于图G上的点对（u,v）,若它们的距离为2,则它们之间会产生VuxWv的联合权值。

请问图G上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

【输入】

输入文件名为link.in。

第一行包含1个整数no

接下来n-1行，每行包含2个用空格隔开的正整数u、v,表示编号为u和编号为v的点之间有边相连。

最后1行，包含n个正整数，每两个正整数之间用一个空格隔开，其中第i个整数表示

图G上编号为i的点的权值为Wio

【输出】

输出文件名为link.out。 输出共1行，包含2个整数，之间用一个空格隔开，依次为图G上联合权值的最大值和

所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对10007取余。

【输入输出样例】

link.in link.out

5 2074

12

23

34

45

152310

【样例说明】

5

2

10>32

本例输入的图如上所示，距离为2的有序点对有(1,3)

(5,3)。其联合权值分别为2、15、2、20、15、20。其中最:

【数据说明】

对于30%勺数据，1

对于60%勺数据，1

对于100%勺数据，1«200,000,0

大的是20,总和为74。 3,飞扬的小鸟

(bird.cpp/c/pas)

果点击屏幕，小鸟就会上升一定高度X,每个单位时间可以点击多次，效果叠加；

如果不点击屏幕，小鸟就会下降一定高度Y。小鸟位于横坐标方向不同位置时，上

升的高度X和下降的高度丫可能互不相同。

4.小鸟高度等于0或者小鸟碰到管道时，游戏失败。小鸟高度为m时，无法

再上升。

现在，请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

【输入】

输入文件名为bird.in。

第1行有3个整数n,mk,分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开；

接下来的n行，每行2个用一个空格隔开的整数X和Y,依次表示在木It坐标位置0~n-1

上玩家点击屏幕后，小鸟在下一位置上升的高度X,以及在这个位置上玩家不点击屏幕时，

小鸟在下一位置下降的高度丫。

接下来k行，每行3个整数巳L,H每两个整数之间用一个空格隔开。每行表示一个管道，其中P表示管道的横坐标，L表示此管道缝隙的下边沿高度为L,H表示管道缝隙上

边沿的高度（输入数据保证P各不相同，但不保证按照大小顺序给出）。

【输出】

输出文件名为bird.out。

共两行。

第一行，包含一个整数，如果可以成功完成游戏，则输出1,否则输出0。

第二行，包含一个整数，如果第一行为1,则输出成功完成游戏需要最少点击屏幕数,

否则，输出小鸟最多可以通过多少个管道缝隙。【问题描述】

FlappyBird是一款风靡一时的休闲手机游戏。玩家需

要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。

为了简化问题，我们对游戏规则进行了简化和改编：

1 .游戏界面是一个长为n,高为m的二维平面，其中有k个管道（忽略管道的宽度）。

2 .小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。

3 .小鸟每个单位时间沿横坐标方向右移的距离为1,

竖直移动的距离由玩家控制。如

【输入输出样例1】

bird.in bird.out

10106 1

39 6

99

12

13

12

11

21

21

16

22

127

515

635

758

879

913

【输入输出样例2】

bird.in bird.out

10104

12

31

22

1 8

2 8

32

3 1

4 1

5 2

12

102

679

914

3810 0

3

【输入输出样例说明】

如下图所示，蓝色直线表示小鸟的飞行轨迹，红色直线表示管道。

输入输出样例1说明输入输出样例2说明

【数据范围】

对于30%勺数据：5wnwi0,5

对于50%勺数据：5

对于70%勺数据：5

对于100%勺数据：5WnW10000,5wmci000,0

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,中间用一个空格隔开，分别代表路口的坐

标(x,y)以及该路口公共场所的数量。同一坐标只会给出一次。

【输出】

输出文件名为wireless.out。

输出一行，包含两个整数，用一个空格隔开，分别表示能覆盖最多公共场所的安装地点方案数，以及能覆盖的最多公共场所的数量。

【输入输出样例】

wireless.in wireless.out

1 130

2

4410

6620

【数据说明】

对于100%勺数据，1&d<20,1&nW20,0WxW128,0

2.寻找道路

(road.cpp/c/pas)

【问题描述】

在有向图G中，每条边的长度均为1,现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以

合集下载

NOIP2014普级组复赛试题

NOIP2014普级组复赛试题

CCF全国信息学奥林匹克联赛 （NOIP2014）复赛

普及组

（请选手务必仔细阅读本页内容）

•题目概况

中文题目名称 珠心算测试 比例简化 螺旋矩阵 子矩阵

英文题目与子目录名 cou nt ratio matrix submatrix

可执行文件名 cou nt ratio matrix submatrix

输入文件名 cou nt.in ratio.in matrix.in submatrix.i n

输出文件名 cou nt.out ratio.out matrix.out submatrix.out

每个测试点时限 1秒 1秒 1秒 1秒

测试点数目 10 10 10 20

每个测试点分值 10 10 10 5

附加样例文件 有 有 有 有

结果比较方式 全文比较（过滤行末空格及文末回车）

题目类型 传统 传统 传统 传统

运行内存上限 128M 128M 128M 128M

•提交源程序文件名

对于C++语言 cou nt.cpp ratio.cpp matrix.cpp submatrix.cpp

对于C语言 cou nt.c ratio.c matrix.c submatrix.c

对于pascal语言 cou nt.pas ratio.pas matrix.pas submatrix.pas

三•编译命令（不包含任何优化开关）

对于C++语言 g++ -o cou nt cou

nt.cpp -lm g++ -o ratio ratio.cpp

-lm g++ -o matrix

matrix.cpp -lm g++ -o submatrix

submatrix.cpp -lm

对于C语言 gcc -o cou nt

cou nt.c -lm gcc -o ratio ratio.c

-lm gcc -o matrix

matrix.c -lm gcc -o submatrix

冲刺NOIP2009普及组模拟测试题

冲刺NOIP2009普及组模拟测试题

冲刺NOIP2009普及组模拟测试题

题1:分数(mark)

源程序名:mark.pas/c/cpp

输入文件名:mark.in

输出文件名:mark.out

时限:1秒

问题描述:

高考分数刚刚公布。共有n人参加考试，为了便于填报志愿，教育部把所有考生的成绩平均分为m档。保证n是m的倍数。考试成绩名次在(k-1)*(n/m)+1名到k*(n/m)名的考生被分在第k档(k=1，2，3„m)。并列第i名的所有考生都算第i名。小Y刚参加完高考.迫切想知道自己被分在第几档，你能帮助他吗?

输入格式:

第一行两个整数n,m≤1000，保证。是m的倍数。

接下来n行，每行一个整数Ai，表示第i个考生的成绩。

最后一行，一个整数x，l≤x≤n，表示询问第i个考生被分在哪一档。

输出格式:

一行一个数，表示它被分在哪一档。

样例输入:

3 3

632

651

624

3

样例输出:

3

题2:背单词(words)

源程序名:words.pas/c/cpp

输入文件名:words.in

输出文件名:words.out

时限.1秒

问题描述:

英语四级考试临近了，小Y却发现他已经把以前学的单词几乎忘光了。好在现在离考试还有一段时间，小Y决定从现在开始夜以继日地背单词。也就是说小Y废寝忘食，一天二十四小时地背单词。

今天的日期(时间)是YYYY年mm月dd日hh时min分，考试的时间是YYYY’年mm’月dd’日hh’时min’分。这之间的所有时间小Y都用来背单词了，那么考试之前他最多能背多少个单词呢? 时间紧张，小Y只管数量不管质量。当然有的单词长一些，有的单词短一些。长的单词难背一些，短的单词好背一些。根据小Y的经验，他能一眼看出背某一个单词需要的时间，以分钟记。

noip2014普及组复赛题解

noip2014普及组复赛题解

百度文库 - 让每个人平等地提升自我

1 1. 珠心算测验

注意看清题意：其中有多少个数，恰好等于集合中另外两个(不同的)数之和。这样的题意加上100的规模，建议暴力3个for:

#include #include #include #include using namespace std; int n; int a[105]; int main(){ freopen("count.in","r",stdin); freopen("count.out","w",stdout); scanf("%d",&n); for(int i=1; i<=n; i++){ scanf("%d",&a[i]); } sort(a+1,a+n+1); int res=0; for(int i=1; i<=n; i++){ int ok=0; for(int j=1; j<=n && !ok; j++) if(j!=i){ for(int k=1; k<=n && !ok; k++) if(a[k]!=a[j]){ if(a[j]+a[k]==a[i]) ok=1; } } res+=ok; } printf("%d\n",res); return 0; }

2. 比例简化

L很小，还是枚举，然后比较的话建议用乘法比较，避免精度问题：

#include #include #include using namespace std; int A,B,L; int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); } int main(){ freopen("ratio.in","r",stdin); freopen("ratio.out","w",stdout); scanf("%d%d%d",&A,&B,&L); int ba=1000000,bb=1; for(int i=1; i<=L; i++){ for(int j=1; j<=L; j++){ if(gcd(i,j)==1 && i*B>=j*A){ 百度文库 - 让每个人平等地提升自我

NOIP复赛题集

NOIP复赛题集

文件的操作

1.概念:在C语言中将文件理解为一个字节流或二进制流.

2.类型定义:和其他类型的变量一样,如int ,long,float,char等,文件类型的变量也需要定义,一般情况下,是以指针的方式进行定义.指针的位置确定文件当前的位置.

定义: FILE *fp; //定义了一个文件类型的指针,这个指针的作用是指向某个特定文件的当前位置(内存).

3.文件的打开和关闭:

a.文件的打开: 使用fopen函数,函数的使用方法描述如下:

FILE * fp;

fp=fopen(文件名,使用文件方式); //fopen函数返回一个指向某特定文件的指针

说明: 文件名表示要打开或创建的文件所在的磁盘路径.

特别指出: (1). 如果文件与程序文件在同一目录下时,不用写出具体的路径;

例如: 文件apple.in和我们的程序apple.cpp位于同一目录时,可以这样写:

FILE *fp=fopen(“apple.in”,”r”);

(2).如果文件位于某一指定地方时,需要写出具体的路径;

例如: 文件apple.in位于d:\c\,那么应该写成:

FILE *fp=fopen(“d:\\c\\apple.in”,”r”);注意表示路径的”\”号,必须以”\\”来表示

(3)使用文件的方式：”r” (读)和”w”(写)

说明：如果文件以”r”（读）的形式打开时，文件必须要存在，否则会引发错误。

如果文件以”w”(写)的形式打开时，如果文件文件不存在，该函数会自动创建新文件。

b.文件的关闭: 每次使用完文件后必须使用fclose函数将文件关闭,具体用法:

fclose(文件指针);

4.文件的读和写

什么是读:读就是将文件中的信息读入计算机的内存.一般用于获取文件的信息给变量赋值.

什么是写:将计算机内存的信息写入文件.一般用于将变量的值输入到文件.

文件读函数：fscanf(文件指针，格式字符串，输入表列)；