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

1.优秀的拆分算法分析奇数不存在优秀的拆分。偶数一定存在优秀的拆分.从大到小枚举2的iii次方，从24到Io如果nnn能被2i2否2i整除,说明2i2Z2i是他的一个拆分项，输出。2i2i2i可以表示为1<<il<<il<<ie#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intmain()(intn;scanf("%d"z&n);if(n%2)printf("-ln");else(for(inti=24;i>=1;-i)(if(n/(1«i)-1)(n-=(1«i);printf("%d",1«i);)return0;)123456789101112131415161718192021算法拓展打表。预处理出2i2i2i次方的值，用数组存起来。对每个预处理的值进行标记。倒序枚举nnn,如果枚举的值被标记了，说明他是2i2N2i。可以直接输出，相应的nnn的值也要减去2i2Z2#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;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()(intn;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),nnn最大为10万，可以过。注意事项：对于P*w%p*w%p*w%的下取整，要注意精度跳变，可以用整除替换：p*w/100p*w/100p*w100.#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>usingnamespacestd;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<1)ent=1;/找排名第Cnt的分数ints=0zk;for(k=600;k>=0;-k)(s+=fk;if(s>=ent)break;)printf("%d",k);)return0;)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的个数还是小于t,则q2的堆顶出堆，进入ql,直到ql的个数等于t.此时ql的堆顶分数就是答案。入堆和出堆时间复杂度都是IOgIoglog的，整体复杂度0(nIogn)O(nlogn)O(nlogn)03 .表达式算法分析对于后缀表达式的计算，朴素的算法可以借助数字栈。从左到右扫描，遇到数字就入栈，遇到操作符op,从栈中依次弹出两个数字x2和xl,进行运算X10PX2×1,op,×2xlopx2,然后将运算结果再入栈。如果是动态取反某个数字q次查询，这个复杂度就高了，为0(n*q)O(n*q)O(n*q)对于这种改变的地方很少，但是需要整体结果的，就需要考虑将改变的影响降到最少。表达式树。建立表达式树的时候还得借助栈。在表达式中，数字都是叶结点，运算符都是非叶结点。叶结点的编号按照Ln进行，运算符按照从左到右的顺序在n的基础上分别加1。结点开结构体，存父节点、左右儿子、值、字符。structnode(intparzIchild,rchildzdata;charc;stree1000010;12345字符串用getchargetchargetchar读入。当读入XXX的时候，后面跟的就是数字，把数字处理出来，然后建立结点并入栈。当读入！!的时候，建立结点，栈顶的结点作为该结点的左儿子。当读入&&&和III时，建立结点，栈顶的结点分别作为他们的右儿子和左儿子。这样就建成了表达式树。根结点的值就是整体结果。查询时。取反的结点都是叶结点。只需要改变该叶结点到根结点之间的结点的值就可以了。如果数据是随机的，每次查询的平均复杂度就是IogIoglog级别的。一个很重要的优化：当某个结点的值和原先的值相同时，则直接返回根节点的值。本题有特殊数据，以下代码官方数据能得95分。#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;chars1000010;inta100010zn,ent,sstack1000010,stop;structnode(intpar,Ichild,rchildzdata;charc;stree1000010;intmain()(intIen=O;while(s+len=getchar()!=,n,);slen=32;scanf("%d",&n);for(inti=1;i<=n;+i)scanf("%d"z&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.Ichild.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=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.datastreestreecnt.rchild.data;streecnt.c=''sstack+stop=ent;)intq;scanf("%d,z&q);while(q-)(intt;scanf("%d",&t);intp,sres=!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=streecnt.data;break;)t=p;if(street.par=0)break;)printf("%dn"zsres);)123456789101112131415161718192021222324252627282930returnO;3132333435363738394041424344454647484950515253545556575859606162636465666768697071727375767778798081828384858687以上表达式树不是平衡树，有3种特殊情况会过不了。1 .全都是！!或大部分是。树退化成了链。2 .全都是&&&或大部分是。树几乎退化成了链。3 .全都是III或大部分是。树几乎退化成了链。如下图：在上述过程中，我们可以发现，某些点的值无论怎么变，都不会影响最终的结果。比如0&a0A&Va0&a,aaa的值无论怎么改变都不会影响结果，此时我们可以给值为aaa的这个点打个标记。相似的还有1IaIVIValIa。建立表达式树后，从根结点开始向下O(n)O(n)O(n)的复杂度就可以完成打标记。如果一个叶结点到跟结点的路径上，有一个点被打标记了，那么该结点也要被打标记，即标记可以下传。这样我们最终只要判断取反的叶结点是否打了标记。如果打标记了，则结果为根结点的值。如果没打标记，则结果为根结点的值取反。为什么？假设取反的叶结点没有打标记，则该叶结点到根结点的路径上都没有打标记。则该叶结点的父结点的值就要取反，该父结点的父结点的值也要取反，依次类推，到根结点之间包含根结点的值都要取反。查询的更杂度是O(I)0(l)0(l)o#include<iostream>#include<cstdio>#include<cstring>#include<ctime>usingnamespacestd;chars1000010;inta100010,n,ent,sstack1000010,stop;structnode(intIchild,rchild,data,tag;charc;stree1000010;voidprint_tag(intt)(if(street.Ichild=0&&street.rchild=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.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("%d"z&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;streesnum.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;streecnt.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("%d"z&q);while(q-)(intt;scanf("%d"z&t);if(street.tag=0)printf("%dn",!ans);elseprintf("%dn"zans);)12345678910111213141516return0;171819202122232425262728293031323334353637383940414243444546474849505152535455565758596162636465666768697071727374757677787980818283844 .方格取数算法分析这种矩阵上求最值的题目，dp无疑了。但是每次可以向上、向下和向右走，定义两个维度如f利州m表示从(1,1)(1,1)(1,1)走到(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<iostream>#include<cstdio>#include<cstring>#defineIllonglongusingnamespacestd;intn,m,a10101010;llf101010103;intmain()(SCanf("%d%d",&n,&m);for(inti=1;i<=n;+i)for(intj=1;j<=m;+j)scanf(',%d"z&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<=n;+i)fiUO=max(f(iU-l2,fi-lU0)+aiU;/mumfnUl=fnU-l2+anU;for(inti=n-1;i>=1;-i)fiUl=max(fiU-l2zfi+lUl)+ai0;/fiU2for(inti=1;i<=n;+i)fij2=max(fiUO,fiUl);)printf(',%lldn"zfnm2);return0;)123456789101112131415171819202122232425262728293031算法拓展记忆化搜索。f0fi皿fij表示从上到下、从左到右到达(i,j)(ij(ij)的最大值，fijlf皿jlfijl表示从下到上、从左到右到达(i,j)(ij(ij)的最大值。目标值是fnm0fnm0川nm0。倒序组织记忆化dfs代码。核心代码：Ildfs(intX,inty,intt)(if(x<111X>n11y<111y>m)returnmininf;if(f×yt!=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中优化的利器。