2021CSP提高组第二轮试题解析.docx

CSP-S2021廊桥分配一句话题意：为国内航班和国际航分配廊桥的数量，使得最终停在廊桥的飞机总数最大。廊桥的使用原则是先到先得。关键点：廊桥是先到先得，不是自由分配！所有的时间点是不同的(这是树状数组优化的前提)数据量105107105,复杂度确定为nIgnNgnnlgn级别，排序是必须的，则剩余的处理大致是一个O(n),或加一个Iogn优化。分析由于先到先得，所以按照区间起点排序。先不考虑廊桥的数量，单纯从为每个飞机分配廊桥的角度出发。通过随手画几个数据例子可以发现，当所有己经在使用的廊桥的结束时间都晚于当前飞机的到达时间时，必须为他单独分配一个新的廊桥。如果己经在使用的廊桥中，存在结束时间早于当前飞机到达时间，则可以利用这个旧廊桥。如果有多个旧廊桥可以利用，我们的选择是等价的。由此我们希望能利用旧廊桥的飞机，尽量利用最早分配的廊桥。通过上面的分析和结论，我们发现，用这样的过程来模拟可以得到第一个廊桥最多的服务次数，前两个廊桥最多的服务次数，依次类推。我们得到了不同数量的廊桥能服务的最大飞机数。然后就暴力枚举分配廊桥数量，取最大就可以了。错误思路三分：两个增函数，X1+X2=nx_l+x_2=nx1+x2=n时，并不能唯一叠加出一个单峰函数，有可能是双峰函数，所以不行,优化树状数组(单点修改，前缀最值)按照以上思路写代码，会出现一个不好解决的问题：要在多个可用的旧廊桥中找编号最小的廊桥。使用暴力方法需要0(n)的扫描，因此更杂度退化为0(n2)O(M2)0(n这个操作很容易被抽象出来：在所有小于某个时间的编号中取最小值，这明显是一个类似二维偏序的问题，所以使用树状数组来维护每个时间点对应的廊桥编号，动态取前缀最小值即可。同是为了防止炸空间我还加了离散化。#include<bitsstdc+.h>usingnamespacestd;typedeflonglongII;template<classT>boolchmax(T&a,constT&b)if(a<b)a=b;return1;return0;template<classT>boolchmin(T&a,constT&b)if(a>b)a=b;return1;return0;constintMOD=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(x>0)ret=min(retzCx);x-=lowbit(x);)returnret;voidupdateMin(intx)while(x<=N)Cx=timx;for(inti=l;i<lowbit(x);i<<=l)Cx=min(CxzCx-i);x+=lowbit(x);)voidDEBUG()for(inti=1;i<=N;i+)cout«i«":"«Ci«endl;)Bit;voidhandle(vector<pair<int,int>>&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(inti=0;i<A.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();vector<pair<intzint>>Al,A2;intF1MAXN,F2MAXN;vector<int>pool;intmain()cin»n»ml»m2;for(inti=0;i<ml;i+)int,r;cin»I»r;Al.push-back(make-pair(lzr);pool.push_back(l);pool.push_back(r);)for(inti=0;i<m2;i+)intLr;cin»I»r;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(inti=0;i<ml;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;i<m2;i+)A2i.first=IOWeJboUnd(PoOLbegin(),pool.begin()+cntzA2i.first)-pool.begin()+1;A2i.second=IoWejbOUnd(POOl.begin(),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);)cout«ans«endl;)12345678910111213141516171819202122232425262728293031323334353637return0;38394041424344454647484950515253545556575859606162636465666768697071727374757677787980828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131CSP-S2021括号序列一句话题意：为？位置填充字符，求合法的序列数量。关键点：数据范围是500,妥妥O(n3)O(n3)O(n3),可能略微卡常，写代码的时候注意一点就好了。合法括号序列数量，结合复杂度，区间DP。分析：本题的类型非常好确认，难点在于搞清楚合法的序列的定义，具体的包含了以下几种(两类，13是包围类,4是并排类)：0(三)（八）、(AS)、(SA)ASA搞清楚这几类之后，我们要的东西就呼之欲出了：dpijOiJ区间，完全合法的括号方案数。dpiUl:ij区间，AS的括号方案数。dpij2:ij区间，SA的括号方案数。dpij3ij区间，S的方案数。易错点有的同学考虑区间dp会导致重复的问题，因此我们将所有的合法括号分为两类，上面己经描述过。这两类之间是不重不漏的。其中第二类会出现重第计数的问题，因此我们枚举ASA中，第一个A的位置，并且要求这个A一定是一个包围类的A。则可以避免重复。#include<bitsstdc+.h>usingnamespacestd;typedeflonglongII;template<classT>boolchmax(T&a,constT&b)if(a<b)a=b;return1;return0;template<classT>boolchmin(T&a,constT&b)if(a>b)a=b;return1;return0;constintMOD=le9+7;constintINF=Ox3f3f3f3f;constIlLLINF=Ox3f3f3f3f3f3f3f3f;constintMAXN=505;constintMAXM=2000005;IldpMAXNMAXN4,bMAXN,visMAXN;intn,m,k;strings;voidDEBUG(inti,intj)for(intp=i;p<=j;p+)printf("%c'sp);printf("(%dz%d):%lld,%lldz%lldz%lldn",ij,dpijOzdpijlzdpi112zdpij3);)intmain()cin»n»m;cin»s;if(m>=1)for(inti=0;i<n;i+)f(si=7'si='*')dpii3=l;/DEBG(izi);)for(intL=2;L<=n;L+)for(inti=0;i<n&&i+L-1<n;i+)intj=i+L-1;/dpijO包围型()if(si=&&sj=')'11si=,('&&sj=Hsi='?'&&sQ=si='('&&sj=')')if(i+l>j-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-1;k+)/枚举前一段的Aif(s='CIlsi='?')&&(sk=THsk='?')if(i+l=k)/ABdpiUO=(dpijO+dpk+ljO)%MOD;/A+SBdpiDO=(dpijO+dpk+lU2)%MOD;)else/ABdpDO=(dpijO+(dpi+lk-lO+dpi+lk-l3+dpi+lk-ll+dpi+lk-l2)*dpk+ljO)%MOD;/A+SBdpUO=(dpijO+(dpi+lk-lO+dpi+lk-l3+dpi+lk-ll+dpi+lk-l2)*dpk+lj2)%MOD;)/AS+B和A+SB重复/dpiUO三(dpiUO+dpikl*dpk+ljO)%MOD;)dp。皿闺AS型for(intk=j-1;k>=j-m&&k>i;k-)dp0l=(dpiUl+dpikO*dpk+lU3)%MOD;dpi皿SA型for(intk=i+1;k<=i+m&&k<j;k+)dpiUl2=(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);cout«dp0n-l0«endl;)12345678910111213141516171819202122232425262728293031323334353637returnO;383940414243444546474849505152535455565758596061626364656667686970717273747576777879808283848586878889909192939495CSP-S2021回文一句话题意：你可以从a序列的两端以任意顺序取数，获得一个回文串。关键点：数据量是5e55e55e5,因此一定是一个简单的做法。分析随手画一个例子，假设第一步取左端，则对应的数字必须最后取°第二个取的数字，其对应的数字一定在倒数第二个取，所以倒数第一个和倒数第二个应该是紧挨在一起的，才可以保证这一点。由上述的两点我们可以推定，一旦第一个数字确定下来，后面的选择是非常有限的，并不是任意可以选择的。简单论证后，证实暴力DFS复杂度仅仅是O(n),#include<bitsstdc+.h>usingnamespacestd;typedeflonglongII;constintMOD=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(step>n)ans=1;return;)/Leftif(L<mL)if(L<mL-1&&aL=amL-l)sstep=,L's2*n-step+l=,L'DFS(L+lzR,mL-lzmR);if(ans)return;)if(R>mR&&aL=amR+l)sstep='L's2*n-step+l=,R'DFS(L+lzR,mL,mR+l);if(ans)return;)/Rightif(R>mR)if(L<mL&&aR=amL-l)sstep=,R's2*n-step+1='L'DFS(L,R-IzmL-l,mR);if(ans)return;)if(R>mR+1&&aR=amR+l)sstep=,R's2*n-step+l='R,;DFS(L,R-LmL,mR+l);讦(ans)return;)intmain()cin»T;while(T-)cin»n;memset(pzO,sizeof(p);for(inti=1;i<=2*n;i+)cin»ai;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+)cout«si;)cout«endl;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+)cout«si;)cout«endl;continue;)cout«-1«endl;)returnO;)1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515354555657585960616263646566676869707172737475767778798081828384858687888990919293CSP-S2021交通规划一个写在脸上的网络流问题。最小割。就是处理点编号的时候麻烦一点。板子大概能得65分。其他的TLE,暂时没想到优化。#include<bitsstdc+.h>usingnamespacestd;typedeflonglongII;constintMOD=le9+7;constintINF=Ox3f3f3f3f;constIlLLJNF=0x3f3f3f3f3f3f3f3f;constintMAXN=5e5+10;constintM=2e5+10;intS,T；intnzm,K;intmw5055052;structEdgeintfrom,to,nxt,cap,flow;Edge()Edge(intfrom,intto,intnxtzintcap,intflow):from(from)zto(to)znxt(nxt),cap(cap),flow(flow)()baseMAXN<<2;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_basev,w,0);head_basev=cnt_base+;)structDinicintn,m,s,t,ent;EdgeedgesMAXN«2;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+;edgescnt=Edge(to,from,headto,cap,O);headto=ent+;)boolbfs()memset(vis,0,sizeofvis);queue<int>q;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.cap>e.flow)vise.to=1;de.to=dnow+1;q.push(e.to);)returnvist;)intdfs(intxjntres)if(x=t11!res)returnres;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;intgetV(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;i<n;i+)for(intj=1;j<=m;j+)scanf("%d,&mwij0);for(inti=1;i<=n;i+)for(intj=1;j<m;j+)scanf("%d"z&mwijl);init();for(inti=1;i<n;i+)for(intj=1;j<=m;j+)intu=(i-l)*m+j;intv=i*m+j;add(u,v,mwij0);)for(inti=1;i<=n;i+)for(intj=1;j<m;j+)intu=(i-l)*m+j;intv=(i-l)*m+j+1;add(u,v,mwijl);)/以上是基础图，每次询问需要重置整个图。while(K-)dinic.init();intk;scanf("%d"z&k);T=n*m+k+1;for(inti=1;i<=k;i+)intw,p,y;scanf("%d%d%d"z&w,&p,&y);intu=n*m+i;intv=getV(p);dinic.addedge(uzv,w);if(y)dinic.addedge(uzT1INF);elseclinic.addedge(0zu,INF);)printf(',%dn"zdinic.maxflow(0,T);)return0;)版权声明：本文为CSDN博主Code,SharkJ的原创文章，遵循CC4.0BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：