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;31323334353637383940414243444546474849505152535455565758596061626364656667686970717273
