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

(word完好版)NOIP提高组初赛历年试题及答案阅读题篇,(word完好版)NOIP提高组初赛历年试题及答案阅读题篇,(word完好版)NOIP提高组初赛历年试题及答案阅读题篇,NOIP提高组初赛历年试题及答案阅读题篇程序写果〔共4，每8分，共32分〕程序的最好方法并不是是挨次从到尾。程序不像迷，我没法从末端几找到答案，也不像一本引人入的籍，只要直接翻到褶最多的那几，我就能找到最出色的片断。所以我在程序，最好逐个观察研究每一段代，搞清楚每一段代的往来脉，理解每一段代在程序中所起的作用，而形成一个虚的程序构，并以此基来行。1、分：高下手，逐深入，正确理解程序。2、写讲解：固化、、提已有的理解成就。3、先模：依据代序追踪量，模运算。4、找律：先模几次循后，找出背后的律。5、看功能：从代构和运算果判断程序功能。6、猜算法：有不知道算法，通构和函数猜一猜。7、方法：认识程序本后，一个熟习的方法。大部分人来，写程序是令人高兴的一件事情，人的程序却很难过，很惧怕，情愿自己重写一遍。其到好的程序，就像一篇美文，令人心神怡，豁然爽朗，因背后是一个人的思，甚至整个人生。人的程序不能够牢固自己的知，启自己的思，提高自己的涵养，你收，其，也是在学、在、在工作中的最重要、最常用的根本功。假如写程序是把自己的思化代，程序就是把代化你理解的人的思。当你程序有烈的代入感，像演一，真实入到的精神世界，面部表情也随之日丰富起来。祝你！你通关了！之，看得多，得多，拼得多，你就考得多⋯⋯NOIP2021-1．#include<iostream>#include<cstring>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<<i<<endl;return0;}输入：1145664332321一步步模拟，注意输出的是sum高出循环条件时的i值〔中位数〕，而不是sum，也不是a[x]输出：3NOIP2021-2．#include<iostream>usingnamespacestd;intn;voidf2(intx,inty);voidf1(intx,inty){if(x<n)f2(y,x+y);}voidf2(intx,inty){cout<<x<<'';f1(y,x+y);}intmain(){cin>>n;f1(0,1);return0;}输入：30此为简单的递归题，挨次输出f2(x,y)中的x值，注意界限条件时f1(x,y)的x>=30咦！这不是隔一个输出一个的Fibonacci吗？输出：1251334NOIP2021-3．#include<iostream>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<<ans<<endl;return0;}输入：46121023203430414013502460一看就知这是深搜算法〔DFS〕，输入是个四个极点的无向图〔毗邻矩阵以下〕：如

len>ans

，那么ans=len

，能够说明这是个在图顶用

DFS

找最长的路径的程序。

DFS

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

4个点，最多就走

3

条边，看看最长的那

3条，结果以以下图：输出：150NOIP2021-4．#include<iostream>#include<cstring>#include<string>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<<sum<<endl;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。输出：57344NOIP2021-1.#include<iostream>usingnamespacestd;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]<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];cout<<sum/(n-2)<<endl;return0;}输入：84070507020401030两轮冒泡，掐头去尾，求均值。数据量不大，就直接模拟吧，速度也挺快的。输出：41NOIP2021-2.#include<iostream>usingnamespacestd;intn,i,ans;intgcd(inta,intb){if(a%b==0)returnb;elsereturngcd(b,a%b);}intmain(){cin>>n;ans=0;for(i=1;i<=n;i++)if(gcd(n,i)==i)ans++;cout<<ans<<endl;return0;}输入：120gcd就是求最大条约数，假如gcd(n,i)==i那么计数，即求120的因子数。输出：16NOIP2021-3.#include<iostream>usingnamespacestd;constintSIZE=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<<ans<<endl;return0;}输入：8持续模拟，while语句中函数调用仔细点即可。输出：7输入：2021对前面的模拟进行察看，得出以下规律后计算：i=2021=512+256+128+64+16+8+4data[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输出：2004NOIP2021-4.#include<iostream>#include<string>usingnamespacestd;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);cout<<ans<<endl;}//输出递归函数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);}输入：ABCDEFBCAEDF这是二叉树的遍历题，先依据两个输入的遍历序列确立二叉树。再依据递归函数计算六个结点深度*权值之和:ans=1*1+2*2+3*3+4*2+5*3+6*3输出：55NOIP2021-1.#include<iostream>#include<string>usingnamespacestd;intmain(){stringStr;cin>>str;intn=str.size();boolisPlalindrome=true;for(inti=0;i<n/2;i++){if(str[i]!=str[n-i-1])}

isPlalindrome=false;if(isPlalindrome)cout<<〞Yes〞<<endl;elsecout<<〞No〞<<endl;}输入：abceecba判断输入的能否是一个回文串，字符串左右颠倒，结果不变。输出：YesNOIP2021-2.#include<iostream>usingnamespacestd;intmain(){inta,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;return0;}输入：1100010151-1000范围内同时是10、15的倍数有多少？注意去重。输出：133NOIP2021-3.#include<iostream>usingnamespacestd;intmain(){constintSIZE=100;intheight[SIZE],num[SIZE],n,ans;cin>>n;for(inti=0;i<n;i++){cin>>height[i];num[i]=1;for(intj=0;j<i;j++){if((height[j]<height[i])&&(num[j]>=num[i]))num[i]=num[j]+1;}}ans=0;for(intI=1;i<n;i++){if(num[i]>ans)ans=num[j];}cout<<ans<<endl;return0;}输入：832511127410求该字符串的最长上涨子序列的长度。输出：4NOIP2021-4.#include<iostream>#include<string>usingnamespacestd;constintSIZE=100;intn,m,p,a[SIZE][SIZE],count;voidcolour(intx,inty){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<n)&&(a[x+1][y]==0))colour(x+1,y);if((y<m)&&(a[x][y+1]==0))colour(x,y+1);}intmain(){inti,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<count)ans<count;}count<<ans<<endl;return0;}输入：6594342413544依据输入的x和y值画出0-1矩阵，再判断同一地区0最多的个数输出：7NOIP2021-1.#include<iostream>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<<tot<<endl;return0;}//统计7-31之间有多少量是3的倍数输入:731输出:8NOIP2021-2.#include<iostream>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<<fun(m,1,n)<<endl;return0;}输入:63递归界限：当n=0时，fun(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,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输出:20NOIP2021-3.#include<iostream>#include<string>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<n;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<<rank[i]<<"";cout<<endl;return0;}输入:7aaaababbbaaaaaacccaa输出:2563471NOIP2021-4.#include<iostream>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<m;j++)num=next(num);cout<<num<<"";alive[num]=0;if(i<n)num=next(num);}cout<<endl;return0;}输入:113这就是约瑟夫环问题，11个人围一圈，从1开始报数，报到3的出局，再从出局的下一个人开始报1，直到所有出局，挨次输出出局人的编号。输出:3691510411827NOIP2021-1.//同普及组阅读题NOIP2021-2#include<iostream>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<<e.c.x<<','<<e.c.y<<endl;return0;}输出:3,2//注意输出有逗号NOIP2021-2.//同普及组阅读题NOIP2021-4#include<iostream>usingnamespacestd;voidfun(char*a,char*b){a=b;(*a)++;}intmain(){charc1,c2,*p1,*p2;c1='A';c2='a';p1=&c1;p2=&c2;fun(p1,p2);cout<<c1<<c2<<endl;return0;}//指针题，注意*a、&a、'a'的差别。输出:AbNOIP2021-3.#include<iostream>#include<string>usingnamespacestd;intmain(){intlen,maxlen;strings,ss;maxlen=0;do{cin>>ss;len=ss.length();if(ss[0]=='#')break;if(len>maxlen){s=ss;maxlen=len;}//输出长度最长的字符串s}while(true);cout<<s<<endl;return0;}输入:IamacitizenofChina#输出:citizenNOIP2021-4.#include<iostream>usingnamespacestd;intfun(intn,intfromPos,inttoPos){intt,tot;if(n==0)return0;for(t=1;t<=3;t++)if(t!=fromPos&&t!=toPos)break;tot=0;tot+=fun(n-1,fromPos,t);tot++;tot+=fun(n-1,t,toPos);returntot;}intmain(){intn;cin>>n;cout<<fun(n,1,3)<<endl;return0;}输入: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,*,*)+1+(0,*,*)=1输出:31NOIP2021-1.#include<iostream>usingnamespacestd;intmain(){inta[6]={1,2,3,4,5,6};intpi=0;intpj=5;intt,i;while(pi<pj){t=a[pi];a[pi]=a[pj];a[pj]=t;pi++;pj--;}for(i=0;i<6;i++)cout<<a[i]<<",";cout<<endl;return0;}//倒序输出，注意逗号输出：6,5,4,3,2,1,NOIP2021-2.#include<iostream>usingnamespacestd;intmain(){chara[100][100],b[100][100];stringc[100];stringtmp;intn,i=0,j=0,k=0,total_len[100],length[100][3];cin>>n;getline(cin,tmp);for(i=0;i<n;i++){getline(cin,c[i]);total_len[i]=c[i].size();//

记录

c[i]

的长度}for(i=0;i<n;i++){j=0;while(c[i][j]!=':'){a[i][k]=c[i][j];//扫描c[i],当c[i]的第j个字符不为":"时，将c[i]的字符存入a[i][k]中，即把c[i]字符串":"前的所有字符存入a[i][k]中，将c[i][0]-->c[i][j]中的字符存入a[i][0]-->a[i][k](k==j)中。k=k+1;j++;}length[i][1]=k-1;记录":"前的字符的个数a[i][k]=0;//记录":"所在的地点k=0;for(j=j+1;j<total_len[i];j++){b[i][k]=c[i][j];//因为j是扫描到":"后的值再+1，所以此时的c[i][j]为":"后输入的字符，并将其存入b[i][k]中k=k+1;}length[i][2]=k-1;记录":"后的字符的个数b[i][k]=0;//记录终点地点k=0;}for(i=0;i<n;i++){if(length[i][1]>=length[i][2])cout<<"NO,";//假如":"前的字符比":"后的字符个数多,输出"NO,"else{k=0;for(j=0;j<length[i][2];j++){if(a[i][k]==b[i][j])假如":"前的字符在":"后有出现k=k+1;找下一个":"前的符能否有出现，是从目前地点今后找if(k>length[i][1])break;//假如k的值比":"前的字符长度大，即已经找完了":"前的所有字符，那么退出循环}if(j==length[i][2])cout<<"NO,";//假如j的值和":"后的字符串长度相等，即在扫描到最后一个点时，不论":"前的字符能否被所有找完，都输出"NO,"elsecout<<"YES,";//假如在找完字符串以前已经找到了":"前的字符，那么输出"YES,"}}cout<<endl;return0;}输入：3AB:ACDEbFBkBDAR:ACDBrTSARS:SevereAtypicalRespiratorySyndrome对！就是判断冒号前的字母能否在冒号后的字符串中出现，大小写要划分，注意有逗号。输出：YES,NO,YES,〔注：输入各行前后均无空格〕NOIP2021-3.#include<iostream>usingnamespacestd;intlps(stringseq,inti,intj){intlen1,len2;if(i==j)return1;//当i=j时，那么此时扫描到的项是必定能够放入该回文子序列中，长度奉献为1if(i>j)return0;//当i>j时，即扫描到的左侧的数在右侧已经扫描