Noip2014初赛提高组C试题及答案

CCF全国信息学奥林匹克联赛(NOIP2014复赛提高组dayl1.生活大爆炸版石头剪刀布(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的得分。

【数据说明】对于100%勺数据，0<N<200,0<NA&200,0<NB&200。

2.联合权值（link.cpp/c/pas）【问题描述】无向连通图G有n个点，n-1条边。

2009-2013年NOIP初赛提高组C++语言试题2013第十九届全国青少年信息学奥林匹克联赛初赛提高组C++语言试题竞赛时间：2013年10月13日14:30~16:30选手注意：试题纸共有12页，答题纸共有2页，满分100分。

请在答题纸上作答，写在试题纸上的一律无效。

不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项）1.一个32位整型变量占用（）个字节。

A.4 B.8 C.32 D.1282.二进制数11.01在十进制下是（）。

A.3.25 B.4.125 C.6.25 D.11.1253.下面的故事与（）算法有着异曲同工之妙。

从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：?从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事....’?A.枚举B.递归C.贪心D.分治4.1948年，（）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。

A.冯·诺伊曼（John von Neumann）B.图灵（Alan Turing）C.欧拉（Leonhard Euler）D.克劳德·香农（Claude Shannon）5.已知一棵二叉树有2013个节点，则其中至多有（）个节点有2个子节点。

A.1006B.1007C.1023D.10246.在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。

右图是一个有5个顶点、8条边的连通图。

若要使它不再是连通图，至少要删去其中的（）条边。

A.2B.3C.4D.57.斐波那契数列的定义如下：F1=1,F2=1,Fn=Fn–1+Fn–2(n≥3)。

如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为（）。

int F(int n){if(n<=2)return 1;elsereturn F(n-1)+F(n-2);})A.O(1)B.O(n)C.O(n2)D.O(Fn8.二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。

第二十届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题2014年一、快单项选择题(共20题，每题1.5分，共计30分；每题有且仅有一个正确选项)⒈以下哪个是面向对象的高级语言( )。

A.汇编语言B.C++C.FortranD.Basic⒉1TB代表的字节数是( )。

A.2的10次方B.2的20次方C.2的30次方D.2的40次方⒊二进制数00100100和00010101的和是( )。

A.00101000B.001010100C.01000101D.00111001⒋以下哪一种设备属于输出设备( )。

A.扫描仪B.键盘C.鼠标D.打印机⒌下列对操作系统功能的描述最为完整的是( )。

A.负责外设与主机之间的信息交换B.负责诊断机器的故障C.控制和管理计算机系统的各种硬件和软件资源的使用D.将没有程序编译成目标程序⒍CPU、存储器、I/O设备是通过( )连接起来的。

A.接口B.总线C.控制线D.系统文件⒎断电后会丢失数据的存储器是( )。

A.RAMB.ROMC.硬盘D.光盘⒏以下哪一种是属于电子邮件收发的协议( )。

A.SMTPB.UDPC.P2PD.FTP⒐下列选项中不属于图像格式的是( )。

A.JPEG格式B.TXT格式C.GIF格式D.PNG格式⒑链表不具有的特点是( )。

A.不必事物估计存储空间B.可随机访问任一元素C.插入删除不需要移动元素D.所需空间与线性表长度成正比⒒下列各无符号十进制整数中，能用八位二进制表示的数中最大的是( )。

A.296B.133C.256D.199⒓下列几个32位IP地址中，书写错误的是( )。

A.162.105.135.27B.192.168.0.1C.256.256.129.1D.10.0.0.1⒔要求以下程序的功能是计算：s=1+1/2+1/3+...+1/10。

#include <iostream>using namespace std;int main(){int n;float s;s = 1.0;for(n = 10; n > 1; n--)s = s + 1 / n;cout << s << endl;return 0;}程序运行后输出结果错误，导致错误结果的程序行是( )。

CCF全国信息学奥林匹克联赛（NOIP2014）复赛提高组day1（请选手务必仔细阅读本页内容）一．题目概况中文题目名称生活大爆炸版石头剪刀布联合权值飞扬的小鸟英文题目与子目录名rps link bird 可执行文件名rps link bird输入文件名rps.in link.in bird.in 输出文件名rps.out link.out bird.out 每个测试点时限1秒1秒1秒测试点数目101020每个测试点分值10105附加样例文件有有有结果比较方式全文比较（过滤行末空格及文末回车）题目类型传统传统传统运行内存上限128M128M128M二．交源程序文件名对于C++语言rps.cpp link.cpp bird.cpp 对于C语言rps.c link.c bird.c 对于pascal语言rps.pas link.pas bird.pas三．编译命令（不包含任何优化开关）对于C++语言g++-o rps rps.cpp–lm g++-o link link.cpp–lmg++-o bird bird.cpp–lm对于C语言gcc-o rps rps.c–lm gcc-o link link.c–lm gcc-o bird bird.c–lm对于pascal语言fpc rps.pas fpc link.pas fpc bird.pas注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。

2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm)64x2Dual Core CPU5200+，2.71GHz，内存2G，上述时限以此配置为准。

4、只供Linux格式附加样例文件。

5、特别提醒：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。

1．生活大爆炸版石头剪刀布(rps.cpp/c/pas)【问题描述】石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。

NOIP2014提高组复赛试题全国信息学奥林匹克联赛(2014)复赛提高组11.生活大爆炸版石头剪刀布()【问题描述】石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。

如果两个人出拳一样，则不分胜负。

在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。

升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势：斯波克：《星际迷航》主角之一。

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

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

表一石头剪刀布升级版胜负关系剪刀石头布蜥蜴人斯波克甲对乙的甲'结果剪刀平输赢赢输石头平输赢输布平输赢蜥蜴人平赢斯波克平现在，小A和小B尝试玩这种升级版的猜拳游戏。

已知他们的出拳都是有周期性规律的，但周期长度不一定相等。

例如：如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为6的周期出拳，那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-……”，而如果小B 以“剪刀-石头-布-斯波克-蜥蜴人”长度为5的周期出拳，那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……”已知小A和小B一共进行N次猜拳。

每一次赢的人得1分，输的得0 分；平局两人都得0 分。

现请你统计N 次猜拳结束之后两人的得分。

【输入】输入文件名为。

第一行包含三个整数：N,,,分别表示共进行N次猜拳、小A出拳的周期长度，小B出拳的周期长度。

数与数之间以一个空格分隔。

第二行包含个整数，表示小A出拳的规律，第三行包含个整数，表示小B出拳的规律。

其中，0表示“剪刀” ,1表示“石头”, 2表示“布”，3 表示“蜥蜴人” ，4 表示“斯波克”。

数与数之间以一个空格分隔。

【输出】输出文件名为。

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

【输入输出样例1】【输入输出样例2】【数据说明】对于100%勺数据，0 2.联合权值()【问题描述】无向连通图G有n个点，1条边。

NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案一、单项选择题（共 15 题，每题 1.5 分，共计 22.5 分；每题有且仅有一个正确选项）1. 从( )年开始，NOIP 竞赛将不再支持 Pascal 语言。

A. 2020B. 2021C. 2022D. 20232.在 8 位二进制补码中，10101011 表示的数是十进制下的( )。

A. 43B. -85C. -43D.-843.分辨率为 1600x900、16 位色的位图，存储图像信息所需的空间为( )。

A. 2812.5KBB. 4218.75KBC. 4320KBD. 2880KB4. 2017年10月1日是星期日，1949年10月1日是( )。

A. 星期三B. 星期日C. 星期六D. 星期二5. 设 G 是有 n 个结点、m 条边(n ≤m)的连通图，必须删去 G 的( )条边，才能使得 G 变成一棵树。

A.m–n+1B. m-nC. m+n+1D.n–m+16. 若某算法的计算时间表示为递推关系式：T(N)=2T(N/2)+NlogNT(1)=1则该算法的时间复杂度为( )。

A.O(N)B.O(NlogN)C.O(N log2N)D.O(N2)7. 表达式a * (b + c) * d的后缀形式是()。

A. abcd*+*B. abc+*d*C. a*bc+*dD. b+c*a*d8. 由四个不同的点构成的简单无向连通图的个数是( )。

A. 32B. 35C. 38D. 419. 将7个名额分给4个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。

A. 60B. 84C. 96D.12010. 若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2，则随着i的增大，f[i]将接近与( )。

A. 1/2B. 2/3D. 111. 设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。

NOIP 提高组初赛历年试题及答案阅读题篇程序写果（共 4 ，每 8 分，共 32 分）程序的最好方法并非是依次从到尾。

程序不像迷，我无法从末尾几找到答案，也不像一本引人入的籍，只需直接翻到褶最多的那几，我就能找到最精彩的片断。

因此我在程序，最好逐一考察研究每一段代，搞清楚每一段代的来去脉，理解每一段代在程序中所起的作用，而形成一个虚的程序构，并以此基来行。

1、分：高入手，逐深入，正确理解程序。

2、写注解：固化、、提已有的理解成果。

3、先模：根据代序跟踪量，模运算。

4、找律：先模几次循后，找出背后的律。

5、看功能：从代构和运算果判断程序功能。

6、猜算法：有不知道算法，通构和函数猜一猜。

7、方法：了解程序本后，一个熟悉的方法。

大多数人来，写程序是令人开心的一件事情，人的程序却很痛苦，很恐惧，宁愿自己重写一遍。

其到好的程序，就像一篇美文，令人心神怡，豁然开朗，因背后是一个人的思，甚至整个人生。

人的程序不可以巩固自己的知，启自己的思，提升自己的修养，你收，其，也是在学、在、在工作中的最重要、最常用的基本功。

如果写程序是把自己的思化代，程序就是把代化你理解的人的思。

当你程序有烈的代入感，像演一，真正入到的精神世界，面部表情也随之日丰富起来。

祝你！你通关了！之，看得多，得多，拼得多，你就考得多⋯⋯NOIP2011-1 ．#include <iostream>#include <cstring>using namespace std;const int SIZE = 100;int main(){int n,i,sum,x,a[SIZE];cin>>n;memset(a,0,sizeof(a));for(i=1;i<=n;i++){cin>>x;a[x]++;}i=0;sum=0;while(sum<(n/2+1)){i++;sum+=a[i];}cout<<i<<endl;return 0;}输入：114 5 6 6 4 3 3 2 3 2 1一步步模拟，注意输出的是sum超出循环条件时的i 值（中位数），而不是sum ，也不是a[x]输出： 3NOIP2011-2 ．#include <iostream> using namespace std; int n;void f2(int x,int y); void f1(int x,int y){if(x<n)f2(y,x+y);}void f2(int x,int y){cout<<x<<' ';f1(y,x+y);}int main(){cin>>n;f1(0,1);return 0;}输入： 30此为简单的递归题，依次输出f2(x,y)中的x值，注意边界条件时f1(x,y)的x>=30咦！这不是隔一个输出一个的Fibonacci吗？输出： 1 2 5 13 34NOIP2011-3 ．#include <iostream>using namespace std; const int V=100;int n,m,ans,e[V][V];bool visited[V];void dfs(int x,intlen){int i;visited[x]= true;if(len>ans)ans=len;for(i=1;i<=n;i++)if( (!visited[i]) &&(e[x][i]!=-1) ) dfs(i,len+e[x][i]);visited[x]=false;}int main(){int i,j,a,b,c;cin>>n>>m;for(i=1;i<=n;i++)for(j=1;j<=m;j++)e[i][j]=-1;for(i=1;i<=m;i++){cin>>a>>b>>c;e[a][b]=c;e[b][a]=c;}for(i=1;i<=n;i++)visited[i]=false;ans=0;for(i=1;i<=n;i++)dfs(i,0);cout<<ans<<endl;return 0;}输入：4 61 2 102 3 203 4 304 1 401 3 502 4 60一看就知这是深搜算法（DFS ），输入是个四个顶点的无向图（邻接矩阵如下）：如len>ans，则 ans=len，可以说明这是个在图中用DFS找最长的路径的程序。

CCF全国信息学奥林匹克联赛（NOIP2014）复赛提高组 day11．生活大爆炸版石头剪刀布(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 rps.out10 5 66 20 1 2 3 40 3 4 2 1 0【输入输出样例2】rps.in rps.out4 49 5 50 1 2 3 41 0 32 4【数据说明】对于100%的数据，0 < N ≤ 200，0 < NA ≤ 200， 0 < NB ≤ 200。

CCF全国信息学奥林匹克联赛（NOIP2014）复赛提高组 day2（请选手务必仔细阅读本页内容）二．ᨀ交源程序文件名三．编译命令（不包含任何优化开关）注意事项：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)以及该路口公共场所的数量。