2020CSP普及组第二轮答案.docx

《2020CSP普及组第二轮答案.docx》由会员分享，可在线阅读，更多相关《2020CSP普及组第二轮答案.docx（18页珍藏版）》请在课桌文档上搜索。

1、1.优秀的拆分算法分析奇数不存在优秀的拆分。偶数一定存在优秀的拆分.从大到小枚举2的iii次方，从24到Io如果nnn能被2i2否2i整除,说明2i2Z2i是他的一个拆分项，输出。2i2i2i可以表示为1ililie#include#include#includeusingnamespacestd;intmain()(intn;scanf(%dz&n);if(n%2)printf(-ln);else(for(inti=24;i=1;-i)(if(n/(1i)-1)(n-=(1i);printf(%d,1i);)return0;)123456789101112131415161718192021

2、算法拓展打表。预处理出2i2i2i次方的值，用数组存起来。对每个预处理的值进行标记。倒序枚举nnn,如果枚举的值被标记了，说明他是2i2N2i。可以直接输出，相应的nnn的值也要减去2i2Z2#include#include#includeusingnamespacestd;intb30=0,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216;intv18000000;intmain()(int

3、n;scanf(%d,&n);if(n%2)(printf(-l);return0;)for(inti=1;i=24;+i)vbi=1;intx=n;while(x)(ifMM)printf(%d,x);n=x;else-x;)returnO;)123456789IO111213141516171819202122232425262.直播获奖算法分析每个选手的成绩取值范围是0,6000,6000,600,可以用hash思想。读到一个成绩的时候，就标记一下。然后从600到0倒序枚举分数线统计个数，当个数大于等于获奖人数时退出，此时就是答案。时间复杂度O(60On)O(60On)O(600n),n

4、nn最大为10万，可以过。注意事项：对于P*w%p*w%p*w%的下取整，要注意精度跳变，可以用整除替换：p*w/100p*w/100p*w100.#include#include#include#include#includeusingnamespacestd;intf610;intmain()(intn,w,cntzd;SCanf(%d%d,&n,&w);for(registerintt=1;t=n;+t)(scanf(%d,&d);+fd;/记录该成绩的人数有多少个ent=t*w/100;if(ent=0;-k)(s+=fk;if(s=ent)break;)printf(%d,k);)r

5、eturn0;)123456789101112131415161819202122232425262728算法拓展1.插入排序。由大到小排序，增加一个人时，直接向前邻项交换。由大到小取。排到最后，其实就相当于一遍完整插入排序的时间匏杂度。插入排序时间复杂度不稳定，最坏情况是O(n2)O(n2)O(n2),最好情况是0(n)O(n)O(n),不知道能过多少点。2 .对顶堆。对顶堆可以维护单调区间第k大数或第k小数。本题适用于求第k大数。左边的是小根堆ql,右边的是大根堆q20两者拼接起来就是由大到小。假设该轮的获奖人数为t。第X个选手成绩出来后，如果此时ql的个数小于3则把X丢进ql。如果ql的

6、个数还是小于t,则q2的堆顶出堆，进入ql,直到ql的个数等于t.此时ql的堆顶分数就是答案。入堆和出堆时间复杂度都是IOgIoglog的，整体复杂度0(nIogn)O(nlogn)O(nlogn)03 .表达式算法分析对于后缀表达式的计算，朴素的算法可以借助数字栈。从左到右扫描，遇到数字就入栈，遇到操作符op,从栈中依次弹出两个数字x2和xl,进行运算X10PX21,op,2xlopx2,然后将运算结果再入栈。如果是动态取反某个数字q次查询，这个复杂度就高了，为0(n*q)O(n*q)O(n*q)对于这种改变的地方很少，但是需要整体结果的，就需要考虑将改变的影响降到最少。表达式树。建立表达式

7、树的时候还得借助栈。在表达式中，数字都是叶结点，运算符都是非叶结点。叶结点的编号按照Ln进行，运算符按照从左到右的顺序在n的基础上分别加1。结点开结构体，存父节点、左右儿子、值、字符。structnode(intparzIchild,rchildzdata;charc;stree1000010;12345字符串用getchargetchargetchar读入。当读入XXX的时候，后面跟的就是数字，把数字处理出来，然后建立结点并入栈。当读入！!的时候，建立结点，栈顶的结点作为该结点的左儿子。当读入&和III时，建立结点，栈顶的结点分别作为他们的右儿子和左儿子。这样就建成了表达式树。根结点的值就是

8、整体结果。查询时。取反的结点都是叶结点。只需要改变该叶结点到根结点之间的结点的值就可以了。如果数据是随机的，每次查询的平均复杂度就是IogIoglog级别的。一个很重要的优化：当某个结点的值和原先的值相同时，则直接返回根节点的值。本题有特殊数据，以下代码官方数据能得95分。#include#include#includeusingnamespacestd;chars1000010;inta100010zn,ent,sstack1000010,stop;structnode(intpar,Ichild,rchildzdata;charc;stree1000010;intmain()(intIen

9、=O;while(s+len=getchar()!=,n,);slen=32;scanf(%d,&n);for(inti=1;i=n;+i)scanf(%dz&ai);ent=n;for(inti=1;i=len;+i)(if(si=1,)(intsnum=Ozt=i+1;while(st!=32)(snum=snum*10+st-,0,;+t;)sstack+stop=snum;streesnum.data=asnum;streesnum.c=asnum+0,;elseif(si=!)(stree+cnt.Ichild=sstackstop;-stop;streestreecnt.Ichil

10、d.par=ent;streecnt.data=!streestreecnt.Ichild.data;streecnt.c=!,;sstack+stop=ent;elseif(si=&)(stree+cnt.rchild=sstackstop;-stop;streecnt.Ichild=sstackstop;-stop;streestreecnt.Ichild.par=ent;streestreecnt.rchild.par=ent;streecnt.data=streestreecnt.Ichild.data&streestreecnt.rchild.data;streecnt.c=ssta

11、ck+stop=ent;elseif(si=)(stree+cnt.rchild=sstackstop;-stop;streecnt.Ichild=sstackstop;-stop;streestreecnt.Ichild.par=ent;streestreecnt.rchild.par=ent;streecnt.data=streestreecnt.Ichild.datastreestreecnt.rchild.data;streecnt.c=;sstack+stop=ent;)intq;scanf(%d,z&q);while(q-)(intt;scanf(%d,&t);intp,sres=

12、!at;while(1)(p=street.par;if(streep.c=!)sres=!sres;elseif(streep.c=&)(if(streep.Ichild=t)sres=sres&streestreep.rchild.data;elsesres=sres&streestreep.lchild.data;Jelseif(streep.c=|)if(streep.Ichild=t)sres=sresstreestreep.rchild.data;elsesres=sresstreestreep.Ichild.data;)if(sres=streep.data)(sres=stre

13、ecnt.data;break;)t=p;if(street.par=0)break;)printf(%dnzsres);)123456789101112131415161718192021222324252627282930returnO;3132333435363738394041424344454647484950515253545556575859606162636465666768697071727375767778798081828384858687以上表达式树不是平衡树，有3种特殊情况会过不了。1 .全都是！!或大部分是。树退化成了链。2 .全都是&或大部分是。树几乎退化成了链。

14、3 .全都是III或大部分是。树几乎退化成了链。如下图：在上述过程中，我们可以发现，某些点的值无论怎么变，都不会影响最终的结果。比如0&a0A&Va0&a,aaa的值无论怎么改变都不会影响结果，此时我们可以给值为aaa的这个点打个标记。相似的还有1IaIVIValIa。建立表达式树后，从根结点开始向下O(n)O(n)O(n)的复杂度就可以完成打标记。如果一个叶结点到跟结点的路径上，有一个点被打标记了，那么该结点也要被打标记，即标记可以下传。这样我们最终只要判断取反的叶结点是否打了标记。如果打标记了，则结果为根结点的值。如果没打标记，则结果为根结点的值取反。为什么？假设取反的叶结点没有打标记，则

15、该叶结点到根结点的路径上都没有打标记。则该叶结点的父结点的值就要取反，该父结点的父结点的值也要取反，依次类推，到根结点之间包含根结点的值都要取反。查询的更杂度是O(I)0(l)0(l)o#include#include#include#includeusingnamespacestd;chars1000010;inta100010,n,ent,sstack1000010,stop;structnode(intIchild,rchild,data,tag;charc;stree1000010;voidprint_tag(intt)(if(street.Ichild=0&street.rchild

16、=0)return;/叶结点if(street.tag=1)(streestreet.lchild.tag=streestreet.rchild.tag=1;elseif(street.c=&)(if(streestreet.IchiId.data=O)streestreet.rchild.tag=1;if(streestreet.rchild.data=O)streestreet.lchild.tag=1;elseif(street.c=)(if(streestreet.IchiId.data=1)streestreet.rchild.tag=1;if(streestreet.rchild.

17、data=1)streestreet.lchild.tag=1;)print-tag(street.Ichild);print_tag(street.rchild);)intmain()(intIen=O;while(s+len=getchar()!=,n,);slen=32;scanf(%d,&n);for(inti=1;i=n;+i)scanf(%dz&ai);ent=n;for(inti=1;i=len;+i)(if(si=1,)(intsnum=Ozt=i+1;while(st!=32)(snum=snum*10+st-,0,;+t;)i=t;sstack+stop=snum;stre

18、esnum.data=asnum;streesnum.c=asnum+0;elseif(si=!)(stree+cnt.Ichild=sstackstop;-stop;streecnt.data=!streestreecnt.Ichild.data;streecnt.c=sstack+stop=ent;elseif(si=&)(stree+cnt.rchild=sstackstop;-stop;streecnt.Ichild=sstackstop;-stop;streecnt.data=streestreecnt.Ichild.data&streestreecnt.rchild.data;st

19、reecnt.c=sstack+stop=ent;elseif(si=,)(stree+cnt.rchild=sstackstop;-stop;streecnt.Ichild=sstackstop;-stop;streecnt.data=streestreecnt.Ichild.datastreestreecnt.rchild.data;streecnt.c=,;sstack+stop=ent;)print_tag(cnt);/打标记，打上标记的结点，值是否改变，对结果不影响intans=streecnt.data;intq;scanf(%dz&q);while(q-)(intt;scanf(

20、%dz&t);if(street.tag=0)printf(%dn,!ans);elseprintf(%dnzans);)12345678910111213141516return0;171819202122232425262728293031323334353637383940414243444546474849505152535455565758596162636465666768697071727374757677787980818283844 .方格取数算法分析这种矩阵上求最值的题目，dp无疑了。但是每次可以向上、向下和向右走，定义两个维度如f利州m表示从(1,1)(1,1)(1,1)

21、走到(i,j)(i,j)(i,j)的最值会有后效性。可以考虑以列作为阶段，从左到右推进。对于每个点(。,讥川有从上到下、从左到右和从下到上、从左到右两种方式到达。然后再合并两种方式的最值。fijOfiDOfijO:第jjj列从上到下、从左到右到达(i,j)(i,j)(i,j)的最大值0fijlfiUlfiUl:第jjj列从下到上、从左到右到达(i,j)(i,j)(i,j)的最大值。fij2fiD2fij2:合并以上两种方式,到达(i,j)(i,j)(i,j)的最大值。需要开Ionglonglong,longlonglong.#include#include#include#defineIllo

22、nglongusingnamespacestd;intn,m,a10101010;llf101010103;intmain()(SCanf(%d%d,&n,&m);for(inti=1;i=n;+i)for(intj=1;j=m;+j)scanf(,%dz&aij);for(inti=lj=n;+i)fill=filO=fil2=fi-ll0+ail;for(intj=2;j=m;+j)(/11iU0flDO=fl0-l2+alU;for(inti=2;i=1;-i)fiUl=max(fiU-l2zfi+lUl)+ai0;/fiU2for(inti=1;i=n;+i)fij2=max(fiUO

23、,fiUl);)printf(,%lldnzfnm2);return0;)123456789101112131415171819202122232425262728293031算法拓展记忆化搜索。f0fi皿fij表示从上到下、从左到右到达(i,j)(ij(ij)的最大值，fijlf皿jlfijl表示从下到上、从左到右到达(i,j)(ij(ij)的最大值。目标值是fnm0fnm0川nm0。倒序组织记忆化dfs代码。核心代码：Ildfs(intX,inty,intt)(if(xn11ym)returnmininf;if(fyt!=mininf)returnfxyt;if(t=O)fxyt=max(dfs(x-l,y,O),max(dfs(x,y-l,O),dfs(x,y-l,1)+axy;elsefxyt=max(dfs(x+lzy,1),max(dfs(x,y-lzO),dfs(x,y-l,1)+axy;returnfxyt;)printf(%lldn,dfs(nzm,0);123456789其实记忆化搜索就是dp的一种组织形式，也是dfs中优化的利器。