2022年（复赛S）CCF非专业级别软件能力认证全国卷真题（附详细答案解析）.docx

2022CCF非专业级软件能力认证CSP-J/S2022第二轮认证提高级时间：2022年10月29日14:3018:30题目名称假期计划策略游戏星战数据传输题目类型传统型传统型传统型传统型目录holidaygamegalaxytransmit可执行文件名holidaygamegalaxytransmit输入文件名holiday.ingame.ingalaxy.intransmit.in输出文件名holiday.outgame.outgalaxy.outtransmit.out每个测试点时限2.0秒1.0秒2.0秒3.0秒内存限制512MiB512MiB512MiB1024MiB测试点数目20202025测试点是否等分是是是是提交源程序文件名对于C+语言holiday.cppgame.cppgalaxy.cpptransmit.cpp编译选项对于C+语言-02-std=c÷+14注意事项(请仔细阅读)1 .文件名(程序名和输入输出文件名)必须使用英文小写.2 .CC÷÷中函数main()的返回值类型必须是int,程序正常结束时的返回值必须是Oo3 .提交的程序代码文件的放置位置请参考各省的具体要求。4 .因违反以上三点而出现的错误或问题，申诉时律不予受理。5 .若无特殊说明，结果的比较方式为全文比较(过滤行末空格及文末回车).6 .选手提交的程序源文件必须不大于100KB.7 .程序可使用的栈空间内存限制9题目的内存限制致。8 .全国统评测时采用的机器配置为Tntcr(R)Com(TM)i78700KCPU3.70GHz,内存32GB。上述时限以此配置为准。9 .只提供1.hIUX格式附加样例文件。10 .评测在当前最新公布的Nol1.imlX下进行，各语白的编译器版本以此为准。Tl假期计划(holiday)题目描述小熊的地图上有几个点，其中编号为1的是它的家、编号为2,3,.,Ti的都是景点。部分点对之间有双向直达的公交线路。如果点Z与句、句与Z2次1与次、.与y之间均有直达的线路，那么我们称I与g之间的行程可转车A次通达；特别地，如果点I与y之间有直达的线路，则称可转车0很快就要放假了，小熊计划从家出发去4个不同的景点游玩，完成5段行程后回家：家T景点AT景点BT景点CT景点D家且每段行程最多转车k次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点A景点B的这段行程中，转车时经过的点可以是家、也可以是景点C,还可以是景点D家这段行程转车时经过的点。假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。输入格式第一行包含三个正整数小m,A,分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。第二行包含n-1个正整数，分别表示编号为2,3,.的景点的分数。接下来m行，每行包含两个正整数叫y,表示点1和y之间有道路直接相连，保证1叫gm且没有重边，自环。输出格式输出一个正整数，表示小熊经过的4个不同景点的分数之和的最大值。检入输出样例沦入1#88197182361 223344556677881输出1#27检入2#790111234122334151617546474输出2#【样例W1】当计划的行程为I2357l时，4个点的分政之和为9+7+8+3=27,可以证明其为最大值.HSl35781的%24,f5l32871的景点分数之和为25.它们都符合要求,但分数之和不是大的.行程I2358l的景点分数之和为30,但其中5N至少需要转车2次，因此不符合最多转车k=I次的要求.fSl23231的Il点分数之和为32,但游玩的并非I个不同的景点，因此也不符合要求.【样例3】见附件中的holidayhoild*jr3.Sa与holidayhoHdav3.ans.fldra对于所有数据，保证5&n2500,l<m<10000,0<fc100.所有景点的分数1<Sj10,.保证至少存在一蛆符合要求的行程.测试点编号n<m<k<1310200451020568205010091130010000121430010001001517250010000018-20250010000100T2策略游戏（game）题目描述小1.和小Q在玩一个策略游戏。有一个长度为n的数组A和一个长度为m.的数组B1在此基础上定义一个大小为n×m的矩阵C1满足Cij=Ai×Bj.所有下标均从1开始。游戏一共会进行q轮，在每一轮游戏中，会事先给出4个参数。,勺/2,72,满足1ZiH<n,1 r2m.游戏中，小1.先选择一个Z1r1之间的下标I,然后小Q选择一个I2F2之间的下标y.定义这一轮游戏中二人的得分是GCJr小1.的目标是使得这个得分尽可能大，小Q的目标是使得这个得分尽可能小.同时两人都是足够聪明的玩家，每次都会采用最优的策略。请问：按照二人的最优策略，每轮游戏的得分分别是多少？输入格式第一行输入三个正整数以n,q,分别表示数组A,数组B的长度和游戏轮数.第二行：7?个整数，表示Ar分别表示数组工的元素。第三行：Tn个整数，表示3,分别表示数组B的元素。接下来q行，每行四个正整数，表示这一次游戏的乙,门"242.输出格式输出共g行，每行一个整数，分别表示每一轮游戏中，小1.和小Q在最优策略下的得分。输入输出样例输入1#32201-2-3413122322输出1#04输入2#6453-1-212012-1-316141514141226342523输出2#0-232-1U这姐数揖中，矩僻如下：00-346-8在第一轮游戏中，无论小1.选取的是2还JIZ：3,小Q部有办法选择栗个y使得终的得分为负数.因此小I选择，=1是最优的，因为这样博分一定为0而在第二轮游戏中，由于小I可以选工=2,小Q只施选y=2,如此慢分为4.【样例3】!S!ftfi9«3ia三e3.In与Caar33.皿.【样例#4】见附件中的tMtae4.io与canegae4ans.11i9SS对于所商IHB.I<n,m,q<IOi,10»<At.B,<ltf,.Mttffi,1<h<r1<n.1hrtm费试有Hn,m,q<榭HI件12001,2220013200245200无6I(MM)1.27810001910I(XM)21112IO(M)无13IO51.21415IO511617IO421820IOi无具中，特殊性质1为：保证A,B,>0.特殊性质2为：保证对于每轮游戏而含，要么/1=r1,要么1.=72T3星战(galaxy)题目描述在这一轮的星际战争中，我方在宇宙中建立了九个据点，以M个单向虫洞连接。我们把终点为据点的所有虫洞归为据点的虫洞。战火纷飞之中这些虫洞很难长久存在，敌人的打击随时可能到来。这些打击中的有效打击可以分为两类：1 .敌人会摧毁某个虫洞，这会使它连接的两个据点无法再通过这个虫洞直接到达，但这样的打击无法摧毁它连接的两个据点。2 .敌人会摧毁某个据点，由于虫洞的主要技术集中在出口处，这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁。注意：摧毁只会导致虫洞不可用，而不会消除它的存在。为了抗击敌人并维护各部队和各据点之间的联系，我方发展出了两种特种部队负责修复虫洞：A型特种部队则可以将某个特定的虫洞修复。B型特种部队可以将某据点的所有损坏的虫洞修复。考虑到敌人打击的特点，我方并未在据点上储备过多的战略物资.因此只要这个据点的某一条虫洞被修复，处于可用状态，那么这个据点也是可用的。我方掌握了一种苛刻的空间特性，利用这T推我方战舰可以沿着虫洞瞬移到敌方阵营，实现精确打击。为了把握发动反攻的最佳时机，指挥部必须关注战场上的所有变化，为了寻找一个能够进行反攻的时刻。总指挥认为： 如果从我方的任何据点出发，在选择了合适的路线的前提下，可以进行无限次的虫洞穿梭（可以多次经过同一据点或同一虫洞），那么这个据点就可以实现反击。 为了使虫洞穿梭的过程连续，尽量减少战舰在据点切换虫洞时的质能损耗，当且仅当只有一介从该据点出发的虫洞可用时，这个据点可以实现连续穿梭。 如果我方所有据点都可以实现反击，也都可以实现连续穿梭，那么这个时刻就是一个绝佳的反攻时刻.总司令为你下达命令，要求你根据战场上实时反馈的信息，迅速告诉他当前的时刻是否能够进行一次反攻。输入格式输入的第一行包含两个正整数72,m.接下来m行每行两个数u,表示一÷从据点U出发到据点V的虫洞.保证u#叽保证不会有两条相同的虫洞.初始时所有的虫洞和据点都是完好的。接下来一行一个正整数q表示询问个数。接下来q行每行表示一次询问或操作。首先读入一个正整数t表示指令类型：.若t=1.接下来两个整数u,表示敌人摧毁了从据点u出发到据点的虫洞.保证该虫洞存在且未被摧毁。 若t=2,接下来一个整数表示敌人摧毁了据点如果该据点的虫洞已全部被摧毁，那么这次袭击不会有任何效果。.若t=3,接下来两个整数以V表示我方修复了从据点u出发到据点V的虫洞.保证该虫洞存在且被摧毁. 若£=4,接下来Y整数U表示我方修复了据点M如果该据点没有被摧毁的虫洞，那么这次修复不会有任何效果.在每次指令执行之后，你需要判断能否进行一次反攻。如果能则输出yes否则输出XO输出格式输出一共q行。对于每个指令，输出这个指令执行后能否进行反攻。输入输出样例输入1#362332111321233322313131342132输出1#NONOYESNOYESNONONOYESNONO【样例虫洞状态可以参考下面的图片,图中的边表示存在且未被摧毁的虫洞:图1：样例1【样例#2见附件中的galaxygalaxy2.in与galaxygalaxy2.ans【样例#3】见附件中的galavsalaxv3.in与galavgalax3.ans.【样例#4】见附件中的salaxvgalav4.in与galagalaxy4.ans.【数据范围】对于所有数据保证：ln5xl(P,1m5×105,1<95×IO5.测试点nm<q特殊限制13102050无48IO3IO4IO3无9105×IO55×IO55×IO5保证没有t=2和£=4的情况11125×IO55XIO55×IO5保证没有f=4的情况1316IO55×IO55×IO5无17205×IO55×Itfi5×IO5无T4数据传输(transmit)题目描述小c正在设计计算机网络中的路由系统。测试用的网络总共有n台主机，依次编号为1九。这72台主机之间由n-1根网线连接，第i条网线连接个主机Qi和瓦。保证任意两台主机可以通过有限根网线直接或者间接地相连。受制于信息发送的功率，主机能够直接将信息传输给主机b当且仅当两个主机在可以通过不超过k根网线直接或者间接的相连。在计算机网络中，数据的传输往往需要通过若干次转发。假定小C需要将数据从主机Q传输到主机b(b),则其会选择出若干台用于传输的主机Cl=,c2,.,cm-,cm=b,并按照如下规则转发：对于所有的1Vn,主机G将信息直接发送给q+i。每台主机处理信息都需要一定的时间，第。台主机处理信息需要单位的时间。数据在网络中的传输非常迅速，因此传输的时间可以忽略不计。据此，上述传输过程花费的时间为%。现在总共有q次数据发送请求，第，次请求会从主机st发送数据到主机。小C想要知道，对于每一次请求至少需要花费多少单位时间才能完成传输。输入格式输入的第一行包含三个正整数*Q/,分别表示网络主机个数，请求个数，传输参数。数据保证ISn2×IO511Q2XIO5,1ft3.输入的第二行包含n个正整数，第，个正整数表示3，保证1”IO9e接下来九一1行，第W行包含两个正整数ai,bil表示一条连接主机ai,bi的网线。保证1&,8n接下来Q行，第，行包含两个正整数Si表示一次从主机Si发送数据到主机ti的请求。保证1n,Si#%输出格式Q行，每行一个正整数，表示第，次请求在传输的时候至少舔要花费多少单位的时间。蛤入修出性例输入1#7331234567242536374756输出1#【样例解释#1】对于第一组请求，由于主机4,7之间需要至少4根网线才能连接，因此数据无法在两台主机之间直接传输，员至少需要一次转发；我们让其在主机1进行一次转发，不难发现主机1和主机4,7之间都只高要两根网线即可连接，且主机1的数据处理时间仅为1,为所有主机中最小，因此最少传输的时间为4+1+7=12.对于第三组请求，由于主机1,2之间只需要1根网线就能连接，因此数据直接传输就是最优解，最少传输的时间为1+2=3.【样例#2】见附件中的transmittransmit2.in与trans三ittransmit2.ans该样例满足测试点2的限制.【样例#3】见附件中的transmittransmit3.in与transaittransmit3.ans该样例满足测试点3的限制【样例#4】见附件中的transmittransmit4.in与transaittransmit，ans。该样例满足测试点20的限制.【数据范围】对于所有的测试数据，满足1n2X1()51<Q<2×IO5fl<k<3lli,6l<n.1WSj,tjWTl,Sirti测试点nQ<k=特殊性质110102是210103是32002002是452002003是67200020001否89200020002否1011200020003否12132×IO52×IO51否145×IO45×IO42三1516IO5IO5217192×IO52×IO52否205×IO45×1043三2122IO5IO53是23-252×IO52×IO53否特殊性质：保证四=£+1,而山则从1,2,.,，中等概率选取.答案部分1 .策略游戏#include<iostream>#include<cstdio>usingnamespacestd;constintinf=1<<30;typedeflonglongII;Ila100005,b100005;intn,m,q,H,r1,12,r2,sa100005,sb100005,Ig2100005;structSTIlst10000517;inttp1,tp2;Ilquery(intl,intr)intk=lg2r-l+1;if(tp1=1)returnmin(stlk,str-(1<<k)+1k);if(tp1=2)returnmax(stlk,str-(1<<k)+1k);)voidbuild(intn,ll*f)for(inti=1;i<=n;i+)(if(tp2=1)sti0=(fi>=0?fi:(tp1=1?inf:-inf);if(tp2=2)sti0=(fi<0?-fi:(tp1=1?inf:-inf);)for(inti=1;i<=16;i+)for(intj=1;j+(1«i)-1<=n;j+)(if(tp1=1)sti=min(sti-1,st+(1<<(i-1)i-1);if(tp1=2)st11i=max(sti-1,st+(1<<(i-1)i-1);)mxa1,mna1,mxa2,mna2,mxb1,mnb1,mxb2,mnb2;intmain()(SCanf(”d%d%d”,&n,&m,&q);for(inti=1;i<=n;i+)scanf(,'%lld',ai);for(inti=1;i<=m;i+)scanf("%lld"bi);for(inti=1;i<=n;i+)sai=sai-1+(ai<0);for(inti=1;i<=m;i+)sbi=sbi-1+(bi<0);for(inti=2;i<=100000;i+)Ig2i=lg2i2+1;mxa1.tp1=2;mxa1.tp2=1;mxa1.build(n,a);mxa2.tp1=2;mxa2.tp2=2;mxa2.build(n,a);mna1.tp1=1;mna1.tp2=1;mna1.build(n,a);mna2.tp1=1;mna2.tp2=2;mna2.build(n,a);mxb1.tp1=2;mxb1.tp2=1;mxb1.build(m,b);mxb2.tp1=2;mxb2.tp2=2;mxb2.build(m,b);mnb1.tp1=1;mnb1.tp2=1;mnb1.build(m,b);mnb2.tp1=1;mnb2.tp2=2;mnb2.build(m,b);while(q-)(scanf(11%d%d%d%d111,&r1,&l2,&r2);intfa1=0,fa2=0,fb1=0,fb2=0;if(sar1-saH-1=r1-11+1)fa1=1;if(sar1-saH-1=0)fa2=1;if(sbr2-sbl2-1=r2-l2+1)fb1=1;if(sbr2-sbl2-1=0)fb2=1;Ilamx1,amx2,am1,am2,bmx1,bmx2,bm1,bm2;amx1=mxa1.query(H,r1);amx2=-mxa2.query(H,r1)；amn1=mna1.query(H,r1);am2=-mna2.query(H,r1);bmx1=mxb1.query(l2,r2);bmx2=-mxb2.query(l2,r2);bmn1=mnb1.query(l2,r2);bm2=-mnb2.query(l2,r2);if(fa1)(if(fb1)printf("%lldn',amx2*bm2);elseprintf(',%lldn",am2*bmx1);)elseif(fa2)(if(fb2)printf("%lldn',amx1*bm1);elseprintf(',%lldn",amn1*bmx2);)else(if(fb1)printf("%lldn',amx2*bmn2);elseif(fb2)printf("%lldn",amx1*bm1);elseprintf(',%lldn",max(amn1*bmx2,am2*bmx1);)returnO;)2 .假期计划include<iostream>include<queue>usingnamespacestd;typedeflonglongII;typedefstructintnxt;intend;Edge;intent=0;intdis25072507,head2507,pos25077;Ils2507,f25072507;Edgeedge20007;queue<int>q;inlinevoidinit(intn)for(registerinti=1;i<=n;i+)for(registerintj=1;j<=n;j+)disi0=0x7fffffff;)inlinevoidadd_edge(intstart,intend)ent+;edgecnt.nxt=headstart;headstart=ent;edgecnt.end=end;voidbfs(intstart,intn)disstartstart=0;q.push(start);while(!q.empty()intcur=q.front();qpp();for(registerinti=headcur;i!=0;i=edgei.nxt)intx=edgei.end;if(disstartx=0x7fffffff)disstartx=disstartcur+1;q.push(x);)intmain()intn,m,k;Ilans=0;cin»n»m»k;k+;init(n);for(registerinti=2;i<=n;i+)cin»si;)for(registerinti=1;i<=m;i+)intx,y;cin»x»y;add_edge(x,y);add_edge(y,x);for(registerinti=1;i<=n;i+)bfs(i,n);)for(registerinti=1;i<=n;i+)for(registerintj=1;j<=n;j+)if(i!=j&&dis1i<=k&&disij<=k)fij=si+s;elsefi0=-4e18;)for(registerinti=2;i<=n;i+)Psi1=Psi2=posi3=i;for(registerintj=2;j<=n;j+)if(fposi1i<fji)posi3=posi2;posi2=posi1;posi1=j;)seif(fposi2i<fi)posi3=posi2;posi2=j;)seif(fposi3i<f11i)posi3=j;)for(registerinti=2;i<=n;i+)for(registerintj=2;j<=n;j+)if(i!=j&&disi0<=k)for(registerintx=1;x<=3;x+)for(registerinty=1;y<=3;y+)if(posix!=j&&posix!=posOy&&posOy!=i)ans=max(ans,fposixi+ffpos11y0);break;)cout«ans;returnO;3 .数据传输include<iostream>include<cstdio>include<cmath>include<cstring>usingnamespacestd;typedeflonglongII;typedefstructintnxt;intend;Edge;typedefstructMatrix_tagintn;intm;Ila33;Matrix-tag()Matrix_tag(intn_,intm_)n=n_;m=m_;for(registerinti=0;i<=n;i+)for(registerintj=0;j<=m;j+)ai11=4e18;)Matrix;intent=0;Matrixe;intv200007,a200007,b200007,head200007,depth200007,fa20000727,min-val200007;Ilsum200007;Edgeedge400007;Matrixeach200007,up20000718,down20000718;Matrixoperator*(Matrixa,Matrixb)Matrixans(a.n,b.m);for(registerinti=O;i<=a.n;i+)for(registerintj=O;j<=b.m;j+)for(registerintk=0;k<=a.m;k+)ans.aij=min(ans.aij,a.aik+b.akj);)returnans;)inlinevoidinit(intn)e=Matrix(n,n);for(registerinti=0;i<=n;i+)e.aii=0;)inlinevoidadd_edge(intstart,intend)ent+;edgecnt.nxt=headstart;headstart=ent;edgecnt.end=end;)voiddfs1(intu,intfather)intt;depthu=depthfather+1;t=Iog2(depthu);fau0=father;sumu=sumfather+vu;for(registerinti=1;i<=t;i+)faui=fafaui-1i-1;)for(registerinti=headu;i!=0;i=edgei.nxt)intx=edgei.end;if(x!=father)dfs1(x,u);inlineintlca(intu,intv)if(depthu<depthv)swap(u,v);while(depthu>depthv)u=fau(int)log2(depthu-depthv);if(u=v)returnu;for(registerinti=Iog2(depthu);i>=0;i-)if(faui!=favi)u=faui;V=favi;returnfauO;)voiddfs2(intu,intk)intt=Iog2(depthu);Matrixmat(k-1,k-1)；if(k=2)mat.a00=mat.a10=vu;mat.a01=O;elsemat.a00=mat.a10=mat.a20=vu;mat.a01=mat.a12=O;mat.a11=min-valu;)eachu=upuO=downu0=mat;for(registerinti=1;i<=t;i+)intx=faui-1;upui=upui-1*upxi-1;downui=downxi-1*downui-1;for(registerinti=headu;i!=0;i=edgei.nxt)intx=edgei.end;if(x!=fauO)dfs2(x,k);Matrixget_up(intu,intv)Matrixans=e;while(depthu>depthv)intx=Iog2(depthu-depthv);ans=ans*upux;u=faux;)if(u=v)ans=ans*eachu;returnans;)Matrixget_down(intu,intv)Matrixans=e;while(depthu>depthv+1)intx=Iog2(depthu-depthv-1);ans=downux*ans;u=faux;)if(depthu>depthv)ans=eachu*ans;returnans;)intmain()intn,q,k;scanf(,'%d%d%du,&n,&q,&k);for(registerinti=1;i<=n;i+)scanf(,'%d,'j&vi);)for(registerinti=1;i<n;i+)scanf(11%d%d",&ai,&bi);add_edge(ai,bi);add_edge(bi,ai);)dfs1(1,0);if(k=1)for(registerinti=1;i<=q;i+)ints,t,curjca;scanf(,'%d%d",&s,&t);curjca=lca(s,t);cout«sums+sumt-sumcurjca-sumfacurjca«endl;)elseinit(k-1);for(registerinti=1;i<=n;i+)min_vali=0x7fffffff;)for(registerinti=1;i<n;i+)min_valai=min(min_valai,vbi);min_valbi=min(min_valbi,vai);dfs2(1,k);for(registerinti=1;i<=q;i+)ints,t;scanf(,'%d%d",&s,&t);intcurjca=lca(s,t);Matrixmat;if(curjca=s)mat=e;elsemat=get_up(fasO,curjca);)if(curjca!=t)mat=mat*get_down(t,curjca);cout«mat.a00+vs«endl;)returnO;4 .星战include<bitsstdc+.h>#defineN500010usingnamespacestd;intn,m,q,i;unsignedlonglongsum,ans,valN,posN,pos2N;pair<int,int>eN;intmain()(srand(time(O),cin»n»m;for(i=1;i<=n;i+)vali=rand(),sum+=vali;for(i=1;i<=m;i+)cin»ei.first»ei.second;ans+=valei.first;posei.second+=valei.first;)for(i=1;i<=n;i+)pos2i=posi;cin»q;for(i=1;i<=q;i+)(intopt;cin»opt;intop=(opt=1opt=2?-1:1);if(opt=1Hopt=3)(intx,y;cin»x»y;if(opt=1)posy-=valx,ans-=valx;elseposy+=valx,ans+=valx;)if(opt=2Hopt=4)intx;cin»x;if(opt=2)ans-=posx,posx=0;elseans+=pos2x-posx,posx=pos2x;)puts(sum=ans?"YES":',NO");)