《2021CSP提高组第二轮试题解析.docx》由会员分享，可在线阅读，更多相关《2021CSP提高组第二轮试题解析.docx（26页珍藏版）》请在课桌文档上搜索。
1、CSP-S2021廊桥分配一句话题意：为国内航班和国际航分配廊桥的数量，使得最终停在廊桥的飞机总数最大。廊桥的使用原则是先到先得。关键点：廊桥是先到先得，不是自由分配！所有的时间点是不同的(这是树状数组优化的前提)数据量105107105,复杂度确定为nIgnNgnnlgn级别，排序是必须的，则剩余的处理大致是一个O(n),或加一个Iogn优化。分析由于先到先得，所以按照区间起点排序。先不考虑廊桥的数量，单纯从为每个飞机分配廊桥的角度出发。通过随手画几个数据例子可以发现，当所有己经在使用的廊桥的结束时间都晚于当前飞机的到达时间时，必须为他单独分配一个新的廊桥。如果己经在使用的廊桥中，存在结束时
2、间早于当前飞机到达时间，则可以利用这个旧廊桥。如果有多个旧廊桥可以利用，我们的选择是等价的。由此我们希望能利用旧廊桥的飞机，尽量利用最早分配的廊桥。通过上面的分析和结论，我们发现，用这样的过程来模拟可以得到第一个廊桥最多的服务次数，前两个廊桥最多的服务次数，依次类推。我们得到了不同数量的廊桥能服务的最大飞机数。然后就暴力枚举分配廊桥数量，取最大就可以了。错误思路三分：两个增函数，X1+X2=nx_l+x_2=nx1+x2=n时，并不能唯一叠加出一个单峰函数，有可能是双峰函数，所以不行,优化树状数组(单点修改，前缀最值)按照以上思路写代码，会出现一个不好解决的问题：要在多个可用的旧廊桥中找编号最
3、小的廊桥。使用暴力方法需要0(n)的扫描，因此更杂度退化为0(n2)O(M2)0(n这个操作很容易被抽象出来：在所有小于某个时间的编号中取最小值，这明显是一个类似二维偏序的问题，所以使用树状数组来维护每个时间点对应的廊桥编号，动态取前缀最小值即可。同是为了防止炸空间我还加了离散化。#includeusingnamespacestd;typedeflonglongII;templateboolchmax(T&a,constT&b)if(ab)a=b;return1;return0;templateboolchmin(T&a,constT&b)if(ab)a=b;return1;return0;c
4、onstintMOD=le9+7;constintINF=Ox3f3f3f3f;constIlLLINF=Ox3f3f3f3f3f3f3f3f;constintMAXN=500005;constintMAXM=2000005;IlvisMAXN,timMAXN;intn,ml,m2;structBITintCMAXN;intN;inlineintlowbit(intx)returnX&(-x);voidinit(int_N)N=_N;memset(Cz0x3f,sizeof(C);)intgetMin(intx)intret=INF;while(x0)ret=min(retzCx);x-=lo
5、wbit(x);)returnret;voidupdateMin(intx)while(x=N)Cx=timx;for(inti=l;ilowbit(x);i=l)Cx=min(CxzCx-i);x+=lowbit(x);)voidDEBUG()for(inti=1;i=N;i+)couti:Ciendl;)Bit;voidhandle(vectorpair&A,intF)Bit.init(2*(ml+m2)+2);sort(A.begin(),A.end();memset(tim,0x3f,sizeof(tim);memset(vis,0,sizeof(vis);intent=0;for(i
6、nti=0;iA.size();i+)intid=Bit.getMin(Ai.first);/没有可以停靠的廊桥if(id=INF)ent+;Fcnt=1;timAi.second=ent;viscnt=Ai.second;Bit.updateMin(Ai.second);)/有可以停靠的廊桥elsetimvisid=INF;Bit.updateMin(visid);visid=Ai.second;timAi.second=id;Bit.updateMin(Ai.second);Fid+;)/Bit.DEBUG();vectorpairAl,A2;intF1MAXN,F2MAXN;vector
7、pool;intmain()cinnmlm2;for(inti=0;iml;i+)int,r;cinIr;Al.push-back(make-pair(lzr);pool.push_back(l);pool.push_back(r);)for(inti=0;im2;i+)intLr;cinIr;A2.push-back(make-pair(lzr);pool.push_back(l);pool.push_back(r);)/离散化sort(pool.begin(),pool.end();intent=unique(pool.begin()zpool.end()-pool.begin();for
8、(inti=0;iml;i+)Ali.first=lower_bound(pool.begin(),pool.begin()+cntzAli.first)-pool.begin()+1;Ali.second=IOWejbOUnd(POOl.begin(),pool.begin()+ent,Ali.second)-pool.begin()+1；)for(inti=O;im2;i+)A2i.first=IOWeJboUnd(PoOLbegin(),pool.begin()+cntzA2i.first)-pool.begin()+1;A2i.second=IoWejbOUnd(POOl.begin(
9、),pool.begin()+ent,A2i.second)-pool.begin()+1；)/分别处理handle(Al,Fl);handle(A2,F2);for(inti=1;i=n;i+)Fli+=Fli-lzF2i+=F2i-1;intans=O;for(inti=O;i=n;i+)ans=max(anszFli+F2n-i);)coutansendl;)12345678910111213141516171819202122232425262728293031323334353637return0;3839404142434445464748495051525354555657585
10、9606162636465666768697071727374757677787980828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131CSP-S2021括号序列一句话题意：为？位置填充字符，求合法的序列数量。关键点：数据范围是500,妥妥O(n3)O(n3)O(n3),可能略微卡常，写代码的时候注意一点就好了。合法括号序列数量，结合复杂度，区间DP。分析：本题的类型非常好确认，难点
11、在于搞清楚合法的序列的定义，具体的包含了以下几种(两类，13是包围类,4是并排类)：0(三)（八）、(AS)、(SA)ASA搞清楚这几类之后，我们要的东西就呼之欲出了：dpijOiJ区间，完全合法的括号方案数。dpiUl:ij区间，AS的括号方案数。dpij2:ij区间，SA的括号方案数。dpij3ij区间，S的方案数。易错点有的同学考虑区间dp会导致重复的问题，因此我们将所有的合法括号分为两类，上面己经描述过。这两类之间是不重不漏的。其中第二类会出现重第计数的问题，因此我们枚举ASA中，第一个A的位置，并且要求这个A一定是一个包围类的A。则可以避免重复。#includeusingnamesp
12、acestd;typedeflonglongII;templateboolchmax(T&a,constT&b)if(ab)a=b;return1;return0;templateboolchmin(T&a,constT&b)if(ab)a=b;return1;return0;constintMOD=le9+7;constintINF=Ox3f3f3f3f;constIlLLINF=Ox3f3f3f3f3f3f3f3f;constintMAXN=505;constintMAXM=2000005;IldpMAXNMAXN4,bMAXN,visMAXN;intn,m,k;strings;voidD
13、EBUG(inti,intj)for(intp=i;p=1)for(inti=0;in;i+)f(si=7si=*)dpii3=l;/DEBG(izi);)for(intL=2;L=n;L+)for(inti=0;in&i+L-1j-l)dpiUO=l;elsedpiUO=(dpi0O+dpi+lj-lO+dpi+lU-ll+dpi+lU-l2+dpi+lj-l3)%M0D;)/dpijO并排型intf=0;for(intk=i+1;k=j-m&ki;k-)dp0l=(dpiUl+dpikO*dpk+lU3)%MOD;dpi皿SA型for(intk=i+1;k=i+m&kj;k+)dpiUl2
14、=(dpij2+dpik-l3*dpkUO)%MOD;dpi皿S型if(L=m)intf=1;for(intk=i;k=j;k+)if(sk=(sk=)f=O;break;)if(f)dpiU3=l;/DEBG(iJ);coutdp0n-l0endl;)12345678910111213141516171819202122232425262728293031323334353637returnO;3839404142434445464748495051525354555657585960616263646566676869707172737475767778798082838485868788
15、89909192939495CSP-S2021回文一句话题意：你可以从a序列的两端以任意顺序取数，获得一个回文串。关键点：数据量是5e55e55e5,因此一定是一个简单的做法。分析随手画一个例子，假设第一步取左端，则对应的数字必须最后取第二个取的数字，其对应的数字一定在倒数第二个取，所以倒数第一个和倒数第二个应该是紧挨在一起的，才可以保证这一点。由上述的两点我们可以推定，一旦第一个数字确定下来，后面的选择是非常有限的，并不是任意可以选择的。简单论证后，证实暴力DFS复杂度仅仅是O(n),#includeusingnamespacestd;typedeflonglongII;constintMO
16、D=le9+7;constintINF=0x3f3f3f3f;constIlLLJNF=0x3f3f3f3f3f3f3f3f;constintMAXN=5e5+10;constintMAXM=2e6+10;intaMAXN*2,bMAXNzpMAXN2,visMAXN;charsMAXN*2;intn,m,T,ans;voidDFS(intLzintR,intmL,intmR)intstep=n*2-(R-L+l)+1;/当前选择的是第step个数字。if(stepn)ans=1;return;)/Leftif(LmL)if(LmR&aL=amR+l)sstep=L;s2*n-step+l=,
17、R;DFS(L+lzR,mL,mR+l);if(ans)return;)/Rightif(RmR)if(LmR+1&aR=amR+l)sstep=,R;s2*n-step+l=R,;DFS(L,R-LmL,mR+l);讦(ans)return;)intmain()cinT;while(T-)cinn;memset(pzO,sizeof(p);for(inti=1;i=2*n;i+)cinai;if(paiO=0)pai0=i;elsepail=i;)ans=0;sl=L;s2*n=L;DFS(2,2*n,pall,pall);if(ans)for(inti=1;i=2*n;i+)coutsi;
18、)coutendl;continue;)ans=O;sl=R;s2*n=,L;DFS(2*n-l,pa2*n0,pa2*n0);if(ans)for(inti=1;i=2*n;i+)coutsi;)coutendl;continue;)cout-1endl;)returnO;)12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505153545556575859606162636465666768697071727374757677787980818283848586
19、87888990919293CSP-S2021交通规划一个写在脸上的网络流问题。最小割。就是处理点编号的时候麻烦一点。板子大概能得65分。其他的TLE,暂时没想到优化。#includeusingnamespacestd;typedeflonglongII;constintMOD=le9+7;constintINF=Ox3f3f3f3f;constIlLLJNF=0x3f3f3f3f3f3f3f3f;constintMAXN=5e5+10;constintM=2e5+10;intS,T；intnzm,K;intmw5055052;structEdgeintfrom,to,nxt,cap,flow
20、;Edge()Edge(intfrom,intto,intnxtzintcap,intflow):from(from)zto(to)znxt(nxt),cap(cap),flow(flow)()baseMAXN2;intCnJbaSe,head-baseMAXN;voidinit()cnt_base=0;memset(head_base,-lzsizeof(head_base);)voidadd(intu,intv,intw)basecnt_base=Edge(u,v,head-baseuzw,0);head_baseu=cnt_base+;basecnt_base=Edge(v,u,head
21、_basev,w,0);head_basev=cnt_base+;)structDinicintn,m,s,t,ent;EdgeedgesMAXN2;intheadMAXN;boolvisMAXN;intdMAXN;intcurMAXN;voidinit()ent=cnt_base;memcpy(head,head-basezsizeof(head_base);memcpy(edges,base,sizeof(base);)voidaddedge(intfromjntto,intcap)edgescnt=Edge(from,to,headfromxcapz0);headfrom=ent+;ed
22、gescnt=Edge(to,from,headto,cap,O);headto=ent+;)boolbfs()memset(vis,0,sizeofvis);queueq;qpush(s);viss=1;while(!q.empty()intnow=q.front();q.pop();for(inti=headnow;i;i=edgesi.nxt)Edge&e=edgesi;if(!vise.to&e.cape.flow)vise.to=1;de.to=dnow+1;q.push(e.to);)returnvist;)intdfs(intxjntres)if(x=t11!res)return
23、res;intflow=0,f;for(int&i=curx;i;i=edgesi.nxt)Edge&e=edgesi;if(dx+1=de.to&(f=dfs(e.tozmin(resze.cap-e.flow)0)e.flow+=f;edgesil.flow-=f;flow+=f;res-=f;if(!res)break;)returnflow;)intmaxflow(intsjntt)this-s=s;this-t=t;intflow=O;while(bfs()memcpy(cuGhead,sizeofhead);flow+=dfs(s,INF);)returnflow;)dinic;i
24、ntgetV(intp)if(p=m)returnp;if(p=n+m)return(p-m)*m;if(p=n+2*m)returnm-(p-n-m)+1+(n-l)*m;return(n-(p-n-2*m)*m+1;)intmain()scanf(%d%d%d,&n,&m,&K);for(inti=1;in;i+)for(intj=1;j=m;j+)scanf(%d,&mwij0);for(inti=1;i=n;i+)for(intj=1;jm;j+)scanf(%dz&mwijl);init();for(inti=1;in;i+)for(intj=1;j=m;j+)intu=(i-l)*
25、m+j;intv=i*m+j;add(u,v,mwij0);)for(inti=1;i=n;i+)for(intj=1;jm;j+)intu=(i-l)*m+j;intv=(i-l)*m+j+1;add(u,v,mwijl);)/以上是基础图，每次询问需要重置整个图。while(K-)dinic.init();intk;scanf(%dz&k);T=n*m+k+1;for(inti=1;i=k;i+)intw,p,y;scanf(%d%d%dz&w,&p,&y);intu=n*m+i;intv=getV(p);dinic.addedge(uzv,w);if(y)dinic.addedge(uzT1INF);elseclinic.addedge(0zu,INF);)printf(,%dnzdinic.maxflow(0,T);)return0;)版权声明：本文为CSDN博主Code,SharkJ的原创文章，遵循CC4.0BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：
