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

T1假期计划（holiday）T2策略游戏（game）T3星战(galaxy)T4数据传输(transmit)答案部分策略游戏#include<iostream>#include<cstdio>usingnamespacestd;constintinf=1<<30;typedeflonglongll;lla[100005],b[100005];intn,m,q,l1,r1,l2,r2,sa[100005],sb[100005],lg2[100005];structST{ llst[100005][17]; inttp1,tp2; llquery(intl,intr) { intk=lg2[r-l+1]; if(tp1==1)returnmin(st[l][k],st[r-(1<<k)+1][k]); if(tp1==2)returnmax(st[l][k],st[r-(1<<k)+1][k]); } voidbuild(intn,ll*f) { for(inti=1;i<=n;i++) { if(tp2==1)st[i][0]=(f[i]>=0?f[i]:(tp1==1?inf:-inf)); if(tp2==2)st[i][0]=(f[i]<0?-f[i]:(tp1==1?inf:-inf)); } for(inti=1;i<=16;i++) for(intj=1;j+(1<<i)-1<=n;j++) { if(tp1==1)st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]); if(tp1==2)st[j][i]=max(st[j][i-1],st[j+(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",&a[i]); for(inti=1;i<=m;i++)scanf("%lld",&b[i]); for(inti=1;i<=n;i++)sa[i]=sa[i-1]+(a[i]<0); for(inti=1;i<=m;i++)sb[i]=sb[i-1]+(b[i]<0); for(inti=2;i<=100000;i++)lg2[i]=lg2[i/2]+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("%d%d%d%d",&l1,&r1,&l2,&r2); intfa1=0,fa2=0,fb1=0,fb2=0; if(sa[r1]-sa[l1-1]==r1-l1+1)fa1=1; if(sa[r1]-sa[l1-1]==0)fa2=1; if(sb[r2]-sb[l2-1]==r2-l2+1)fb1=1; if(sb[r2]-sb[l2-1]==0)fb2=1; llamx1,amx2,amn1,amn2,bmx1,bmx2,bmn1,bmn2; amx1=mxa1.query(l1,r1); amx2=-mxa2.query(l1,r1); amn1=mna1.query(l1,r1); amn2=-mna2.query(l1,r1); bmx1=mxb1.query(l2,r2); bmx2=-mxb2.query(l2,r2); bmn1=mnb1.query(l2,r2); bmn2=-mnb2.query(l2,r2); if(fa1) { if(fb1)printf("%lld\n",amx2*bmn2); elseprintf("%lld\n",amn2*bmx1); } elseif(fa2) { if(fb2)printf("%lld\n",amx1*bmn1); elseprintf("%lld\n",amn1*bmx2); } else { if(fb1)printf("%lld\n",amx2*bmn2); elseif(fb2)printf("%lld\n",amx1*bmn1); elseprintf("%lld\n",max(amn1*bmx2,amn2*bmx1)); } } return0;}假期计划#include<iostream>#include<queue>usingnamespacestd;typedeflonglongll;typedefstruct{ intnxt; intend;}Edge;intcnt=0;intdis[2507][2507],head[2507],pos[2507][7];lls[2507],f[2507][2507];Edgeedge[20007];queue<int>q;inlinevoidinit(intn){ for(registerinti=1;i<=n;i++){ for(registerintj=1;j<=n;j++){ dis[i][j]=0x7fffffff; } }}inlinevoidadd_edge(intstart,intend){ cnt++; edge[cnt].nxt=head[start]; head[start]=cnt; edge[cnt].end=end;}voidbfs(intstart,intn){ dis[start][start]=0; q.push(start); while(!q.empty()){ intcur=q.front(); q.pop(); for(registerinti=head[cur];i!=0;i=edge[i].nxt){ intx=edge[i].end; if(dis[start][x]==0x7fffffff){ dis[start][x]=dis[start][cur]+1; q.push(x); } } }}intmain(){ intn,m,k; llans=0; cin>>n>>m>>k; k++; init(n); for(registerinti=2;i<=n;i++){ cin>>s[i]; } 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&&dis[1][i]<=k&&dis[i][j]<=k){ f[i][j]=s[i]+s[j]; }else{ f[i][j]=-4e18; } } } for(registerinti=2;i<=n;i++){ pos[i][1]=pos[i][2]=pos[i][3]=i; for(registerintj=2;j<=n;j++){ if(f[pos[i][1]][i]<f[j][i]){ pos[i][3]=pos[i][2]; pos[i][2]=pos[i][1]; pos[i][1]=j; }elseif(f[pos[i][2]][i]<f[j][i]){ pos[i][3]=pos[i][2]; pos[i][2]=j; }elseif(f[pos[i][3]][i]<f[j][i]){ pos[i][3]=j; } } } for(registerinti=2;i<=n;i++){ for(registerintj=2;j<=n;j++){ if(i!=j&&dis[i][j]<=k){ for(registerintx=1;x<=3;x++){ for(registerinty=1;y<=3;y++){ if(pos[i][x]!=j&&pos[i][x]!=pos[j][y]&&pos[j][y]!=i){ ans=max(ans,f[pos[i][x]][i]+f[pos[j][y]][j]); break; } } } } } } cout<<ans; return0;}数据传输#include<iostream>#include<cstdio>#include<cmath>#include<cstring>usingnamespacestd;typedeflonglongll;typedefstruct{ intnxt; intend;}Edge;typedefstructMatrix_tag{ intn; intm; lla[3][3]; Matrix_tag(){} Matrix_tag(intn_,intm_){ n=n_; m=m_; for(registerinti=0;i<=n;i++){ for(registerintj=0;j<=m;j++){ a[i][j]=4e18; } } }}Matrix;intcnt=0;Matrixe;intv[200007],a[200007],b[200007],head[200007],depth[200007],fa[200007][27],min_val[200007];llsum[200007];Edgeedge[400007];Matrixeach[200007],up[200007][18],down[200007][18];Matrixoperator*(Matrixa,Matrixb){ Matrixans(a.n,b.m); for(registerinti=0;i<=a.n;i++){ for(registerintj=0;j<=b.m;j++){ for(registerintk=0;k<=a.m;k++){ ans.a[i][j]=min(ans.a[i][j],a.a[i][k]+b.a[k][j]); } } } returnans;}inlinevoidinit(intn){ e=Matrix(n,n); for(registerinti=0;i<=n;i++){ e.a[i][i]=0; }}inlinevoidadd_edge(intstart,intend){ cnt++; edge[cnt].nxt=head[start]; head[start]=cnt; edge[cnt].end=end;}voiddfs1(intu,intfather){ intt; depth[u]=depth[father]+1; t=log2(depth[u]); fa[u][0]=father; sum[u]=sum[father]+v[u]; for(registerinti=1;i<=t;i++){ fa[u][i]=fa[fa[u][i-1]][i-1]; } for(registerinti=head[u];i!=0;i=edge[i].nxt){ intx=edge[i].end; if(x!=father)dfs1(x,u); }}inlineintlca(intu,intv){ if(depth[u]<depth[v])swap(u,v); while(depth[u]>depth[v])u=fa[u][(int)log2(depth[u]-depth[v])]; if(u==v)returnu; for(registerinti=log2(depth[u]);i>=0;i--){ if(fa[u][i]!=fa[v][i]){ u=fa[u][i]; v=fa[v][i]; } } returnfa[u][0];}voiddfs2(intu,intk){ intt=log2(depth[u]); Matrixmat(k-1,k-1); if(k==2){ mat.a[0][0]=mat.a[1][0]=v[u]; mat.a[0][1]=0; }else{ mat.a[0][0]=mat.a[1][0]=mat.a[2][0]=v[u]; mat.a[0][1]=mat.a[1][2]=0; mat.a[1][1]=min_val[u]; } each[u]=up[u][0]=down[u][0]=mat; for(registerinti=1;i<=t;i++){ intx=fa[u][i-1]; up[u][i]=up[u][i-1]*up[x][i-1]; down[u][i]=down[x][i-1]*down[u][i-1]; } for(registerinti=head[u];i!=0;i=edge[i].nxt){ intx=edge[i].end; if(x!=fa[u][0])dfs2(x,k); }}Matrixget_up(intu,intv){ Matrixans=e; while(depth[u]>depth[v]){ intx=log2(depth[u]-depth[v]); ans=ans*up[u][x]; u=fa[u][x]; } if(u==v)ans=ans*each[u]; returnans;}Matrixget_down(intu,intv){ Matrixans=e; while(depth[u]>depth[v]+1){ intx=log2(depth[u]-depth[v]-1); ans=down[u][x]*ans; u=fa[u][x]; } if(depth[u]>depth[v])ans=each[u]*ans; returnans;}intmain(){ intn,q,k; scanf("%d%d%d",&n,&q,&k); for(registerinti=1;i<=n;i++){ scanf("%d",&v[i]); } for(registerinti=1;i<n;i++){ scanf("%d%d",&a[i],&b[i]); add_edge(a[i],b[i]); add_edge(b[i],a[i]); } dfs1(1,0); if(k==1){ for(registerinti=1;i<=q;i++){ ints,t,cur_lca; scanf("%d%d",&s,&t); cur_lca=lca(s,t); cout<<sum[s]+sum[t]-sum[cur_lca]-sum[fa[cur_lca][0]]<<endl; } }else{ init(k-1); for(registerinti=1;i<=n;i++){ min_val[i]=0x7fffffff; } for(registerinti=1;i<n;i++){ min_val[a[i]]=min(min_val[a[i]],v[b[i]]); min_val[b[i]]=min(min_val[b[i]],v[a[i]]); } dfs2(1,k); for(registerinti=1;i<=q;i++){ ints,t; scanf("%d%d",&s,&t); intcur_lca=lca(s,t); Matrixmat; if(cur_lca==s){ mat=e; }else{ mat=get_up(fa[s][0],cur_lca); } if(cur_lca!=t)mat=mat*get_down(t,cur_lca); cout<<mat.a[0][0]+v[s]<<endl; } } return0;}星战#include<bits/stdc++.h>#defineN500010usingnamespacestd;intn,m,q,i;unsignedlonglongsum,ans,val[N],pos[N],p