NOIP提高组初赛历年试题及答案完善题篇(56页)

NOIP提高组初赛历年试题及答案（完善题篇）

完善程序，每年两题，每题每空

2-4

分，共

28

分。

【数学题目】

1

、变量赋初值，如果以后用到的是加减运算，则赋初值

0

；如果以后用到的是

乘除运算，则赋初值为

1

。

2

、循环条件的填空，分析表达式的规律，看表达式中的最后一项的值是否到了

第

m

项或者是第

n

项，如果到了，则在循环中的第二个表达式中用到的是

i<=

或者

i>=

。

3

、循环条件中如果用的是

while

语句，则循环变量的初值应该在

while

的外面

定义和赋初值，在循环语句中必须给变量自加或者是自减，即

i++

或

i--

。

【字符串题目】

1

、把一个数字字符转变成对应的数值的格式是：

ch=’1’-‘0’;

把大写字母转变为小

写字母的格式：

ch=ch+32;

把小写字母转变为大写字母的格式为：

ch=ch-32

。

2

、区分好字符数组中的指针和指针所指的值的关系。在循环语句中，当指针往

后走一个位置的时候，用的是指针的自加，而不是指针所指的值的自加。

【结构体题目】

1

、注意定义结构体变量时的格式。

2

、结构体中成员的调用格式。结构体中的成员分为多种类型，调用结构体中的

成员，使用的是

“.”

或者是

“—>”

运算符。

3

、如果返回的是结构体的话，函数的返回类型必须是结构体类型。调用函数的

格式中，调用的若是结构体数组，则只用写结构体数组名。

【函数题目】

1

、看函数的返回类型，函数的返回类型必须和

return

语句返回的表达式的类型

一致。

2

、函数的调用的情况，函数调用时只用写函数的名称，以及函数的参数。如：

f1(x)

和

f2(x,y)

。

【数组题目】

1

、求一个数值数组中的所有值的平均值和把大于或者小于平均值的数放到另外

一个数组中。首先定义一个变量来存放平均值，如果变量

avg

已经定义但是没

有赋初值，那么这个空填写的内容的为：

avg=0;

2

、求平均值时有两种方法，如果在

for

语句的后面有

avg=avg/N;

则第二个空一

般的填写时

avg+=s[i];

如果说没有

avg=avg/N;

则填写的是：

avg+=s[i]/N

。

3

、二维数组遍历时，使用的是两个循环，使用的是循环的嵌套使用，第二个循

环填写的内容为：

j=0

。

NOIP2011-1.

大整数开方（同普及组

2011-2

）

输入一个正整数n(1≤n≤10^100)，试用二分法计算它的平方根的整数部分。

#include

#include

usingnamespacestd;

constintSIZE=200;

structhugeint{

intlen,num[SIZE];

};

//其中len表示大整数的位数;num[1]表示个位，num[2]表示十位，以此类推

hugeinttimes(hugeinta,hugeintb)

//

计算大整数

a

和

b

的乘积

{

inti,j;

hugeintans;

memset(,0,sizeof());

for(i=1;i<=;i++)

for(j=1;j<=;j++)

[i+j-1]+=[i]*[j];

for(i=1;i<=+;i++){

[i+1]+=[i]/10;

[i]%=10;

}

if([+]>0)

=+;

else

=+-1;

returnans;

}

hugeintadd(hugeinta,hugeintb)

//

计算大整数

a

和

b

的和

{

inti;hugeintans;

memset(,0,sizeof());

if(>)

=;

else

=;

for(i=1;i<=;i++){

[i]+=[i]+[i];

[i+1]+=[i]/10;

[i]%=10;

}

if([+1]>0)

++;

returnans;

}

hugeintaverage(hugeinta,hugeintb)

//计算大整数a和b的平均数的整数部分

{

inti;

hugeintans;

ans=add(a,b);

for(i=;i>=2;i--){

[i-1]+=([i]%2)*10;

[i]/=2;

}

[1]/=2;

if([]==0)

--;

returnans;

}

hugeintplustwo(hugeinta)

//

计算大整数

a

加

2

之后的结果

{

inti;

hugeintans;

ans=a;

[1]+=2;

i=1;

while((i<=)&&([i]>=10)){

[i+1]+=[i]/10;

[i]%=10;

i++;

}

if([+1]>0)

++;

returnans;

}

boolover(hugeinta,hugeintb)

//

若大整数

a>b

则返回

true

，否则返回

false

{

inti;

if(<)

returnfalse;

if(>)

returntrue;

for(i=;i>=1;i--){

if([i]<[i])

returnfalse;

if([i]>[i])

returntrue;

}

returnfalse;

}

intmain()

{

strings;

inti;

hugeinttarget,left,middle,right;

cin>>s;

memset(,0,sizeof());

=();

for(i=1;i<=;i++)

[i]=s[-i]-'0';

memset(,0,sizeof());

=1;

[1]=1;

right=target;

do{

middle=average(left,right);

if(over(times(middle,middle),target))

right=middle;

else

left=middle;

}while(!over(plustwo(left),right));

for(i=;i>=1;i--)

cout<<[i];

return0;

}

NOIP2011-2.

笛卡尔树

对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，

它是一个最小堆，即除了根结点，每个节点的权值都大雨父节点的权值；其次，

它的中序遍历恰好就是给定的序列。例如，对于序列

7

、

2

、

12

、

1

、

10

、

5

、

15

、

3

，下图就是一棵对应的笛卡尔树。现输入序列的规模

n

（

1≤n<100

）和序列的

n

个元素，试求其对应的笛卡尔树的深度

d

（根节点深度为

1

），以及有多少个叶

子节点的深度为

d

。

#include

usingnamespacestd;

constintSIZE=100+5;

constintINFINITY=1000000;

intn,a[SIZE],maxDeep,num;

voidsolve(intleft,intright,intdeep)

{

inti,j,min;

if(deep>maxDeep){

maxDeep=deep;

num=1;

}

elseif(deep==maxDeep)

num++;

min=INFINITY;

for(i=left;i<=right;i++)

if(min>a[i]){

min=a[i];

j=i;

}

if(left

solve(left,j–1,deep+1);

if(j

solve(j+1,right,deep+1);

}

intmain()

{

inti;

cin>>n;

for(i=1;i<=n;i++)

cin>>a[i];

maxDeep=0;

solve(1,n,1);

cout<

return0;

}

NOIP2012-1.

排列数（同普及组

2012-2

）

输入两个正整数

n,m(1≤n≤20,1≤m≤n)

，在

1~n

中任取

m

个数，按字典序

从小到大输出所有这样的排列。例如

输入

:

32

输出

:

12

13

21

23

31

32

#include

#include

usingnamespacestd;

constintSIZE=25;

boolused[SIZE];

intdata[SIZE];

intn,m,i,j,k;

boolflag;

intmain()

{

cin>>n>>m;

memset(used,false,sizeof(used));

for(i=1;i<=m;i++)

{

data[i]=i;

used[i]=true;

}

flag=true;

while(flag)

{

for(i=1;i<=m-1;i++)cout<

cout<

flag=false;

for(i=m;i>=1;i--){

used[data[i]]=false;

for(j=data[i]+1;j<=n;j++)if(!used[j]){

used[j]=true;

data[i]=j;

flag=true;

break;

}

if(flag)

{

for(k=i+1;k<=m;k++)

for(j=1;j<=n;j++)if(!used[j]){

data[k]=j;

used[j]=true;

break;

}

break;

}

}

}

}

NOIP2012-2.

新壳栈

小

Z

设计了一种新的数据结构

“

新壳栈

”

。首先，它和传统的栈一样支持压入、弹

出操作。此外，其栈顶的前

c

个元素是它的壳，支持翻转操作。其中，

c>2

是

一个固定的正整数，表示壳的厚度。小

Z

还希望，每次操作，无论是压入、弹

出还是翻转，都仅用与

c

无关的常数时间完成。聪明的你能帮助她编程实现

“

新

壳栈

”

吗？

程序期望的实现效果如以下两表所示。其中，输入的第一行是正整数c，之后每

行输入都是一条指令。另外，如遇弹出操作时栈为空，或翻转操作时栈中元素不

足c个，应当输出相应的错误信息。

#include

usingnamespacestd;

constintNSIZE=100000,CSIZE=1000;

intn,c,r,tail,head,s[NSIZE],q[CSIZE];

//

数组

s

模拟一个栈，

n

为栈的元素个数

//

数组

q

模拟一个循环队列，

tail

为队尾的下标，

head

为队头的下标

booldirection,empty;

intprevious(intk)

{

if(direction)

return((k+c-2)%c)+1;

else

return(k%c)+1;

}

intnext(intk)

{

if(direction)

return(k%c)+1;

else

return((k+c-2)%c)+1;

}

voidpush()

{

intelement;

cin>>element;

if(next(head)==tail){

n++;

s[n]=q[tail];

tail=next(tail);

}

if(empty)

empty=false;

else

head=next(head);

q[head]=element;

}

voidpop()

{

if(empty){

cout<<"Error:thestackisempty!"<

return;

}

cout<

if(tail==head)

empty=true;

else{

head=previous(head);

if(n>0){

tail=previous(tail);

q[tail]=s[n];

n--;

}

}

}

voidreverse()

{

inttemp;

if(next(head)==tail){

direction=!direction;

temp=head;

head=tail;

tail=temp;

}

else

cout<<"Error:lessthan"<

}

intmain()

{

cin>>c;

n=0;

tail=1;

head=1;

empty=true;

direction=true;

do{

cin>>r;

switch(r){

case1:push();break;

case2:pop();break;

case3:reverse();break;

}

}while(r!=0);

return0;

}

NOIP2013-1.

序列重排

全局数组变量

a

定义如下：

ConstintSIZE=100;

inta[SIZE],n;

它记录着一个长度为n的序列a[1],a[2],…,a[n]。

现在需要一个函数，以整数

p(1≤p≤n)

为参数，实现如下功能：将序列

a

的前

p

个数与后

n–p

个数对调，且不改变这

p

个数（或

n–p

个数）之间的相对位置。

例如，长度为

5

的序列

1,2,3,4,5

，当

p=2

时重排结果为

3,4,5,1,2

。

有一种朴素的算法可以实现这一需求，其时间复杂度为O(n)、空间复杂度为

O(n)：

voidswap1(intp)

{

inti,j,b[SIZE];

for(i=1;i<=p;i++)

b[n–p+i]=a[i];

for(i=p+1;i<=n;i++)

b[i-p]=a[i];

for(i=1;i<=n;i++)

a[i]=b[i];

}

我们也可以用时间换空间，使用时间复杂度为O(n2)、空间复杂度为O(1)的算

法：

voidswap2(intp)

{

inti,j,temp;

for(i=p+1;i<=n;i++){

temp=a[i];

for(j=i;j>=i–p+1;j--)

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

a[i–p]=temp;

}

}

事实上，还有一种更好的算法，时间复杂度为

O(n)

、空间复杂度为

O(1)

：

voidswap3(intp)

{

intstart1,end1,start2,end2,i,j,temp;

start1=1;

end1=p;

start2=p+1;

end2=n;

while(true){

i=start1;

j=start2;

while((i<=end1)&&(j<=end2)){

temp=a[i];

a[i]=a[j];

a[j]=temp;

i++;

j++;

}

if(i<=end1)

start1=i;

elseif(j<=end2){

start1=i

endl=j–1

start2=j;

}

else

break;

}

}

NOIP2013-2.

两元序列

试求一个整数序列中，最长的仅包含两个不同整数的连续子序列。如有多个子序

列并列最长，输出任意一个即可。例如，序列“131”中，有

两段满足条件的最长子序列，长度均为7，分别用下划线和上划线标出。

#include

usingnamespacestd;

intmain()

{

constintSIZE=100;

intn,i,j,a[SIZE],cur1,cur2,count1,count2,

ans_length,ans_start,ans_end;

//cur1,cur2

分别表示当前子序列中的两个不同整数

//count1,count2分别表示cur1,cur2在当前子序列中出现的次数

cin>>n;

for(i=1;i<=n;i++)

cin>>a[i];

i=1;

j=1;

//i,j分别表示当前子序列的首尾，并保证其中至多有两个不同整数

while((j<=n)&&(a[j]==a[i]))

j++;

cur1=a[i];

cur2=a[j];

count1=j-1

count2=1;

ans_length=j-i+1;

while(j

j++;

if(a[j]==cur1)

count1++;

elseif(a[j]==cur2)

count2++;

else{

if(a[j-1]==cur1){

while(count2>0){

if(a[i]==cur1)

count1--;

else

count2--;

i++;

}

cur2=a[j];

count2=1;

}

else{

while(count1>0){

if(a[i]==cur1)

count1--

else

count2--

i++;

}

cur1=a[j]

count1=1;

}

}

if(ans_length

ans_length=j-i+1;

ans_start=i;

ans_end=j;

}

}

for(i=ans_start;i<=ans_end;i++)

cout<

return0;

}

NOIP2014-1.

双栈模拟数组

只使用两个栈结构stack1和stack2，模拟对数组的随机读取。作为栈结构，

stack1和stack2只能访问栈顶(最后一个有效元素)。栈顶指针top1和top2

均指向栈顶元素的下一个位置。

输入第一行包含两个整数，分别是数组长度

n

和访问次数

m

，中间用单个空格

隔开。第二行包含

n

个整数，依次给出数组各项

(

数组下标从

0

到

n-1)

。第三

行包含

m

个整数，需要访问的数组下标。对于每次访问，输出对应的数组元素。

#include

usingnamespacestd;

constintSIZE=100;

intstack1[SIZE],stack2[SIZE];

inttop1,top2;intn,m,i,j;

voidclearStack(){

inti;

for(i=top1;i

stack1[i]=0;

for(i=top2;i

stack2[i]=0;

}

intmain(){

cin>>n>>m;

for(i=0;i>stack1[i];

top1=n;

top2=0;

for(j=0;j

cin>>i;

while(i

top1--;

stack2[top2]=stack1[top1];

top2++;

}

while(i>top1-1){

top2--;

stack1[top1]=stack2[top2];

top1++;

}

clearStack();

cout<

}

return0;

}

NOIP2014-2.最大子矩阵和（同普及组NOIP2014-2）

给出

m

行

n

列的整数矩阵，求最大的子矩阵和

(

子矩阵不能为空

)

。

输入第一行包含两个整数m和n，即矩阵的行数和列数。之后m行，每行n个

整数，描述整个矩阵。程序最终输出最大的子矩阵和。

#include

usingnamespacestd;

constintSIZE=100;

intmatrix[SIZE+1][SIZE+1];

introwsum[SIZE+1][SIZE+1];//rowsum[i][j]记录第i行前j个数的和

intm,n,i,j,first,last,area,ans;

intmain(){

cin>>m>>n;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

cin>>matrix[i][j];

ans=matrix[1][1];

for(i=1;i<=m;i++)

rowsum[i][0]=0;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

rowsum[i][j]=rowsum[i][j-1]+matrix[i][j];

for(first=1;first<=n;first++)

for(last=first;last<=n;last++){

area=0;

for(i=1;i<=m;i++){

area+=rowsum[i][last]-rowsum[i][first-1];

if(area>ans)

ans=area;

if(area<0)

area=0;

}

}

cout<

return0;

}

NOIP2015-1.双子序列最大和

给定一个长度为

n(3≤n≤1000)

的整数序列，要求从中选出两个连续子序列，

使得这两个连续子序列的序列和之和最大，最终只需输出这个最大和。一个连续

子序列的序列和为该连续子序列中所有数之和。要求

:

每个连续子序列长度至少

为

1

，且两个连续子序列之间至少间隔

1

个数。

#include

usingnamespacestd;

constintMAXN=1000;

intn,i,ans,sum;

intx[MAXN];

intlmax[MAXN];

//lmax[i]

为仅含

x[i]

及

x[i]

左侧整数的连续子序列的序列和中，最大的序列和

intrmax[MAXN];

//rmax[i]

为仅含

x[i]

及

x[i]

右侧整数的连续子序列的序列和中，最大的序列和

intmain(){

cin>>n;

for(i=0;i

cin>>x[i];

lmax[0]=x[0];

for(i=1;i

if(lmax[i-1]<=0)

lmax[i]=x[i];

else

lmax[i]=lmax[i-1]+x[i];

for(i=1;i

if(lmax[i]

lmax[i]=lmax[i-1];

rmax[n-1]=x[n-1];

for(i=n-2;i>=0;i--)

if(rmax[i+1]<=0)

rmax[i]=x[i];

else

rmax[i]=rmax[i+1]+x[i];

for(i=n-2;i>=0;i--)

if(rmax[i]

rmax[i]=rmax[i+1];

ans=x[0]+x[2];

for(i=1;i

sum=lmax[i-1]+rmax[i+1];

if(sum>ans)

ans=sum;

}

cout<

return0;

}

NOIP2015-2.

最短路径问题

无向连通图G有n个结点，依次编号为0,1,2,...,(n-1)。用邻接矩阵的形式给

出每条边的边长，要求输出以结点0为起点出发，到各结点的最短路径长度。

使用

Dijkstra

算法解决该问题

:

利用

dist

数组记录当前各结点与起点的已找到

的最短路径长度

;

每次从未扩展的结点中选取

dist

值最小的结点

v

进行扩展，

更新与

v

相邻的结点的

dist

值

;

不断进行上述操作直至所有结点均被扩展，此

时

dist

数据中记录的值即为各结点与起点的最短路径长度。

#include

usingnamespacestd;

constintMAXV=100;

intn,i,j,v;

intw[MAXV][MAXV];//邻接矩阵，记录边长

//其中w[i][j]为连接结点i和结点j的无向边长度，若无边则为-1

intdist[MAXV];intused[MAXV];//记录结点是否已扩展(0:未扩展;1:已扩展)

intmain(){

cin>>n;

for(i=0;i

for(j=0;j

cin>>w[i][j];

dist[0]=0;

for(i=1;i

dist[i]=-1;

for(i=0;i

used[i]=0;

while(true){

v=-1;

for(i=0;i

if(used[i]!=1&&dist[i]!=-1&&(v==-1||dist[i]

v=i;

if(v==-1)

break;

used[v]=1;

for(i=0;i

if(w[v][i]!=-1&&(dist[i]==-1||dist[v]+w[v][i]

dist[i]=dist[v]+w[v][i];

}

for(i=0;i

cout<

return0;

}

NOIP2016-1.交朋友

根据社会学研究表明，人们都喜欢找和自己身高相近的人做朋友。现在有

n

名

身高两两不相同的同学依次走入教室，调查人员想预测每个人在走入教室的瞬间

最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样

时，这名同学会更想和高的那个人做朋友。比如一名身高为

1.80

米的同学进入

教室时，有一名身高为

1.79

米的同学和一名身高为

1.81

米的同学在教室里，

那么这名身高为

1.80

米的同学会更想和身高为

1.81

米的同学做朋友。对于第

一个走入教室的同学我们不做预测。

由于我们知道所有人的身高和走进教室的次序，所以我们可以采用离线的做法来

解决这样的问题，我们用排序加链表的方式帮助每一个人找到在他之前进入教室

的并且和他身高最相近的人。

#include

usingnamespacestd;

#defineMAXN200000

#defineinfinity2147483647

intanswer[MAXN],height[MAXN],previous[MAXN],next[MAXN];

intrank[MAXN];

intn;

voidsort(intl,intr){

intx=height[rank[(l+r)/2]],i=l,j=r,temp;

while(i<=j)

{

while(height[rank[i]]

while(height[rank[j]]>x)j--;

if(i<=j){

temp=rank[i];rank[i]=rank[j];rank[j]=temp;

i++;j--;

}

}

if(i

if(l

}

intmain()

{

cin>>n;

inti,higher,shorter;

for(i=1;i<=n;i++){

cin>>height[i];

rank[i]=i;

sort(1,n);

for(i=1;i<=n;i++){

previous[rank[i]]=rank[i-1];

next[rank[i]]=rank[i+1];

}

for(i=n;i>=2;i--){

higher=shorter=infinity;

if(previous[i]!=0)

shorter=height[i]-height[previous[i]];

if(next[i]!=0)

higher=height[next[i]]-height[i];

if(shorter

answer[i]=previous[i];

else

answer[i]=next[i];

next[previous[i]]=next[i];

previous[next[i]]=previous[i];

}

for(i=2;i<=n;i++)

cout<

return0;

}

NOIP2016-2.交通中断

有一个小国家，国家内有n座城市和m条双向的道路，每条道路连接着两座

不同的城市。其中1号城市为国家的首都。由于地震频繁可能导致某一个城市

与外界交通全部中断。这个国家的首脑想知道，如果只有第i(i>1)个城市因地震

而导致交通中断时，首都到多少个城市的最短路径长度会发生改变。如果因为无

法通过第i个城市而导致从首都出发无法到达某个城市，也认为到达该城市的

最短路径长度改变。

对于每一个城市

i

，假定只有第

i

个城市与外界交通中断，输出有多少个城市会

因此导致到首都的最短路径长度改变。

我们采用邻接表的方式存储图的信息，其中head[x]表示顶点x的第一条边的

编号，next[i]表示第i条边的下一条边的编号，point[i]表示第i条边的终点，

weight[i]表示第i条边的长度。

#include

#include

usingnamespacestd;

#defineMAXN6000

#defineMAXM100000

#defineinfinity2147483647

inthead[MAXN],next[MAXM],point[MAXM],weight[MAXM];

intqueue[MAXN],dist[MAXN],visit[MAXN];

intn,m,x,y,z,total=0,answer;

voidlink(intx,inty,intz){

total++;

next[total]=head[x];

head[x]=total;

point[total]=y;

weight[total]=z;

total++;

next[total]=head[y];

head[y]=total;

point[total]=x;

weight[total]=z;

}

intmain(){

inti,j,s,t;

cin>>n>>m;

for(i=1;i<=m;i++){

cin>>x>>y>>z;link(x,y,z);

}

for(i=1;i<=n;i++)dist[i]=infinity;

dist[1]=0;

queue[1]=1;

visit[1]=1;

s=1;

t=1;

//使用SPFA求出第一个点到其余各点的最短路长度

while(s<=t){

x=queue[s%MAXN];

j=head[x];

while(j!=0){

if(dist[x]+weight[j]

dist[point[j]]=dist[x]+weight[j];

if(visit[point[j]]==0){

t++;

queue[t%MAXN]=point[j];

visit[point[j]]=1;

}

}

j=next[j];

}

visit[x]=0;

s++;

}

for(i=2;i<=n;i++){

queue[1]=1;

memset(visit,0,sizeof(visit));

visit[1]=1;

s=1;

t=1;

while(s<=t){//

判断最短路长度是否不变

x=queue[s];

j=head[x];

while(j!=0){

if(point[j]!=i&&dist[x]+weight[j]==dist[point[j]]

&&visit[point[j]]==0){

visit[point[j]]=1;

t++;

queue[t]=point[j];

}

j=next[j];

}

s++;

}

answer=0;

for(j=1;j<=n;j++)

answer+=1-visit[j];

cout<

}

return0;

}