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

NOIP提高组初赛历年试题及答案阅读题篇阅读程序写结果（共4题，每题8分，共计32分）阅读程序的最好方法并非是依次从头到尾。程序不像迷语，我们无法从末尾几页找到答案，也不像一本引人入胜的书籍，只需直接翻到褶皱最多的那几页，我们就能找到最精彩的片断。因此我们在阅读程序时，最好逐一考察研究每一段代码，搞清楚每一段代码的来龙去脉，理解每一段代码在程序中所起的作用，进而形成一个虚拟的程序结构，并以此为基础来进行阅读。1、分层读：高层入手，逐层深入，正确理解程序。2、写注解：固化、总结、提炼已有的理解成果。3、先模拟：根据代码顺序跟踪变量，模拟运算。4、找规律：先模拟几次循环后，找出背后的规律。5、看功能：从代码结构和运算结果判断程序功能。6、猜算法：有时不知道算法，通过结构和函数猜一猜。7、换方法：了解程序本质后，换一个熟悉的方法试试。对大多数人来说，写程序是令人开心的一件事情，读别人的程序却很痛苦，很恐惧，宁愿自己重写一遍。其实读到好的程序，就像读一篇美文，令人心旷神怡，豁然开朗，因为这背后是一个人的思维，甚至整个人生。阅读别人的程序不仅可以巩固自己的知识，启发自己的思维，提升自己的修养，让你收获满满，其实，这也是在学习、在竞赛、在工作中的最重要、最常用的基本功。如果说写程序是把自己的思维转化为代码，读程序就是把代码转化为你理解的别人的思维。当你阅读程序时有强烈的代入感，像演员一样，真正进入到编剧的精神世界，面部表情也随之日渐丰富起来。祝贺你！你通关了！总之，看得多，码得多，拼得多，你就考得多……NOIP2011-1．#includeiostream#includecstringusingnamespacestd;constintSIZE=100;intmain(){intn,i,sum,x,a[SIZE];cinn;memset(a,0,sizeof(a));for(i=1;i=n;i++){cinx;a[x]++;}i=0;sum=0;while(sum(n/2+1)){i++;sum+=a[i];}coutiendl;return0;}输入：1145664332321一步步模拟，注意输出的是sum超出循环条件时的i值（中位数），而不是sum，也不是a[x]输出：3NOIP2011-2．#includeiostreamusingnamespacestd;intn;voidf2(intx,inty);voidf1(intx,inty){if(xn)f2(y,x+y);}voidf2(intx,inty){coutx'';f1(y,x+y);}intmain(){cinn;f1(0,1);return0;}输入：30此为简单的递归题，依次输出f2(x,y)中的x值，注意边界条件时f1(x,y)的x=30咦！这不是隔一个输出一个的Fibonacci吗？输出：1251334NOIP2011-3．#includeiostreamusingnamespacestd;constintV=100;intn,m,ans,e[V][V];boolvisited[V];voiddfs(intx,intlen){inti;visited[x]=true;if(lenans)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;cinnm;for(i=1;i=n;i++)for(j=1;j=m;j++)e[i][j]=-1;for(i=1;i=m;i++){cinabc;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);coutansendl;return0;}输入：46121023203430414013502460一看就知这是深搜算法（DFS），输入是个四个顶点的无向图（邻接矩阵如下）：如lenans，则ans=len，可以说明这是个在图中用DFS找最长的路径的程序。DFS以任意点作为起点，找一条路径，本次走过的点不走，找到没路走为止。由于就4个点，最多就走3条边，看看最长的那3条，结果如下图：输出：150NOIP2011-4．#includeiostream#includecstring#includestringusingnamespacestd;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;cinn;memset(a,0,sizeof(a));m=1;while(1){i=1;while((i=n)&&(a[m][i]==1))i++;if(in)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);coutsumendl;return0;}输入：7根据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。输出：57344NOIP2012-1.#includeiostreamusingnamespacestd;intn,i,temp,sum,a[100];intmain(){cinn;for(i=1;i=n;i++)cina[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]a[i-1]){temp=a[i];a[i]=a[i-1];a[i-1]=temp;}sum=0;for(i=2;i=n-1;i++)sum+=a[i];coutsum/(n-2)endl;return0;}输入：84070507020401030两轮冒泡，掐头去尾，求均值。数据量不大，就直接模拟吧，速度也挺快的。输出：41NOIP2012-2.#includeiostreamusingnamespacestd;intn,i,ans;intgcd(inta,intb){if(a%b==0)returnb;elsereturngcd(b,a%b);}intmain(){cinn;ans=0;for(i=1;i=n;i++)if(gcd(n,i)==i)ans++;coutansendl;return0;}输入：120gcd就是求最大公约数，如果gcd(n,i)==i则计数，即求120的因子数。输出：16NOIP2012-3.#includeiostreamusingnamespacestd;constintSIZE=20;intdata[SIZE];intn,i,h,ans;voidmerge(){data[h-1]=data[h-1]+data[h];h--;ans++;}intmain(){cinn;h=1;data[h]=1;ans=0;for(i=2;i=n;i++){h++;data[h]=1;while(h1&&data[h]==data[h-1])merge();}coutansendl;return0;}输入：8继续模拟，while语句中函数调用细心点即可。输出：7输入：2012对前面的模拟进行观察，得出如下规律后计算：i=2012=512+256+128+64+16+8+4即data[1]=512data[2]=256data[3]=128data[4]=64data[5]=16data[6]=8data[7]=4ans=512-1+256-1+128-1+64-1+16-1+8-1+4-1=2004输出：2004NOIP2012-4.#includeiostream#includestringusingnamespacestd;intlefts[20],rights[20],father[20];strings1,s2,s3;intn,ans;voidcalc(intx,intdep){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);coutansendl;}//输出递归函数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(){cins1;//先序遍历序列cins2;//中序遍历序列n=s1.size();memset(lefts,-1,sizeof(lefts));memset(rights,-1,sizeof(rights));memset(father,-1,sizeof(father));dfs(0,1);}输入：ABCDEFBCAEDF这是二叉树的遍历题，先根据两个输入的遍历序列确定二叉树。再根据递归函数计算六个结点深度*权值之和:ans=1*1+2*2+3*3+4*2+5*3+6*3输出：55NOIP2013-1.#includeiostream#includestringusingnamespacestd;intmain(){stringStr;cinstr;intn=str.size();boolisPlalindrome=true;for(inti=0;in/2;i++){if(str[i]!=str[n-i-1])isPlalindrome=false;}if(isPlalindrome)cout”Yes”endl;elsecout”No”endl;}输入：abceecba判断输入的是不是一个回文串，字符串左右颠倒，结果不变。输出：YesNOIP2013-2.#includeiostreamusingnamespacestd;intmain(){inta,b,u,v,i,num;cinab