当前位置: 首页 > news >正文

P8818 [CSP-S 2022] 策略游戏

题目传送门

闲聊:本蒟蒻调了两天……

(以下称先手为A,后手为B)

首先\(c\)矩阵就是个诈骗的障眼法,真正的题面应该是这样:

给你两个固定的数组\(a\)\(b\),每次询问给你\(l1\)\(l2\)\(r1\)\(r2\),A要先选一个数,这个数在\(a\)数组中,且这个数对应的下标在\([l1,r1]\)范围里。B后选一个\(b\)数组中的数,同样,这个数对应的下表在\([l2,r2]\)范围里。

设A选的数是\(x\),B选的数是\(y\),则最终结果是\(x \times y\)。A要让结果最大,B要让结果最小,求最终结果会是什么。

首先,由于\(a\)\(b\)数组里的数有正有负,符号会影响两人最终的决策,所以我们不妨比较笨地分讨一下。

1.如果\(b\)的选定区间里全是非负数:

①如果此时\(a\)的选定区间里全是负数,那么B知道A会选负数,B为了让值尽可能小,一定会选最大的非负数。那么A思考后知道B会选最大的非负数,A为了让最终结果最大,必然选择绝对值最小的负数(也就是\(a\)中的最大值)。

②如果\(a\)的选定区间中有非负数,那么A首先一定会选非负数(为了让结果非负) ,B思考到这一层后(即A会选非负数),为了让结果最小一定会选最小的非负数(或者说,\(b\)选定区间中的最小值)。A的话知道B选非负数,那么为了让结果最大,他会选择\(a\)选定区间中的最大非负数(即最大值)。

2.如果\(b\)的选定区间里全是负数:

③如果此时\(a\)的选定区间里全是非负数,类似①,B会选绝对值最大的负数(最小的负数),A预判了B的预判,A会选最小的非负数(也就是\(a\)选定区间中的最小值)。

④如果\(a\)的选定区间中有负数,那么类似②,B知道A会选负数,B会选一个绝对值最小的负数(也就是\(b\)选定区间中的最大值),A思考B的思考后,会选择绝对值最大的负数(也就是\(a\)选定区间中的最小值)。

3.如果\(b\)的选定区间里两种都有:

⑤如果\(a\)选定区间中全部为非负数,首先B一定不会选非负数(防止结果非负),这样问题就转化为了③的那种情景,B选最小值,A选最小值。

⑥如果\(a\)选定区间中全部为负数,那么类似⑤,B一定不会选负数(这样结果就大于0了),问题转化为①,B选最大值,A选最大值。

⑦如果\(a\)也是两种都有,那么A有两种决策:一种是选非负数,那么B就会选负数,同③,B选最小值,A选最小的非负数(注意A要在非负数里选一个)。另一种是选负数,那么B就会选负数,同①,B选最大值,A选最大的负数

这样,由于\(a\)\(b\)都是静态数组,我们用六个ST表维护六个值:\(a\)数组区间最大最小值、\(a\)数组区间非负数区间最小值、\(a\)数组负数区间最大值、以及\(b\)数组区间最大最小值。

至于如何维护\(a\)数组区间非负数区间最小值和\(a\)数组负数区间最大值,我们新开两个数组(以下称\(a1\)\(a2\)),\(a1\)数组在\(a\)数组的基础上,把所有负数修改为一个极大值,同理\(a2\)数组在\(a\)数组的基础上把所有非负数修改为一个极小值。然后正常使用ST表求最值即可。

时间复杂度\(O(nlogn+q)\)

理论上本题还可以使用线段树维护区间最值,这里我采用的是ST表,只贴ST表代码。

P8818_ST表
#include<bits/stdc++.h>
#define int long long
using namespace std;inline int read(){int x=0,f=1;char c=getchar();while(c<48){if(c=='-') f=-1;c=getchar();} while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}const int N=1e5+5;
const int inf=2e18;//极大值一定要往大里赋,否则过不了sub1 
int n,m,q,a[N],b[N],a1[N],a2[N],f[6][21][N];
//f[0][...][...]:a数组区间最大值
//f[1][...][...]:a数组区间最小值 
//f[2][...][...]:a数组非负数区间最小值
//f[3][...][...]:a数组负数区间最大值
//f[4][...][...]:b数组区间最大值
//f[5][...][...]:b数组区间最小值 inline void init(){//初始化 for(int i=1;i<=n;i++){f[0][0][i]=a[i],f[1][0][i]=a[i];f[2][0][i]=a1[i],f[3][0][i]=a2[i];}for(int i=1;i<=m;i++){f[4][0][i]=f[5][0][i]=b[i];}//ST表求值 for(int i=1;i<=20;i++){for(int j=1;j+(1<<i)-1<=n;j++){f[0][i][j]=max(f[0][i-1][j],f[0][i-1][j+(1<<(i-1))]);f[1][i][j]=min(f[1][i-1][j],f[1][i-1][j+(1<<(i-1))]);f[2][i][j]=min(f[2][i-1][j],f[2][i-1][j+(1<<(i-1))]);f[3][i][j]=max(f[3][i-1][j],f[3][i-1][j+(1<<(i-1))]);f[4][i][j]=max(f[4][i-1][j],f[4][i-1][j+(1<<(i-1))]);f[5][i][j]=min(f[5][i-1][j],f[5][i-1][j+(1<<(i-1))]);}}
}signed main(){n=read(),m=read(),q=read();//a1、a2数组定义同题解 for(int i=1;i<=n;i++){a[i]=read();//a1、a2数组初始化 if(a[i]>=0){a2[i]=-inf,a1[i]=a[i];}else{a2[i]=a[i],a1[i]=inf;}}for(int i=1;i<=m;i++){b[i]=read();}init();for(int i=1;i<=q;i++){int l1=read(),r1=read(),l2=read(),r2=read();int ln1=log(r1-l1+1)/log(2),ln2=log(r2-l2+1)/log(2);int c1,c2,c3,c4,c5,c6,ans=-inf;c1=max(f[0][ln1][l1],f[0][ln1][r1-(1<<ln1)+1]);//amaxc2=min(f[2][ln1][l1],f[2][ln1][r1-(1<<ln1)+1]);//a1minc3=max(f[3][ln1][l1],f[3][ln1][r1-(1<<ln1)+1]);//a2maxc4=min(f[1][ln1][l1],f[1][ln1][r1-(1<<ln1)+1]);//aminc5=max(f[4][ln2][l2],f[4][ln2][r2-(1<<ln2)+1]);//bmaxc6=min(f[5][ln2][l2],f[5][ln2][r2-(1<<ln2)+1]);//bmin//c1:a数组区间最大值//c2:a数组非负数区间最小值//c3:a数组负数区间最大值//c4:a数组区间最小值//c5:b数组区间最大值//c6:b数组区间最小值if(c6>=0){if(c1<0){//case1ans=max(ans,c1*c5);	}else{//case2ans=max(ans,c6*c1);}}else if(c5<0){if(c4>=0){//case3ans=max(ans,c6*c4);}else{//case4ans=max(ans,c5*c4);}}else{if(c4>=0){//case5ans=max(ans,c6*c4);}else if(c1<0){//case6ans=max(ans,c5*c1);}else{ans=max(ans,max(c6*c2,c5*c3));//case7}}printf("%lld\n",ans);}return 0;
} 
http://www.hskmm.com/?act=detail&tid=16150

相关文章:

  • FortiGate连接中国联通SDWAN
  • 第五章 运算符、表达式和语句
  • 学习问题日记-2
  • 封神台复现
  • 李之一的Java第一作
  • 2025.9.24 闲话:Lucas 定理究极证明
  • Are English people good or bad
  • 9
  • Lampiao靶场渗透wp-脏牛提权
  • 画矩形
  • NOIP 模拟赛八
  • 第三篇
  • 基于cloacked-pixel隐写工具爆破项目
  • 随便写的
  • Bcliux-docker-nacos2.2.0升级至2.2.3版本
  • 社交网络架构。京东场景题:亿级用户100Wqps 社交关系如何设计?如何查看我的关注,关注我的?
  • go 面试题
  • 事件和图形界面(暂未完成)
  • 什么是sql 慢日志。哈罗面试:没开sql慢日志,怎么发现慢 sql?
  • Spring连环炮。哈罗面试:Spring Bean生命周期,Spring怎么创建Bean的,BFPP和BPP的x别
  • redis 大 key 优化。哈罗面试:redis 有个大 key需要在线优化, 不能影响现有业务,请求不能大量到库,怎么优化?
  • ACL高可用架构。希音面试:第三方挂了,我们总在背锅。来一 靠谱的 高可用方案,让 外部依赖 稳如泰山
  • 软工9.24
  • 2025CSP-S模拟赛51
  • 2025年9月24日 - 20243867孙堃2405
  • 【星海随笔】RabbitMQ开发篇 - 教程
  • P13754 【MX-X17-T3】Distraction
  • 2025.9.24
  • 初学汇编
  • 架构图设计还得是华为 - 智慧园区