《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;voidDEBUG(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-1n;i+)intj=i+L-1;/dp