NOIP普及组初赛历年试题及答案完善题篇

NOIP普及组初赛历年试题及答案（完善题篇）完善程序，每年两题，每题每空2-4分，共28分。【解题步骤】1、仔细读题，尤其是题目给你的解题思路：解决什么问题？用的什么算法？输入输出是什么？……2、要知道变量的含义，也可通过变量单词的意思知道，比如sum表示和，que表示队列等等。3、在充分了解前两点的基础上，先根据自己的想法大致想想：如果让你实现程序，你会怎么做。4、通读程序，理顺程序结构，千万不要因为程序很长而觉得气馁，有时程序越长，填空越简单。5、按照程序执行的顺序做，遇到难的先放一边，继续往下做。有些空格很简单，一下就能看出来的。6、到这步为止，程序大概意图就知道了，然后就是填比较难的几格了。这一点就靠你对程序的理解了。7、填完了以后，再执行一遍程序，有样例就结合样例，没样例就自己造数据模拟。【解题技巧】1、变量初始化：这个得结合后面的运算确定，不过有些也很简单，如sum=0之类的。2、for循环初、终值：如果是嵌套的循环，可结合父循环或子循环确定。3、更新最优解：比较或赋值。4、要填的空格与某句对应，这样的例子在下面能找到很多。NOIP2011-1.子矩阵给输入一个n1*m1的矩阵a，和n2*m2的矩阵b，问a中是否存在子矩阵和b相等。若存在，输出所有子矩阵左上角的坐标:若不存在输出“Thereisnoanswer”。#includeiostreamusingnamespacestd;constintSIZE=50;intn1,m1,n2,m2,a[SIZE][SIZE],b[SIZE][SIZE];intmain(){inti,j,k1,k2;boolgood,haveAns;cinn1m1;for(i=1;i=n1;i++)for(j=1;j=m1;j++)cina[i][j];cinn2m2;for(i=1;i=n2;i++)for(j=1;j=m2;j++)cinb[i][j];haveAns=false;for(i=1;i=n1-n2+1;i++)for(j=1;j=m1-m2+1;j++){good=true;for(k1=1;k1=n2;k1++)for(k2=1;k2=m2;k2++){if(a[i+k1-1][j+k2-1]!=b[k1][k2])good=false;}if(good){couti''jendl;haveAns=true;}}if(!haveAns)coutThereisnoanswerendl;return0;}NOIP2011-2.大整数开方输入一个正整数n(1≤n≤10^100)，试用二分法计算它的平方根的整数部分。#includeiostream#includestringusingnamespacestd;constintSIZE=200;structhugeint{intlen,num[SIZE];};//其中len表示大整数的位数;num[1]表示个位，num[2]表示十位，以此类推hugeinttimes(hugeinta,hugeintb)//计算大整数a和b的乘积{inti,j;hugeintans;memset(ans.num,0,sizeof(ans.num));for(i=1;i=a.len;i++)for(j=1;j=b.len;j++)ans.num[i+j-1]+=a.num[i]*b.num[j];for(i=1;i=a.len+b.len;i++){ans.num[i+1]+=ans.num[i]/10;ans.num[i]%=10;}if(ans.num[a.len+b.len]0)ans.len=a.len+b.len;elseans.len=a.len+b.len-1;returnans;}hugeintadd(hugeinta,hugeintb)//计算大整数a和b的和{inti;hugeintans;memset(ans.num,0,sizeof(ans.num));if(a.lenb.len)ans.len=a.len;elseans.len=b.len;for(i=1;i=ans.len;i++){ans.num[i]+=a.num[i]+b.num[i];ans.num[i+1]+=ans.num[i]/10;ans.num[i]%=10;}if(ans.num[ans.len+1]0)ans.len++;returnans;}hugeintaverage(hugeinta,hugeintb)//计算大整数a和b的平均数的整数部分{inti;hugeintans;ans=add(a,b);for(i=ans.len;i=2;i--){ans.num[i-1]+=(ans.num[i]%2)*10;ans.num[i]/=2;}ans.num[1]/=2;if(ans.num[ans.len]==0)ans.len--;returnans;}hugeintplustwo(hugeinta)//计算大整数a加2之后的结果{inti;hugeintans;ans=a;ans.num[1]+=2;i=1;while((i=ans.len)&&(ans.num[i]=10)){ans.num[i+1]+=ans.num[i]/10;ans.num[i]%=10;i++;}if(ans.num[ans.len+1]0)ans.len++;returnans;}boolover(hugeinta,hugeintb)//若大整数ab则返回true，否则返回false{inti;if(a.lenb.len)returnfalse;if(a.lenb.len)returntrue;for(i=a.len;i=1;i--){if(a.num[i]b.num[i])returnfalse;if(a.num[i]b.num[i])returntrue;}returnfalse;}intmain(){strings;inti;hugeinttarget,left,middle,right;cins;memset(target.num,0,sizeof(target.num));target.len=s.length();for(i=1;i=target.len;i++)target.num[i]=s[target.len-i]-'0';memset(left.num,0,sizeof(left.num));left.len=1;left.num[1]=1;right=target;do{middle=average(left,right);if(over(times(middle,middle),target))right=middle;elseleft=middle;}while(!over(plustwo(left),right));for(i=left.len;i=1;i--)coutleft.num[i];return0;}NOIP2012-1.坐标统计输入n个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点(即x、y坐标都比它小)，它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号(如果两个点战斗力一样，输出较大的编号)。#includeiostreamusingnamespacestd;constintSIZE=100;intx[SIZE],y[SIZE],f[SIZE];intn,i,j,max_f,ans;intmain(){cinn;for(i=1;i=n;i++)cinx[i]y[i];max_f=0;for(i=1;i=n;i++){f[i]=0;for(j=1;j=n;j++){if(x[j]x[i]&&y[j]y[i];f[i]++;}if(f[i]=max_f){max_f=f[i];ans=i;}}for(i=1;i=n;i++)coutf[i]endl;coutansendl;returno;}NOIP2012-2.排列数输入两个正整数n,m(1≤n≤20,1≤m≤n)，在1~n中任取m个数，按字典序从小到大输出所有这样的排列。例如输入:32输出:121321233132#includeiostream#includecstringusingnamespacestd;constintSIZE=25;boolused[SIZE];intdata[SIZE];intn,m,i,j,k;boolflag;intmain(){cinnm;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++)coutdata[i];coutdata[m]endl;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;}}}}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;}}NOIP2013-2.二叉查找树二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。输入的第一行包含一个整数n，表示这棵树有n个顶点，编号分别为1,2,...,n，其中编号为1的为根结点。之后的第i行有三个数value,left_child,right_child，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点，则用0代替。输出1表示这棵树是二叉查找树，输出0则表示不是。#includeiostreamusingnamespacestd;constintSIZE=100;constintINFINITE=1000000;structnode{intleft_child,right_child,value;};nodea[SIZE];intis_bst(introot,intlower_bound,intupper_bound){intcur;if(root==0)return1;cur=a[root].va