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

1、NOIP提高组初赛历年试题及答案阅读题篇阅读程序写结果（共4 题，每题8 分，共计32 分）阅读程序的最好方法并非是依次从头到尾。程序不像迷语，我们无法从末尾几页找到答案，也不像一本引人入胜的书籍，只需直接翻到褶皱最多的那几页，我们就能找到最精彩的片断。因此我们在阅读程序时，最好逐一考察研究每一段代码，搞清楚每一段代码的来龙去脉，理解每一段代码在程序中所起的作用，进而形成一个虚拟的程序结构，并以此为基础来进行阅读。1、分层读：高层入手，逐层深入，正确理解程序。2、写注解：固化、总结、提炼已有的理解成果。3、先模拟：根据代码顺序跟踪变量，模拟运算。4、找规律：先模拟

2、几次循环后，找出背后的规律。5、看功能：从代码结构和运算结果判断程序功能。6、猜算法：有时不知道算法，通过结构和函数猜一猜。7、换方法：了解程序本质后，换一个熟悉的方法试试。对大多数人来说，写程序是令人开心的一件事情，读别人的程序却很痛苦，很恐惧，宁愿自己重写一遍。其实读到好的程序，就像读一篇美文，令人心旷神怡，豁然开朗，因为这背后是一个人的思维，甚至整个人生。阅读别人的程序不仅可以巩固自己的知识，启发自己的思维，提升自己的修养，让你收获满满，其实，这也是在学习、在竞赛、在工作中的最重要、最常用的基本功。如果说写程序是把自己的思维转化为代码，读程序就是把代码转化为你理解的别人的思维。当你阅读程

3、序时有强烈的代入感，像演员一样，真正进入到编剧的精神世界，面部表情也随之日渐丰富起来。祝贺你！你通关了！总之，看得多，码得多，拼得多，你就考得多NOIP2011-1#include <iostream>#include <cstring>using namespace std;const int SIZE = 100;int main()int n,i,sum,x,aSIZE;cin>>n;memset(a,0,sizeof(a);for(i=1;i<=n;i+)cin>>x;ax+;i=0;sum=0;while(sum<(n/2+

4、1)i+;sum+=ai;cout<<i<<endl;return 0;输入：114 5 6 6 4 3 3 2 3 2 1一步步模拟，注意输出的是sum超出循环条件时的i值（中位数），而不是sum，也不是ax输出：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,

5、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,eVV;bool visitedV;void dfs(int x,intlen)int i;visitedx= true;if(len>ans)ans=le

6、n;for(i=1;i<=n;i+)if( (!visitedi) &&(exi!=-1) )dfs(i,len+exi);visitedx=false;int main()int i,j,a,b,c;cin>>n>>m;for(i=1;i<=n;i+)for(j=1;j<=m;j+)eij=-1;for(i=1;i<=m;i+)cin>>a>>b>>c;eab=c;eba=c;for(i=1;i<=n;i+)visitedi=false;ans=0;for(i=1;i<=n;i+)

7、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找最长的路径的程序。DFS以任意点作为起点，找一条路径，本次走过的点不走，找到没路走为止。由于就4个点，最多就走3条边，看看最长的那3条，结果如下图：输出：150NOIP2011-4#include <iostream>#include <cstring>

8、#include <string>using namespace std;const int SIZE=10000;const int LENGTH=10;int n,m,aSIZELENGTH;int h(int u,int v)int ans,i;ans=0;for(i=1;i<=n;i+)if( aui!=avi)ans+;return ans;int main()int sum,i,j;cin>>n;memset(a,0,sizeof(a);m=1;while(1)i=1;while( (i<=n) &&(ami=1) )i+;if(

9、i>n)break;m+;ami=1;for(j=i+1;j<=n;j+)amj=am-1j;sum=0;for(i=1;i<=m;i+)for(j=1;j<=m;j+)sum+=h(i,j);cout<<sum<<endl;return 0;输入：7根据while(1)的程序功能模拟几行看看，观察m*n的0-1矩阵，此矩阵其实就是所有7位的二进制数（顺序左右颠倒），m=2n。再根据h(u,v)的程序功能判断出本程序的目的。每一列中有2n-1个1和0，在一列里每个1都有2(n-1)个0与它不同，同样每个0也有2(n-1)个1与它不同，即每列的结果

10、为2(2n-2)*2=2(2n-1)，n列的结果为n*2(2n-1)，所以本题的结果为213*7。输出：57344NOIP2012-1.#include <iostream>using namespace std;int n,i,temp,sum,a100;int main()cin>>n;for (i=1;i<=n;i+)cin>>ai;for (i=1;i<=n-1;i+)if(ai>ai+1)temp=ai;ai= ai+1;ai+1=temp;for (i=n;i>=2;i-)if(ai<ai-1)t

11、emp=ai;ai=ai-1;ai-1=temp;sum=0;for (i=2;i<=n-1;i+)sum +=ai;cout<<sum/(n -2)<<endl;return 0;输入：840 70 50 70 20 40 10 30两轮冒泡，掐头去尾，求均值。数据量不大，就直接模拟吧，速度也挺快的。输出：41NOIP2012-2.#include <iostream>using namespace std;int n,i,ans;int gcd(inta,intb)if(a%b=0)ret

12、urn b;elsereturn gcd(b,a%b);int main()cin>>n; ans=0;for (i=1;i<=n;i+)if(gcd(n,i)= i)ans+;cout<<ans<<endl;return 0;输入：120gcd就是求最大公约数，如果gcd(n,i)= i则计数，即求120的因子数。输出：16NOIP2012-3.#include <iostream>using namespace std;const int SIZE=20;int dataSIZE;int n,i,

13、h,ans;void merge()datah-1=datah-1+datah;h-;ans+;int main()cin>>n;h= 1;datah=1;ans=0;for (i=2;i<=n;i+)h+;datah=1;while(h>1&&datah=datah-1)merge();cout<<ans<<endl;return 0;输入：8继续模拟，while语句中函数调用细心点即可。输出：7输入：2012对前面的模拟进行观察，得出如下规律后计算：i=2012=512+256+128+64+16+8+4即data1=512d

14、ata2=256 data3=128 data4=64 data5=16 data6=8 data7=4ans=512-1+256-1+128-1+64-1+16-1+8-1+4-1=2004输出：2004NOIP2012-4.#include <iostream>#include <string>using namespace std;int lefts20,rights20,father20;string s1,s2,s3;int n,ans;void calc(int x,int dep)ans=ans+dep*(s1x -

15、'A'+1);if(leftsx>=0)calc(leftsx,dep+1);if(rightsx>=0)calc(rightsx,dep+1); /递归函数，返回ans，累计结点深度*结点权值之和void check(int x)if(leftsx>=0)check(leftsx);s3=s3+s1x;if(rightsx>=0)check(rightsx);void dfs(int x,int th)if(th=n)s3=""check(0);if(s3=s2)ans=0;calc(0,1);cout<<ans<

16、<endl; /输出递归函数calc(0,1)的值return;if(leftsx=-1&&rightsx= -1)leftsx=th;fatherth=x;dfs(th,th+1);fatherth= -1;leftsx=-1;if(rightsx= -1)rightsx=th;fatherth=x;dfs(th,th+1);fatherth= -1;rightsx=-1;if(fatherx>=0)dfs(fatherx,th);int main()cin>>s1; /先序遍历序列cin>>s2; /中序遍历序列n= s1.size();

17、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.#include <iostream>#include <string >using namespace  std;int main( )str

18、ing Str;cin>>str;int  n = str.size( );bool  isPlalindrome = true;for (int  i =0; i<n/2;i+)if(stri !=strn-i-1)  isPlalindrome =false;if(isPlalindrome)cout<< ”Yes” << endl;elsecout<< ”No” << endl;输入：abceecba判断输入的是不是一个回文串，字符串左右颠倒，结果不变。输出：YesNOIP

19、2013-2.#include <iostream>using namespace std;int main( )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 <<num<<endl;return  0;输入：1  1000 10 151-1000范围内同时是10、15的倍数有多少？注意去重。输

20、出：133NOIP2013-3.#include <iostream>using namespace std;int main( )const  int SIZE = 100;int  heightSIZE, numSIZE,  n, ans;cin>>n;for  (int i=0;  i<n;  i+) cin>>heighti;numi=1;for  (int j=0;  j<i;  j+) if(heightj

21、<heighti)&&(numj>= numi)numi=numj+1;ans =0;for(int  I = 1; i<n;  i+)if(numi>ans) ans =numj;cout <<ans<<endl;return 0;输入：83 2 5 11 12 7 4 10求该字符串的最长上升子序列的长度。输出：4NOIP2013-4.#include <iostream>#include <string >using namespace  std;const&#

22、160; int  SIZE = 100;int  n,  m, p,  aSIZE SIZE, count;void  colour  (int x,  int  y)Count+;axy = 1;if (x > 1)&&(ax-1y  = 0)colour(x - 1, y);if (y> 1)&&(axy-1  = 0)colour(x, y- 1);if (x < n)&&(ax+1y  =

23、0)colour(x +1, y);if (y < m)&&(axy+1  = 0)colour(x, y+1);int main( )int  i, j,  x,  y, ans;memset(a,  0, sizeof(a);cin >>n>>m>>p;for(i =1 ; I <=p;  i+) cin>>x>>y;axy  = 1;ans  =  0;for  (i =1; i &

24、lt;=n; i+)for  (j =1; j <=m;j+)if(aij  =  0)count  =  0;colour  (i , j);if  (ans <count)ans<count;count<<ans<<endl;return  0;输入：6 5 91 42 32 43 24 14 34 55 46 4根据输入的x和y值画出0-1矩阵，再判断同一区域0最多的个数输出：7NOIP2014-1.#include <iostream>using nam

25、espace std;int main()int a, 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 << tot << endl;return 0; /统计7-31之间有多少数是3的倍数输入: 7  31输出: 8NOIP2014-2.#include <i

26、ostream>using namespace std;int fun(int n, int minNum, int maxNum)int tot, i;if(n = 0)return1;tot= 0;for(i = minNum; i <= maxNum; i+)tot+= fun(n - 1, i + 1, maxNum);returntot;int main()int n, m;cin>> n >> m;cout<< fun(m, 1, n) << endl;return 0;输入: 6  3递归边界：当n=0时，fu

27、n(n,minNum,maxNum)=1fun(3,1,6)=(2,2,6)+(2,3,6)+(2,4,6)+(2,5,6)+(2,6,6)+(2,7,6)=20fun(2,2,6)=(1,3,6)+(1,4,6)+(1,5,6)+(1,6,6)+(1,7,6)=10fun(2,3,6)=(1,4,6)+(1,5,6)+(1,6,6)+(1,7,6)=6fun(2,4,6)=(1,5,6)+(1,6,6)+(1,7,6)=3fun(2,5,6)=(1,6,6)+(1,7,6)=1fun(2,6,6)=(1,7,6)=0fun(1,3,6)=(0,4,6)+(0,5,6)+(0,6,6)+(0,

28、7,6)=4fun(1,4,6)=(0,5,6)+(0,6,6)+(0,7,6)=3fun(1,5,6)=(0,6,6)+(0,7,6)=2fun(1,6,6)=(0,7,6)=1fun(1,7,6)=0输出: 20NOIP2014-3.#include <iostream>#include <string>using namespace std;const int SIZE = 100;int main()string dictSIZE;int rankSIZE;int indSIZE;int i, j, n, tmp;cin >> n;for (i =

29、1; i <= n; i+) ranki = i;indi = i;cin >>dicti;for  (i= 1; i < n; i+)for (j = 1; j<= n - i; j+)if (dictindj> dictindj + 1)tmp = indj;indj = indj +1;indj + 1 = tmp; /冒泡排序for (i = 1; i <= n; i+)rankindi = i; /输出dict里字符排序后应该在的位置for (i = 1; i <= n; i+)cout <<ranki <&

30、lt; " "cout << endl;return 0;输入:7aaaababbbaaaaaacccaa输出: 2 5 6 3 4 7 1NOIP2014-4.#include <iostream>using namespace std;const int SIZE = 100;int aliveSIZE;int n;int next(int num)do num+;if (num > n)num = 1; while (alivenum = 0);return num;int main()int m, i, j, num;cin >&

31、gt; n >> m;for (i = 1; i <= n; i+)alivei = 1;num = 1;for (i = 1; i <= n; i+) for (j = 1; j <m; j+)num = next(num);cout << num<< " "alivenum = 0;if (i < n)num = next(num);cout << endl;return 0;输入: 11 3这就是约瑟夫环问题，11个人围一圈，从1开始报数，报到3的出局，再从出局的下一个人开始报1，直到全部出局，依

32、次输出出局人的编号。输出: 3 6 9 1 5 10 4 11 8 2 7NOIP2015-1. /同普及组阅读题NOIP2015-2#include <iostream>using namespace std;struct point int x;int y;int main()struct EXint a;int b;point c;e;e.a= 1;e.b= 2;e.c.x= e.a + e.b;e.c.y= e.a * e.b;cout<< e.c.x << ',' << e.c.y << endl;retur

33、n 0;输出: 3,2 /注意输出有逗号NOIP2015-2. /同普及组阅读题NOIP2015-4#include <iostream>using namespace std;void fun(char *a, char *b) a = b;(*a)+;int main()char c1, c2, *p1, *p2;c1 = 'A'c2 = 'a'p1 = &c1;p2 = &c2;fun(p1, p2);cout << c1 << c2 << endl;return 0; /指针题，注

34、意*a、&a、'a'的区别。输出: AbNOIP2015-3.#include <iostream>#include <string>using namespace std;int main()int len, maxlen;string s, ss;maxlen = 0;do cin >> ss;len = ss.length();if (ss0 = '#')break;if (len >maxlen) s = ss;maxlen = len;/输出长度最长的字符串s while (true);cout <

35、;< s << endl;return 0;输入:IamacitizenofChina#输出: citizenNOIP2015-4.#include <iostream>using namespace std;int fun(int n, int fromPos, int toPos)int t, tot;if (n = 0)return 0;for (t = 1; t <= 3; t+)if (t != fromPos&& t != toPos)break;tot = 0;tot += fun(n - 1, fromPos, t);tot+

36、;tot += fun(n - 1, t, toPos);return tot;int main()int n;cin >> n;cout << fun(n, 1, 3) << endl;return 0;输入: 5递归边界：当n=0时，fun(n,fromPos,toPos)=0fun(5,1,3)=(4,*,*)+1+(4,*,*)=31fun(4,*,*)=(3,*,*)+1+(3,*,*)=15fun(3,*,*)=(2,*,*)+1+(2,*,*)=7fun(2,*,*)=(1,*,*)+1+(1,*,*)=3fun(1,*,*)=(0,*,*)+

37、1+(0,*,*)=1输出: 31NOIP2016-1.#include <iostream>using namespace std;int main()int a6 = 1, 2, 3, 4, 5, 6;int pi = 0;int pj = 5;intt , i;while (pi < pj) t = api;api = apj;apj = t;pi+;pj-;for (i = 0; i < 6; i+)cout<< ai << ","cout << endl;return 0;/倒序输出，注意逗号输出：6,5

38、,4,3,2,1,NOIP2016-2.#include <iostream>using namespace std;int main()char a100100, b100100;string c100;string tmp;intn, i = 0, j = 0, k = 0, total_len100, length1003;cin >> n;getline(cin, tmp);for (i = 0; i < n; i+) getline(cin, ci);total_leni = ci.size(); /记录ci的长度for (i = 0; i < n

39、; i+) j = 0;while (cij != ':') aik = cij;/扫描ci,当ci的第j个字符不为":"时，将ci的字符存入aik中，即把ci字符串":"前的所有字符存入aik中，将ci0->cij中的字符存入ai0->aik(k=j)中。k = k + 1;j+;lengthi1 = k - 1;/记录":"前的字符的个数aik = 0; /记录":"所在的位置k = 0;for (j = j + 1; j < total_leni; j+) bik = cij

40、;/由于j是扫描到":"后的值再+1，所以此时的cij为":"后输入的字符，并将其存入bik中k = k + 1;lengthi2 = k - 1;/记录":"后的字符的个数bik = 0; /记录终点位置k = 0;for (i = 0; i < n; i+) if (lengthi1 >=lengthi2)cout << "NO," /如果":"前的字符比":"后的字符个数多,输出"NO,"else k = 0;for (j =

41、 0; j < lengthi2;j+) if (aik = bij)/如果":"前的字符在":"后有出现k = k + 1;/找下一个":"前的符是否有出现，是从当前位置往后找if (k > lengthi1)break;/如果k的值比":"前的字符长度大，即已经找完了":"前的所有字符，那么退出循环if (j = lengthi2)cout << "NO,"/如果j的值和":"后的字符串长度相等，即在扫描到最后一个点时，无论&q

42、uot;:"前的字符是否被全部找完，都输出"NO,"elsecout << "YES,"/如果在找完字符串之前已经找到了":"前的字符，那么输出"YES,"cout << endl;return 0;输入：3AB:ACDEbFBkBDAR:ACDBrTSARS:Severe Atypical Respiratory Syndrome对！就是判断冒号前的字母是否在冒号后的字符串中出现，大小写要区分，注意有逗号。输出：YES,NO,YES,（注：输入各行前后均无空格）NOIP2016-3.#include<iostream>using namespace std;int lps(string seq, int i, int j)int len1, len2;if (i = j)return 1;/当i=j时，则此时扫描到的项是一定可以放入该回文子序列中，长度贡献为1if (i &