NOIP2012 初赛提高组C++试题及答案

CCF全国信息学奥林匹克联赛（NOIP2012）复赛提高组 day1（请选手务必仔细阅读本页内容）注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。

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

3、全国统一评测时采用的机器配置为：CPU Intel Core2 Quad Q8200 2.33GHz, 内存2G，上述时限以此配置为准。

4、特别提醒：评测在NOI Linux下进行。

1．Vigenère密码(vigenere.cpp/c/pas)【问题描述】16世纪法国外交家Blaise de Vigenère设计了一种多表密码加密算法——Vigenère密码。

Vigenère密码的加密解密算法简单易用，且破译难度比较高，曾在美国南北战争中为南军所广泛使用。

在密码学中，我们称需要加密的信息为明文，用M表示；称加密后的信息为密文，用C表示；而密钥是一种参数，是将明文转换为密文或将密文转换为明文的算法中输入的数据，记为k。

在Vigenère密码中，密钥k是一个字母串，k=k1k2…k n。

当明文M=m1m2…m n时，得到的密文C=c1c2…c n，其中c i=m i®k i，运算®的规则如下表所示：®【输入】输入文件名为vigenere.in。

输入共2行。

第一行为一个字符串，表示密钥k，长度不超过100，其中仅包含大小写字母。

第二行为一个字符串，表示经加密后的密文，长度不超过1000，其中仅包含大小写字母。

【输出】输出文件名为vigenere.out。

输出共1行，一个字符串，表示输入密钥和密文所对应的明文。

对于100%的数据，输入的密钥的长度不超过100，输入的密文的长度不超过1000，且都仅包含英文字母。

2．国王游戏(game.cpp/c/pas)【问题描述】恰逢H国国庆，国王邀请n位大臣来玩一个有奖游戏。

【最新整理，下载后即可编辑】NOIP提高组初赛历年试题及答案求解题篇问题求解题（每次2题，每题5分，共计10分。

每题全部答对得5分，没有部分分）注：答案在文末提高组的问题求解题的知识点大多涉及计数问题、鸽巢原理、容斥问题、逻辑推理、递推问题、排列组合问题等。

NOIP2011-1．平面图可以画在平面上，且它的边仅在顶点上才能相交的简单无向图。

4个顶点的平面图至少有6条边，如图所示。

那么，5个顶点的平面图至多有_________条边。

NOIP2011-2．定义一种字符串操作，一次可以将其中一个元素移到任意位置。

举例说明，对于字符串“BCA”可以将A移到B 之前，变字符串“ABC”。

如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要_________次操作。

NOIP2012-1. 本题中，我们约定布尔表达式只能包含p,q, r三个布尔变量，以及“与”（∧）、“或”（∨）、“非”（¬）三种布尔运算。

如果无论p, q,r如何取值，两个布尔表达式的值总是相同，则称它们等价。

例如，(p∨q)∨r和p∨(q∨r)等价，p∨¬p 和q∨¬q 也等价；而p∨q 和p∧q不等价。

那么，两两不等价的布尔表达式最多有_________个。

NOIP2012-2. 对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。

例如，图1有5个不同的独立集（1个双点集合、3个单点集合、1个空集），图2有14个不同的独立集。

那么，图3有_________个不同的独立集。

NOIP2013-1. 某系统自称使用了一种防窃听的方式验证用户密码。

密码是n个数s1,s2,…,sn，均为0或1。

该系统每次随机生成n个数a1,a2,…,an，均为0或1，请用户回答(s1a1+s2a2+…+snan)除以2的余数。

如果多次的回答总是正确，即认为掌握密码。

该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。

第十八届全国青少年信息学奥林匹克联赛初赛提高组C++语言试题（竞赛时间：2012年10月13日14:30~16:30）一、单项选择题（共10题，每题1.5分，共计15分；每题有且仅有一个正确选项）1.目前计算机芯片（集成电路）制造的主要原料是（），它是一种可以在沙子中提炼出的物质。

A.硅B.铜C.锗D.铝2.（）是主要用于显示网页服务器或者文件系统的HTML文件内容，并让用户与这些文件交互的一种软件。

A.资源管理器B.浏览器C.电子邮件D.编译器3.目前个人电脑的（）市场占有率最靠前的厂商包括Intel、AMD等公司。

A.显示器B.CPUC.内存D.鼠标4.无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。

如果用现实生活中的例子来比喻这些“层”，以下最恰当的是( ）。

A.中国公司的经理与伊拉克公司的经理交互商业文件B.军队发布命令C.国际会议中，每个人都与他国地位对等的人直接进行会谈D.体育比赛中，每一级比赛的优胜者晋级上一级比赛5.如果不在快速排序中引入随机化，有可能导致的后果是（ ）。

A.数组访问越界B.陷入死循环C.排序结果错误D.排序时间退化为平方级6.1946年诞生于美国宾夕法尼亚大学的ENIAC 属于（ ）计算机。

A.电子管B.晶体管C.集成电路D.超大规模集成电路7.在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

A.系统分配的栈空间溢出B.系统分配的堆空间溢出C.系统分配的队列空间溢出D.系统分配的链表空间溢出8.地址总线的位数决定了CPU 可直接寻址的内存空间大小，例如地址总线为16位，其最大的可寻址空间为64KB 。

如果地址总线是32位，则理论上最大可寻址的内存空间为（ ）。

A.128KBB.1MBC.1GBD.4GB9.以下不属于目前3G （第三代移动通信技术）标准的是（ ）。

A.GSMB.TD-SCDMAC.CDMA2000D.WCDMA10.仿生学的问世开辟了独特的科学技术发展道路。

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;}输入：4 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找最长的路径的程序。

2012年全国青少年信息学奥林匹克联赛初赛模拟试题一.单项选择题（共10题,每题1.5分,共计15分,每题有且仅有一个正确答案。

）1、以下说法正确的是（）A、第一个提出“goto语句有害论”的计算机科学家是Donald E.KnuthB、被誉为“迄今最伟大的计算机程序员、算法学家”的是Edsger Wybe DijkstraC、世界上第一位程序员是V on NoumaD、被誉为“计算机语言之母”的是Grace Hopper2、关于CPU的说法正确的是（）A、计算机的运算速度取决于给定的时间内,它的处理器所能处理的数据量。

B、64位计算机指的是CPU每秒钟可处理的数据为2^64位。

C、双核CPU,是指在一个主板上放入两个CPU并行进行工作。

D、我国自主产权的CPU龙芯3A集成了两个处理器核心3、ASCII码表中的大写字母后有6个其它字符,接着便是小写字母。

现已知:A字母的ASCII码为（41）16{表示16进制数41 },那么f应为( )10A、46B、78C、102D、1084、Pascal的创始人是（）。

（A）Donald E.Knuth （B）Steve Jobs （C）Charles Bachman D （D）Niklaus Wirth5、若二叉树的先序遍历序列为ABDECF,中序遍历序列DBEAFC,则其后序遍历序列为（）A. DEBAFCB. DEFBCAC. DEBCFAD. DEBFCA6、已知后缀表达式abc+*d-,则它的中缀表达式和前缀表达式分别是:A） (a+b)*c-d -+*abcd B）a+b*c-d -+a*bcdC）a*(b+c)-d -*a+ bcd D）a*(b+c)-d -a b*+cd7、由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度为（）A.23B.37C.44D.468、排序算法是稳定的意思是:关键码相同的记录排序前后相对位置不发生改变,下列哪种排序算法是不稳定的:A) 冒泡排序 B) 插入排序 C) 归并排序 D) 快速排序9、下图给出了一个加权有向图,从顶点V1出发,以下哪个是活动中的关键路径（）A. V1,V5,V3,V2B. V1,V4,V3,V2C. V1,V4, V2D. V1,V4,V5,V3,V210、以下有关全国信息学奥林匹克竞赛说法有误的是（）A、 NOI评测只检查按照要求输出的结果,而不涉及过程和算法。

NOIP 2012简要题解王赢绪东北师大附中高二二班499167119@2012年11月19日分数分布：Day 1：Problem Contest Current Vigenère密码（vigenere）100 100国王游戏（game）100 100开车旅行（drive）70 100Day 2：Problem Contest Current 同余方程（mod）100 100借教室（classroom）90 100疫情控制（blockade）50 100题解：Day 1：Problem 1 Vigenère密码（vigenere）这是一道模拟题，我的做法的先把密钥都换成大写或者小写。

然后对输入的加密文章进行处理，如果当前对应的密钥位置超过了密钥的总长度，则把当前位置转回1即可，并且注意加密文章的大小写问题。

时间复杂度为O(n+m)，其中n和m分别为两个字符串的长度。

Problem 2国王游戏（game）这道题的主要考察点是高精度乘法除法以及贪心算法的应用。

这是USACO 2007年某次月赛的改编题。

我们不难观察出必存在一种最优的安排方案，是按照每个人左右手两个数的乘积由小到大排序后计算得来，对于乘积相同的我们可以不考虑他们的顺序。

Problem 3开车旅行（drive）这道题我只能想到用平衡树然后倍增维护每个点往前走2的次幂到达哪，以及需要的路程为多少。

具体实现是这样的，我们首先按照站点倒序的顺序进行处理，那么显然每个点离它最近的那个点一定是它高度值的前驱或者后继（如果存在的话），接下来我们考虑每个点的次近点，比如最近点为前驱，那么显然次近点为前驱的前驱或者后继，而如果最近点为后继，则次近点为后继的后继或者前驱。

所以我们可以花O(n log n)的时间处理完成每个点的最近点及次近点。

接下来由于我们已经有了每个点可以到达的最近点及次近点，那么我们可以处理出每个点走2的次幂以后，A走过的路程为多少，B走过的路程为多少，以及此时所在的位置。