NOIP提高组初赛历年试题及答案阅读题篇.docx

资源描述

NOIP提高组初赛历年试题及答案阅读题篇.docx

《NOIP提高组初赛历年试题及答案阅读题篇.docx》由会员分享，可在线阅读，更多相关《NOIP提高组初赛历年试题及答案阅读题篇.docx（30页珍藏版）》请在冰点文库上搜索。

NOIP提高组初赛历年试题及答案阅读题篇.docx

NOIP提高组初赛历年试题及答案阅读题篇

阅读程序写结果（共4 题，每题8 分，共计32 分）

阅读程序的最好方法并非是依次从头到尾。

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

因此我们在阅读程序时，最好逐一考察研究每一段代码，搞清楚每一段代码的来龙去脉，理解每一段代码在程序中所起的作用，进而形成一个虚拟的程序结构，并以此为基础来进行阅读。

1、分层读：

高层入手，逐层深入，正确理解程序。

2、写注解：

固化、总结、提炼已有的理解成果。

3、先模拟：

根据代码顺序跟踪变量，模拟运算。

4、找规律：

先模拟几次循环后，找出背后的规律。

5、看功能：

从代码结构和运算结果判断程序功能。

6、猜算法：

有时不知道算法，通过结构和函数猜一猜。

7、换方法：

了解程序本质后，换一个熟悉的方法试试。

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

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

阅读别人的程序不仅可以巩固自己的知识，启发自己的思维，提升自己的修养，让你收获满满，其实，这也是在学习、在竞赛、在工作中的最重要、最常用的基本功。

如果说写程序是把自己的思维转化为代码，读程序就是把代码转化为你理解的别人的思维。

当你阅读程序时有强烈的代入感，像演员一样，真正进入到编剧的精神世界，面部表情也随之日渐丰富起来。

祝贺你！

你通关了！

总之，看得多，码得多，拼得多，你就考得多……

NOIP2011-1．

#include

usingnamespacestd;

constintSIZE=100;

intmain（）

{

intn,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<

return0;

}

输入：

45664332321

一步步模拟，注意输出的是sum超出循环条件时的i值（中位数），而不是sum，也不是a[x]

输出：

NOIP2011-2．

#include

usingnamespacestd;

intn;

voidf2（intx,inty）;

voidf1（intx,inty）

{

if（x

f2（y,x+y）;

}

voidf2（intx,inty）

{

cout<

f1（y,x+y）;

}

intmain（）

{

cin>>n;

f1（0,1）;

return0;

}

输入：

此为简单的递归题，依次输出f2（x,y）中的x值，注意边界条件时f1（x,y）的x>=30

咦！

这不是隔一个输出一个的Fibonacci吗？

输出：

1251334

NOIP2011-3．

#include

usingnamespacestd;

constintV=100;

intn,m,ans,e[V][V];

boolvisited[V];

voiddfs（intx,intlen）

{

inti;

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;

}

intmain（）

{

inti,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<

return0;

}

输入：

1210

2320

3430

4140

1350

2460

一看就知这是深搜算法（DFS），输入是个四个顶点的无向图（邻接矩阵如下）：

如len>ans，则ans=len，可以说明这是个在图中用DFS找最长的路径的程序。

DFS以任意点作为起点，找一条路径，本次走过的点不走，找到没路走为止。

由于就4个点，最多就走3条边，看看最长的那3条，结果如下图：

输出：

150

NOIP2011-4．

#include

usingnamespacestd;

constintSIZE=10000;

constintLENGTH=10;

intn,m,a[SIZE][LENGTH];

inth（intu,intv）

{

intans,i;

ans=0;

for（i=1;i<=n;i++）

if（a[u][i]!

=a[v][i]）

ans++;

returnans;

}

intmain（）

{

intsum,i,j;

cin>>n;

memset（a,0,sizeof（a））;

m=1;

while

（1）

{

i=1;

while（（i<=n）&&（a[m][i]==1））

i++;

if（i>n）

break;

m++;

a[m][i]=1;

for（j=i+1;j<=n;j++）

a[m][j]=a[m-1][j];

}

sum=0;

for（i=1;i<=m;i++）

for（j=1;j<=m;j++）

sum+=h（i,j）;

cout<

return0;

}

输入：

根据while

（1）的程序功能模拟几行看看，观察m*n的0-1矩阵，此矩阵其实就是所有7位的二进制数（顺序左右颠倒），m=2^n。

再根据h（u,v）的程序功能判断出本程序的目的。

每一列中有2^n-1个1和0，在一列里每个1都有2^（n-1）个0与它不同，同样每个0也有2^（n-1）个1与它不同，即每列的结果为2^（2n-2）*2=2^（2n-1），n列的结果为n*2^（2n-1），所以本题的结果为2^13*7。

输出：

57344

NOIP2012-1.

#include

using namespace std;

intn,i,temp,sum,a[100];

intmain（）

{

cin>>n;

for（i=1;i<=n;i++）

cin>>a[i];

for（i=1;i<=n-1;i++）

if（a[i]>a[i+1]）{

temp=a[i];

a[i]=a[i+1];

a[i+1]=temp;

}

for（i=n;i>=2;i--）

if（a[i]

temp=a[i];

a[i]=a[i-1];

a[i-1]=temp;

}

sum=0;

for（i=2;i<=n-1;i++）

sum+=a[i];

cout<

return0;

}

输入：

4070 5070 2040 10 30

两轮冒泡，掐头去尾，求均值。

数据量不大，就直接模拟吧，速度也挺快的。

输出：

NOIP2012-2.

#include

using namespace std;

intn,i,ans;

intgcd（inta,intb）

{

if（a%b==0）

returnb;

else

returngcd（b,a%b）;

}

intmain（）

{

cin>>n;ans=0;

for（i=1;i<=n;i++）

if（gcd（n,i）==i）

ans++;

cout<

return0;

}

输入：

120

gcd就是求最大公约数，如果gcd（n,i）==i则计数，即求120的因子数。

输出：

NOIP2012-3.

#include

using namespace std;

const int SIZE=20;

intdata[SIZE];

intn,i,h,ans;

voidmerge（）

{

data[h-1]=data[h-1]+data[h];

h--;

ans++;

}

intmain（）

{

cin>>n;

h=1;

data[h]=1;

ans=0;

for（i=2;i<=n;i++）

{

h++;

data[h]=1;

while（h>1&&data[h]==data[h-1]）

merge（）;

}

cout<

return0;

}

输入：

继续模拟，while语句中函数调用细心点即可。

输出：

输入：

2012

对前面的模拟进行观察，得出如下规律后计算：

i=2012=512+256+128+64+16+8+4

即data[1]=512data[2]=256data[3]=128data[4]=64data[5]=16data[6]=8data[7]=4

ans=512-1+256-1+128-1+64-1+16-1+8-1+4-1=2004

输出：

2004

NOIP2012-4.

#include

using namespace std;

intlefts[20],rights[20],father[20];

strings1,s2,s3;

intn,ans;

voidcalc（int x,int dep）

{

ans=ans+dep*（s1[x]-'A'+1）;

if（lefts[x]>=0）calc（lefts[x],dep+1）;

if（rights[x]>=0）calc（rights[x],dep+1）;

}//递归函数，返回ans，累计结点深度*结点权值之和

voidcheck（intx）

{

if（lefts[x]>=0）check（lefts[x]）;

s3=s3+s1[x];

if（rights[x]>=0）check（rights[x]）;

}

voiddfs（intx,intth）

{

if（th==n）

{

s3="";

check（0）;

if（s3==s2）

{

ans=0;

calc（0,1）;

cout<

}//输出递归函数calc（0,1）的值

return;

}

if（lefts[x]==-1&&rights[x]==-1）

{

lefts[x]=th;

father[th]=x;

dfs（th,th+1）;

father[th]=-1;

lefts[x]=-1;

}

if（rights[x]==-1）

{

rights[x]=th;

father[th]=x;

dfs（th,th+1）;

father[th]=-1;

rights[x]=-1;

}

if（father[x]>=0）

dfs（father[x],th）;

}

intmain（）

{

cin>>s1;//先序遍历序列

cin>>s2;//中序遍历序列

n=s1.size（）;

memset（lefts,-1,sizeof（lefts））;

memset（rights,-1,sizeof（rights））;

memset（father,-1,sizeof（father））;

dfs（0,1）;

}

输入：

ABCDEF

BCAEDF

这是二叉树的遍历题，先根据两个输入的遍历序列确定二叉树。

再根据递归函数计算六个结点深度*权值之和:

ans=1*1+2*2+3*3+4*2+5*3+6*3

输出：

NOIP2013-1.

#include

usingnamespace std;

intmain（）

{

stringStr;

cin>>str;

int n=str.size（）;

bool isPlalindrome=true;

for（int i=0;i

if（str[i]!

=str[n-i-1]） isPlalindrome=false;

}

if（isPlalindrome）

cout<<”Yes”<

else

cout<<”No”<

}

输入：

abceecba

判断输入的是不是一个回文串，字符串左右颠倒，结果不变。

输出：

Yes

NOIP2013-2.

#include

usingnamespacestd;

intmain（）

{

int a,b,u,v,i,num;

cin>>a>>b>>u>>v;

num =0;

for （i=a;I<=b; i++）

if（（（i%u）==0）||（（i%v）==0））

num++;

count<

return 0;

}

输入：

1 10001015

1-1000范围内同时是10、15的倍数有多少？

注意去重。

输出：

133

NOIP2013-3.

#include

usingnamespacestd;

intmain（）

{

const int SIZE=100;

int height[SIZE], num[SIZE], n,ans;

cin>>n;

for （int i=0; i

cin>>height[i];

num[i]=1;

for （int j=0; j

if（（height[j]=num[i]））

num[i]=num[j]+1;

}

ans=0;

for（int I=1; i

if（num[i]>ans）ans=num[j];

}

cout<

return0;

}

输入：

32511127410

求该字符串的最长上升子序列的长度。

输出：

NOIP2013-4.

#include

usingnamespace std;

const int SIZE=100;

int n, m, p, a[SIZE][SIZE],count;

void colour （int x, int y）

{

Count++;

a[x][y]=1;

if（（x>1）&&（a[x-1][y] ==0））

colour（x-1,y）;

if（（y>1）&&（a[x][y-1] ==0））

colour（x,y-1）;

if（（x

colour（x+1,y）;

if（（y

colour（x,y+1）;

}

intmain（）

{

int i, j, x, y,ans;

memset（a, 0, sizeof（a））;

cin>>n>>m>>p;

for（i=1;I<=p; i++）{

cin>>x>>y;

a[x][y] =1;

}

ans = 0;

for （i=1;i<=n;i++）

for （j=1;j<=m;j++）

if（a[i][j] == 0）{

count = 0;

colour （i,j）;

if （ans

ans

}

count<

return 0;

}

输入：

659

根据输入的x和y值画出0-1矩阵，再判断同一区域0最多的个数

输出：

NOIP2014-1.

#include

usingnamespacestd;

intmain（）

{

inta,b,i,tot,c1,c2;

cin>>a>>b;

tot=0;

for（i=a;i<=b;i++）

{

c1=i/10;

c2=i%10;

if（（c1+c2）%3==0）

tot++; //一个数的各位数之和是3的倍数，它就是3的倍数。

}

cout<

return0;

} //统计7-31之间有多少数是3的倍数

输入:

7 31

输出:

NOIP2014-2.

#include

usingnamespacestd;

intfun（intn,intminNum,intmaxNum）

{

inttot,i;

if（n==0）

return1;

tot=0;

for（i=minNum;i<=maxNum;i++）

tot+=fun（n-1,i+1,maxNum）;

returntot;

}

intmain（）

{

intn,m;

cin>>n>>m;

cout<

return0;

}

输入:

6 3

递归边界：

当n=0时，fun（n,minNum,maxNum）=1

fun（3,1,6）=（2,2,6）+（2,3,6）+（2,4,6）+（2,5,6）+（2,6,6）+（2,7,6）=20

fun（2,2,6）=（1,3,6）+（1,4,6）+（1,5,6）+（1,6,6）+（1,7,6）=10

fun（2,3,6）=（1,4,6）+（1,5,6）+（1,6,6）+（1,7,6）=6

fun（2,4,6）=（1,5,6）+（1,6,6）+（1,7,6）=3

fun（2,5,6）=（1,6,6）+（1,7,6）=1

fun（2,6,6）=（1,7,6）=0

fun（1,3,6）=（0,4,6）+（0,5,6）+（0,6,6）+（0,7,6）=4

fun（1,4,6）=（0,5,6）+（0,6,6）+（0,7,6）=3

fun（1,5,6）=（0,6,6）+（0,7,6）=2

fun（1,6,6）=（0,7,6）=1

fun（1,7,6）=0

输出:

NOIP2014-3.

#include

usingnamespacestd;

constintSIZE=100;

intmain（）

{

stringdict[SIZE];

intrank[SIZE];

intind[SIZE];

inti,j,n,tmp;

cin>>n;

for（i=1;i<=n;i++）{

rank[i]=i;

ind[i]=i;

cin>>dict[i];

}

for （i=1;i

for（j=1;j<=n-i;j++）

if（dict[ind[j]]>dict[ind[j+1]]）{

tmp=ind[j];

ind[j]=ind[j+1];

ind[j+1]=tmp;

}//冒泡排序

for（i=1;i<=n;i++）

rank[ind[i]]=i;//输出dict里字符排序后应该在的位置

for（i=1;i<=n;i++）

cout<

return0;

}

输入:

aaa

aba

bbb

aaa

ccc

输出:

2563471

NOIP2014-4.

#include

usingnamespacestd;

constintSIZE=100;

intalive[SIZE];

intn;

intnext（intnum）

{

do{

num++;

if（num>n）

num=1;

}while（alive[num]==0）;

returnnum;

}

intmain（）

{

intm,i,j,num;

cin>>n>>m;

for（i=1;i<=n;i++）

alive[i]=1;

num=1;

for（i=1;i<=n;i++）{

for（j=1;j

num=next（num）;

cout<

alive[num]=0;

if（i

num=next（num）;

}

cout<

return0;

}

输入:

113

这就是约瑟夫环问题，11个人围一圈，从1开始报数，报到3的出局，再从出局的下一个人开始报1，直到全部出局，依次输出出局人的编号。

输出:

3691510411827

NOIP2015-1.//同普及组阅读题NOIP2015-2

#include

usingnamespacestd;

structpoint{

intx;

inty;

};

intmain（）

{

structEX{

inta;

intb;

pointc;

}e;

e.a=1;

e.b=2;

e.c.x=e.a+e.b;

e.c.y=e.a*e.b;

cout<

展开阅读全文