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

T1 假期计划（holiday） T2 策略游戏（game） T3 星战(galaxy) T4数据传输(transmit) 答案部分 1. 策略游戏 #include<iostream> #include<cstdio> using namespace std; const int inf=1<<30; typedef long long ll; ll a[100005],b[100005];int n,m,q,l1,r1,l2,r2,sa[100005],sb[100005],lg2[100005]; struct ST { ll st[100005][17]; int tp1,tp2; ll query(int l,int r) { int k=lg2[r-l+1]; if(tp1==1) return min(st[l][k],st[r-(1<<k)+1][k]); if(tp1==2) return max(st[l][k],st[r-(1<<k)+1][k]); } void build(int n,ll *f) { for(int i=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(int i=1;i<=16;i++) for(int j=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; int main() { scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=m;i++) scanf("%lld",&b[i]); for(int i=1;i<=n;i++) sa[i]=sa[i-1]+(a[i]<0); for(int i=1;i<=m;i++) sb[i]=sb[i-1]+(b[i]<0); for(int i=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); int fa1=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; ll amx1,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 ",amx2*bmn2); else printf("%lld ",amn2*bmx1); } else if(