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

《2022年NOIP提高组初赛历年试题及答案阅读题篇 .pdf》由会员分享，可在线阅读，更多相关《2022年NOIP提高组初赛历年试题及答案阅读题篇 .pdf（50页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

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

3、你阅读程序时有强烈的代入感，像演员一样， 真正进入到编剧的精神世界，面部表情也随之日渐丰富起来。祝贺你！你通关了！总之，看得多，码得多，拼得多，你就考得多NOIP2011-1 #include 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 50 页 - - - - - - - - - - vip 会员免费#include using namespace std; const int SIZE = 100; int main() int n,i,sum,x,aSIZE; cinn; memse

4、t(a,0,sizeof(a); for(i=1;ix; ax+; i=0; sum=0; while(sum(n/2+1) i+; sum+=ai; coutiendl; return 0; 输入：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 50 页 - - - - - - - - - - vip 会员免费11 4 5 6 6 4 3 3 2 3 2 1 一步步模拟，注意输出的是sum 超出循环条件时的i 值（中位数），而不是sum ，也不是ax输出： 3NOIP2011-2 #incl

5、ude using namespace std; int n; void f2(int x,int y); void f1(int x,int y) if(xn) f2(y,x+y); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 50 页 - - - - - - - - - - vip 会员免费 void f2(int x,int y) coutxn; f1(0,1); return 0; 输入： 30 此为简单的递归题，依次输出f2(x,y)中的 x 值，注意边界条件时f1(x,y)的

6、x=30 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 50 页 - - - - - - - - - - vip 会员免费咦！这不是隔一个输出一个的Fibonacci吗？输出： 1 2 5 13 34NOIP2011-3 #include 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 50 页 - - - - - - - - - - vip 会员免费using namespace std;

7、 const int V=100; int n,m,ans,eVV; bool visitedV; void dfs(int x,intlen) int i; visitedx= true; if(lenans) ans=len; for(i=1;inm; for(i=1;i=n;i+) for(j=1;j=m;j+) eij=-1; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 50 页 - - - - - - - - - - vip 会员免费for(i=1;iabc; eab=c; eb

8、a=c; for(i=1;i=n;i+) visitedi=false; ans=0; for(i=1;i=n;i+) dfs(i,0); coutansans ，则 ans=len，可以说明这是个在图中用DFS 找最长的路径的程序。DFS 以任意点作为起点，找一条路径，本次走过的点不走，找到没路走为止。由于就4 个点，最多就走 3 条边，看看最长的那3 条，结果如下图：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 50 页 - - - - - - - - - - vip 会员免费输出： 1

9、50NOIP2011-4 #include #include #include 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;in; memset(a,0,sizeof(a); m=1; while(1) i=1; while( (in) break; m+; ami=1; for(j=i+1;j=n;j+) amj=am-1j; 精品资料 - - - 欢迎下载 - - - - -

10、- - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 50 页 - - - - - - - - - - vip 会员免费sum=0; for(i=1;i=m;i+) for(j=1;j=m;j+) sum+=h(i,j); coutsumendl; return 0; 输入： 7 根据 while(1)的程序功能模拟几行看看，观察 m*n的 0-1矩阵，此矩阵其实就是所有7位的二进制数 （顺序左右颠倒），m=2n。再根据 h(u,v) 的程序功能判断出本程序的目的。每一列中有2n-1个 1 和 0，在一列里每个1 都有 2(n-1)个 0 与它不同

11、， 同样每个 0也有 2(n-1)个 1 与它不同，即每列的结果为2(2n-2)*2=2(2n-1)，n 列的结果为n*2(2n-1)，所以本题的结果为213*7。输出： 57344精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 50 页 - - - - - - - - - - vip 会员免费NOIP2012-1. #include using namespace std; int n,i,temp,sum,a100; int main() cinn; for (i=1;iai; for

12、(i=1;iai+1) temp=ai; ai= ai+1; ai+1=temp; for (i=n;i=2;i-) if(aiai-1) temp=ai; ai=ai-1; ai-1=temp; sum=0; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 50 页 - - - - - - - - - - vip 会员免费for (i=2;i=n-1;i+) sum +=ai; coutsum/(n -2)endl; return 0; 输入：8 40 70 50 70 20 40 10

13、30 两轮冒泡，掐头去尾，求均值。数据量不大，就直接模拟吧，速度也挺快的。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 50 页 - - - - - - - - - - vip 会员免费输出： 41精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 50 页 - - - - - - - - - - vip 会员免费NOIP2012-2. #include using namespace st

14、d; int n,i,ans; int gcd(inta,intb) if(a%b=0) return b; else return gcd(b,a%b); int main() cinn; ans=0; for (i=1;i=n;i+) if(gcd(n,i)= i) ans+; coutansendl; return 0; 输入： 120 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 15 页，共 50 页 - - - - - - - - - - vip 会员免费gcd 就是求最大公约数，如果gcd

15、(n,i)= i则计数，即求120的因子数。输出： 16NOIP2012-3. #include using namespace std; const int SIZE=20; int dataSIZE; int n,i,h,ans; void merge() datah-1=datah-1+datah; h-; ans+; int main() cinn; h= 1; datah=1; ans=0; for (i=2;i1&datah=datah-1) merge(); coutansendl; return 0; 输入： 8 继续模拟， while语句中函数调用细心点即可。精品资料 - -

16、 - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 17 页，共 50 页 - - - - - - - - - - vip 会员免费输出： 7 输入： 2012 对前面的模拟进行观察，得出如下规律后计算：i=2012=512+256+128+64+16+8+4 即 data1=512data2=256 data3=128 data4=64 data5=16 data6=8 data7=4 ans=512-1+256-1+128-1+64-1+16-1+8-1+4-1=2004 输出： 2004NOIP2012-4. #inc

17、lude #include using namespace std; int lefts20,rights20,father20; string s1,s2,s3; int n,ans; void calc(int x,int dep) ans=ans+dep*(s1x -A+1); if(leftsx=0)calc(leftsx,dep+1); if(rightsx=0)calc(rightsx,dep+1); /递归函数，返回ans ，累计结点深度*结点权值之和精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - -

18、 -第 18 页，共 50 页 - - - - - - - - - - vip 会员免费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); coutans=0) dfs(fatherx,th); int main() cins1; /先序遍历序列cins2; /中序遍历序列n= s1.size(); 精品资料 - - - 欢迎下载

19、 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 20 页，共 50 页 - - - - - - - - - - vip 会员免费memset(lefts, -1,sizeof(lefts); memset(rights,-1,sizeof(rights); memset(father,-1,sizeof(father); dfs(0,1); 输入：ABCDEF BCAEDF 这是二叉树的遍历题，先根据两个输入的遍历序列确定二叉树。再根据递归函数计算六个结点深度*权值之和 : ans=1*1+2*2+3*3+4*2+5*3+6*3 输出

20、： 55NOIP2013-1. #include #include using namespace std; int main( ) string Str; cinstr; int n = str.size( ); bool isPlalindrome = true; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 21 页，共 50 页 - - - - - - - - - - vip 会员免费for (int i =0; in/2;i+) if(stri !=strn-i-1) isPlalindrom

21、e =false; if(isPlalindrome) cout ” Yes” endl;else cout ” No ” endl; 输入： abceecba 判断输入的是不是一个回文串，字符串左右颠倒，结果不变。输出： YesNOIP2013-2. #include 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 22 页，共 50 页 - - - - - - - - - - vip 会员免费using namespace std; int main( ) int a,b,u,v,i, num; ci

22、nabuv; num =0; for ( i= a; I =b; i+) if(i%u) =0)|(i%v)=0) num +; count numendl; return 0; 输入： 1 1000 10 15 1-1000范围内同时是10 、15的倍数有多少？注意去重。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 23 页，共 50 页 - - - - - - - - - - vip 会员免费输出： 133NOIP2013-3. #include using namespace std; int m

23、ain( ) const int SIZE = 100; int heightSIZE, numSIZE, n, ans; cinn; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 24 页，共 50 页 - - - - - - - - - - vip 会员免费for (int i=0; iheighti; numi=1; for (int j=0; ji; j+) if(heightj= numi) numi=numj+1; ans =0; for(int I = 1; ians) ans =numj

24、; cout ansendl; return 0; 输入：8 3 2 5 11 12 7 4 10 求该字符串的最长上升子序列的长度。输出： 4NOIP2013-4. #include 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 25 页，共 50 页 - - - - - - - - - - vip 会员免费#include using namespace std; const int SIZE = 100; int n, m, p, aSIZE SIZE, count; void colour (i

25、nt 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 = 0) colour(x +1, y); if (y nmp; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 26 页，共 50 页 - - - - - - - - - - vip 会员免费for(i =1 ; I xy; axy = 1; ans = 0;

26、for (i =1; i =n; i+) for (j =1; j =m;j+) if(aij = 0) count = 0; colour (i , j); if (ans count) anscount; countansendl; return 0; 输入：6 5 9 1 4 2 3 2 4 3 2 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 27 页，共 50 页 - - - - - - - - - - vip 会员免费4 1 4 3 4 5 5 4 6 4 根据输入的x 和 y 值画出 0-

27、1矩阵，再判断同一区域0 最多的个数输出： 7NOIP2014-1. #include using namespace std; int main() int a, b, i, tot, c1, c2; cin a b; tot = 0; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 28 页，共 50 页 - - - - - - - - - - vip 会员免费for (i = a; i = b; i+) c1 = i / 10; c2 = i % 10; if (c1 + c2) % 3= 0) t

28、ot+; /一个数的各位数之和是3 的倍数，它就是3 的倍数。 cout tot endl; return 0; /统计 7-31之间有多少数是3 的倍数输入 : 7 31 输出 : 8NOIP2014-2. #include using namespace std; int fun(int n, int minNum, int maxNum) int tot, i; if(n = 0) return1; tot= 0; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 29 页，共 50 页 - - -

29、- - - - - - - vip 会员免费for(i = minNum; i n m; cout fun(m, 1, n) endl; return 0; 输入 : 6 3 递归边界：当n=0时，fun(n,minNum,maxNum)=1 fun(3,1,6)=(2,2,6)+(2,3,6)+(2,4,6)+(2,5,6)+(2,6,6)+(2,7,6)=20 fun(2,2,6)=(1,3,6)+(1,4,6)+(1,5,6)+(1,6,6)+(1,7,6)=10 fun(2,3,6)=(1,4,6)+(1,5,6)+(1,6,6)+(1,7,6)=6 fun(2,4,6)=(1,5,6

30、)+(1,6,6)+(1,7,6)=3 fun(2,5,6)=(1,6,6)+(1,7,6)=1 fun(2,6,6)=(1,7,6)=0 fun(1,3,6)=(0,4,6)+(0,5,6)+(0,6,6)+(0,7,6)=4 fun(1,4,6)=(0,5,6)+(0,6,6)+(0,7,6)=3 fun(1,5,6)=(0,6,6)+(0,7,6)=2 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 30 页，共 50 页 - - - - - - - - - - vip 会员免费fun(1,6,6)

31、=(0,7,6)=1 fun(1,7,6)=0 输出 : 20NOIP2014-3. #include #include using namespace std; const int SIZE = 100; int main() string dictSIZE; int rankSIZE; int indSIZE; int i, j, n, tmp; cin n; for (i = 1; i dicti; for (i= 1; i n; i+) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 31 页，共

32、 50 页 - - - - - - - - - - vip 会员免费for (j = 1; j 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 ; cout endl; return 0; 输入 : 7 aaa aba bbb aaa aaa ccc aa 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下

33、载 名师归纳 - - - - - - - - - -第 32 页，共 50 页 - - - - - - - - - - vip 会员免费输出 : 2 5 6 3 4 7 1NOIP2014-4. #include using namespace std; const int SIZE = 100; int aliveSIZE; int n; int next(int num) do num+; if (num n) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 33 页，共 50 页 - - - - -

34、 - - - - - vip 会员免费num = 1; while (alivenum = 0); return num; int main() int m, i, j, num; cin 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; 精品资料 - - - 欢迎下载 - - - -

35、 - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 34 页，共 50 页 - - - - - - - - - - vip 会员免费输入 : 11 3 这就是约瑟夫环问题，11个人围一圈，从1 开始报数，报到3 的出局，再从出局的下一个人开始报1 ，直到全部出局，依次输出出局人的编号。输出 : 3 6 9 1 5 10 4 11 8 2 7NOIP2015-1. / 同普及组阅读题 NOIP2015-2 #include using namespace std; struct point int x; int y; ; int main() struct

36、 EX int a; int b; point c; e; e.a= 1; e.b= 2; e.c.x= e.a + e.b; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 35 页，共 50 页 - - - - - - - - - - vip 会员免费e.c.y= e.a * e.b; cout e.c.x , e.c.y endl; return 0; 输出 : 3,2 /注意输出有逗号NOIP2015-2. / 同普及组阅读题 NOIP2015-4 #include using namespace

37、 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; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 36 页，共 50 页 - - - - - - - - - - vip 会员免费return 0; /指针题，注意 *a 、&a 、a的区别。输出 : AbNOIP20

38、15-3. #include #include 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 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 37 页，共 50 页 - - - - - - - - - -

39、 vip 会员免费 while (true); cout s endl; return 0; 输入 : I am a citizen of China # 输出 : citizenNOIP2015-4. #include using namespace std; int fun(int n, int fromPos, int toPos) int t, tot; if (n = 0) return 0; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 38 页，共 50 页 - - - - - - - -

40、 - - vip 会员免费for (t = 1; t n; cout fun(n, 1, 3) endl; return 0; 输入 : 5 递归边界：当n=0时，fun(n,fromPos,toPos)=0 fun(5,1,3)=(4,*,*)+1+(4,*,*)=31 fun(4,*,*)=(3,*,*)+1+(3,*,*)=15 fun(3,*,*)=(2,*,*)+1+(2,*,*)=7 fun(2,*,*)=(1,*,*)+1+(1,*,*)=3 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第

41、39 页，共 50 页 - - - - - - - - - - vip 会员免费fun(1,*,*)=(0,*,*)+1+(0,*,*)=1 输出 : 31NOIP2016-1. #include 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; 精品资料 - - - 欢

42、迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 40 页，共 50 页 - - - - - - - - - - vip 会员免费return 0; /倒序输出，注意逗号输出： 6,5,4,3,2,1,NOIP2016-2. #include using namespace std; int main() char a100100, b100100; string c100; string tmp; intn, i = 0, j = 0, k = 0, total_len100, length1003; cin n; getlin

43、e(cin, tmp); for (i = 0; i n; i+) getline(cin, ci); total_leni = ci.size(); /记录 ci 的长度 for (i = 0; i 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; / 由于 j 是扫描到 : 后的值再 +1 ， 所以此时的cij为: 后输入的字符， 并将其存入bik中k = k

44、 + 1; lengthi2 = k - 1; / 记录 : 后的字符的个数bik = 0; /记录终点位置k = 0; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 42 页，共 50 页 - - - - - - - - - - vip 会员免费for (i = 0; i =lengthi2) cout NO,; /如果 : 前的字符比 : 后的字符个数多,输出 NO, else k = 0; for (j = 0; j lengthi1) break; / 如果 k 的值比 : 前的字符长度大，即已

45、经找完了: 前的所有字符，那么退出循环 if (j = lengthi2) cout NO,; / 如果 j 的值和 : 后的字符串长度相等，即在扫描到最后一个点时，无论: 前的字符是否被全部找完，都输出NO, else cout YES,; / 如果在找完字符串之前已经找到了: 前的字符，那么输出YES, 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 43 页，共 50 页 - - - - - - - - - - vip 会员免费 cout endl; return 0; 输入：3 AB:ACDEbF

46、BkBD AR:ACDBrT SARS:Severe Atypical Respiratory Syndrome 对！就是判断冒号前的字母是否在冒号后的字符串中出现，大小写要区分，注意有逗号。输出： YES,NO,YES, （注：输入各行前后均无空格）NOIP2016-3. #include using namespace std; int lps(string seq, int i, int j) int len1, len2; if (i = j) return 1; / 当 i=j 时，则此时扫描到的项是一定可以放入该回文子序列中，长度贡献为1 if (i j) return 0; 精品

47、资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 44 页，共 50 页 - - - - - - - - - - vip 会员免费/ 当 ij 时，即扫描到的左边的数在右边已经扫描过了，所以该项及往后的所有项都是已经扫描过的项，长度贡献为0 if(seqi = seqj) /当扫描到相同的字符时return lps(seq, i + 1, j - 1) + 2; / 此时这两个相同字符必定可以放入回文子序列中，长度贡献为2 len1= lps(seq, i, j - 1); len2= lps(seq, i +

48、 1, j); / 如果没有扫描到相同字符，则此时有两种情况，一种是此时的第i 个字符对最长回文子序列的长度有贡献，另一种是此时的第j 个字符对最长回文子序列的长度有贡献if(len1 len2) return len1; return len2; / 比较上面两种情况的回文子序列的长度大小，返回其中长度较大的回文子序列的长度 int main() string seq = acmerandacm; int n = seq.size(); cout lps(seq, 0, n - 1) endl; return 0; 精品资料 - - - 欢迎下载 - - - - - - - - - - -

49、欢迎下载 名师归纳 - - - - - - - - - -第 45 页，共 50 页 - - - - - - - - - - vip 会员免费/ 对！就是计算最长回文子序列长度输出： 5NOIP2016-4. #include #include using namespace std; int map100100; int sum100, weight100; int visit100; int n; void dfs(int node) visitnode = 1; sumnode = 1; int v, maxw = 0; for (v = 1; v maxw) maxw = sumv;

50、精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 46 页，共 50 页 - - - - - - - - - - vip 会员免费 if (n - sumnode maxw) maxw = n - sumnode; weightnode = maxw; int main() memset(map, 0, sizeof(map); memset(sum, 0, sizeof(sum); memset(weight, 0, sizeof(weight); memset(visit, 0, sizeof(visi