admin 管理员组

文章数量: 1184232

[CSP

P8818 [CSP-S 2022] 策略游戏 题面

今年到现在也没写总结，也快失去写它的欲望了，五味杂陈，想说出的理由有很多，想来还是罢了，毕竟也已经没有了意义…

这题可能是往年以来最容易的第二题了，可惜考试时钻T1失去了很多时间，T2无法完成，感觉考试时心里目标不高，导致实际结果更差。

分 A ≥ 0 , A < 0 , B ≥ 0 , B < 0 A \geq0,A<0,B\geq0,B<0 A≥0,A<0,B≥0,B<0 几种情况讨论，于是需要维护
A ≥ 0 A \geq0 A≥0最大值，最小值
A < 0 A<0 A<0最大值，最小值
B ≥ 0 B\geq0 B≥0最大值，最小值
B < 0 B<0 B<0最大值，最小值
使用八棵线段树即可，没有什么思维深度。（当然也有六个ST表的，没有什么区别）

最后再根据5种不同情况制定相应策略即可，分别是：

  • 以A（即甲）为主导： { A 有 非 负 数 ， B 无 负 数 A 有 负 数 ， B 无 非 负 数 \left\{\begin{matrix}A有非负数，B无负数\\A有负数，B无非负数\end{matrix}\right. {A有非负数，B无负数A有负数，B无非负数​
  • 以B（即乙）为主导： { B 有 非 负 数 ， A 无 非 负 数 B 有 负 数 ， A 无 负 数 \left\{\begin{matrix}B有非负数，A无非负数\\B有负数，A无负数\end{matrix}\right. {B有非负数，A无非负数B有负数，A无负数​
  • A，B非负数，负数兼备。

码就是了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+5,BZ=-1e9-1;
int n,m,q;
struct qh{LL a[N],tr[N<<2];int bz;#define M (l+r>>1)#define ls (id<<1)#define rs (ls|1)void pushup(int bz,int id){if(tr[ls]==BZ&&tr[rs]==BZ) tr[id]=BZ;else if(tr[ls]!=BZ&&tr[rs]!=BZ) tr[id]=bz==1?max(tr[ls],tr[rs]):min(tr[ls],tr[rs]);else if(tr[ls]==BZ) tr[id]=tr[rs];else if(tr[rs]==BZ) tr[id]=tr[ls];return ;}void build(int id,int l,int r){if(l==r){tr[id]=a[l];return ;}build(ls,l,M);build(rs,M+1,r);pushup(bz,id);}LL queryn(int id,int l,int r,int x,int y){if(x<=l&&r<=y) return tr[id];LL mn=1e10;if(x<=M){LL q=queryn(ls,l,M,x,y);if(q!=BZ) mn=min(mn,q);}if(M<y){LL q=queryn(rs,M+1,r,x,y);if(q!=BZ) mn=min(mn,q);}return mn;}LL queryx(int id,int l,int r,int x,int y){if(x<=l&&r<=y) return tr[id];LL mx=BZ;if(x<=M){LL q=queryx(ls,l,M,x,y);if(q!=BZ) mx=max(mx,q);}if(M<y){LL q=queryx(rs,M+1,r,x,y);if(q!=BZ) mx=max(mx,q);}return mx;}
}axz,anz,bxz,bnz,axf,anf,bxf,bnf;
inline int Rd(){int s=0,w=1;char ch=getchar();while (ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}while (ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();return s*w;
}
int main(){// freopen("game4.in","r",stdin);// freopen("game.out","w",stdout);n=Rd();m=Rd();q=Rd();axz.bz=bxz.bz=1;axf.bz=bxf.bz=1;anz.bz=bnz.bz=2;anf.bz=bnf.bz=2;for(int i=1,x;i<=n;i++) x=Rd(),axz.a[i]=anz.a[i]=(x>=0?x:BZ), axf.a[i]=anf.a[i]=(x<0?x:BZ);for(int i=1,x;i<=m;i++) x=Rd(),bxz.a[i]=bnz.a[i]=(x>=0?x:BZ),bxf.a[i]=bnf.a[i]=(x<0?x:BZ);axz.build(1,1,n);anz.build(1,1,n);bxz.build(1,1,m);bnz.build(1,1,m);axf.build(1,1,n);anf.build(1,1,n);bxf.build(1,1,m);bnf.build(1,1,m);while (q--){int l1=Rd(),r1=Rd(),l2=Rd(),r2=Rd();LL Axz=axz.queryx(1,1,n,l1,r1),Axf=axf.queryx(1,1,n,l1,r1),Anz=anz.queryn(1,1,n,l1,r1),Anf=anf.queryn(1,1,n,l1,r1),Bxz=bxz.queryx(1,1,m,l2,r2),Bxf=bxf.queryx(1,1,m,l2,r2),Bnz=bnz.queryn(1,1,m,l2,r2),Bnf=bnf.queryn(1,1,m,l2,r2);LL A=0,B=0;// printf("%lld %lld %lld %lld %lld %lld %lld %lld\n",Axz,Axf,Anz,Anf,Bxz,Bxf,Bnz,Bnf);if(Axz!=BZ&&Bxf==BZ) A=Axz,B=Bnz;else if(Axf!=BZ&&Bxz==BZ) A=Anf,B=Bxf;else if(Bxf!=BZ&&Axf==BZ) A=Anz,B=Bnf;else if(Bxz!=BZ&&Axz==BZ) A=Axf,B=Bxz;else{if(Axf*Bxz>Anz*Bnf) A=Axf,B=Bxz;else A=Anz,B=Bnf;}printf("%lld\n",A*B);}return 0;
}
/*
start coding:10:23
stop:10:46
continue:11:19
stop:12:00
continue:15:04
finish debuging:15:11
*/

71分钟一遍过，哭死

本文标签： CSP

版权声明：本文标题：[CSP 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1687349491a92488.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。