复赛2:策略游戏

P8818

若 B 只有正数:
若 A 有正数,那么答案一定为正数, A取最大值,B取最小值,两者相乘。
若 A没有正数,那么答案一定为负数,A取最大值,B取最大值,两者相乘。

若B只有负数:
若A 有负数,那么答案一定为正数, A取最小值,B取值最大值,两者相乘。
若 A 没有负数,那么答案一定为负数, A取最小值,B取最小值,两者相乘。

若B 有正有负:答案一定是负数
若A没有正数,A取最大值,B取最大值,两者相乘。
若A没有负数,A取最小值 ,B取最小值 ,两者相乘。
若A有正有负,取A的正数最小值与B的最小值乘积和A的负数最大值与B的最大值乘积,两者中大的。

代码实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**************************************************************** 
 * Description: 2022_S_R2_2 策略游戏
 * Author: Alex Li
 * Date: 2023-10-03 12:02:39
 * LastEditTime: 2023-10-04 23:55:35
****************************************************************/
#include <iostream>
#include <limits.h>
//把long long型定义成LL
typedef long long LL;
using namespace std;

int n,m,q,x;
LL ans; //两个整数类型的乘积可能会超过整数范围,所以要用long long
const int maxn=1e5+5;//n和m的数据最大10^5
const int maxm=1e5+5;
const int mlgn=25; //指数下标,25足够大
const int mlgm=25;

// 6 个 ST 表
// amx:a 的区间最大值,amn:a 的区间最小值,afx:a 的负数区间最大值,azn:a 的非负数区间最小值。
// bmx:b 的区间最大值,bmn:b 的区间最小值。bfx:
int amx[maxn][mlgn],amn[maxn][mlgn],afx[maxn][mlgn],azn[maxn][mlgn];
int bmx[maxm][mlgm],bmn[maxm][mlgm];
int lg[maxn];
//打ST表,把区间最值求出来,详见ST表建立讲解
void ST(){
   for (int i = 2; i <=max(n,m);i++)lg[i]=lg[i/2]+1;
    //A数组建表 
    for (int j = 1; j <= lg[n]; j++){
        for(int i=1;i+(1<<j)-1<=n;++i){
            int p=i+(1<<(j-1));
            amx[i][j]=max(amx[i][j-1],amx[p][j-1]);
            afx[i][j]=max(afx[i][j-1],afx[p][j-1]);
            amn[i][j]=min(amn[i][j-1],amn[p][j-1]);
            azn[i][j]=min(azn[i][j-1],azn[p][j-1]);
        } 
    }
    //B数组建表
    for (int j = 1; j <=lg[m]; j++){
       for (int i = 1; i+(1<<j)-1 <=m; i++){
        int p=i+(1<<(j-1));
        bmx[i][j]=max(bmx[i][j-1],bmx[p][j-1]);
        bmn[i][j]=min(bmn[i][j-1],bmn[p][j-1]);
  
       }
    }
        
}

int main(){
    cin>>n>>m>>q;
    for (int i = 1; i <=n; i++){
        cin>>x;
        amx[i][0]=x;
        amn[i][0]=x;
        afx[i][0]=(x<0?x:INT_MIN); //INT_MIN是int型最小值
        azn[i][0]=(x>=0?x:INT_MAX);//INT_MAX是int型最大值
   }
    for (int i = 1; i <=m; i++){
         cin>>x;
        bmx[i][0]=x;
        bmn[i][0]=x;
    }
    
    ST();//建表
    while(q--){
        int la,ra,lb,rb;
        cin>>la>>ra>>lb>>rb;
       
        int sa=lg[ra-la+1],sb=lg[rb-lb+1];
        int pa=ra-(1<<sa)+1,pb=rb-(1<<sb)+1;

        int amax=max(amx[la][sa],amx[pa][sa]);//A区间最大值
        int amin=min(amn[la][sa],amn[pa][sa]);//A区间最小值
        int afmx=max(afx[la][sa],afx[pa][sa]);//A区间负数中最大值 
        int azmn=min(azn[la][sa],azn[pa][sa]);//A区间正数中最小值
        int bmax=max(bmx[lb][sb],bmx[pb][sb]);//B区间最大值
        int bmin=min(bmn[lb][sb],bmn[pb][sb]);//B区间最小值 
       
        if(bmin>=0){                      //若 B 只有正数:
            if(amax>=0)ans=(LL)amax*bmin;//若A有正数,那么答案一定为正数,A取最大值,B取最小值,两者相乘。
            else ans=(LL)amax*bmax;      //若A没有正数,那么答案一定为负数,A取最大值,B取最大值,两者相乘。
        }else if(bmax<0){                //若B只有负数:
            if(amin<0)ans=(LL)amin*bmax;// 若A有负数,那么答案一定为正数,A取最小值,B取值最大值,两者相乘。
            else ans=(LL)amin*bmin;     //若A没有负数,那么答案一定为负数, A取最小值,B取最小值,两者相乘。
        }else {                         //若B有正有负:答案一定是负数
            if(amax<0)ans=(LL)amax*bmax;//若A没有正数,A取最大值,B取最大值,两者相乘。
            else if(amin>=0)ans=(LL)amin*bmin;//若A没有负数,A取最小值 ,B取最小值 ,两者相乘。
            else ans=max((LL)azmn*bmin,(LL)afmx*bmax);
           //若A有正有负,取A的正数最小值与B的最小值乘积和A的负数最大值与B的最大值乘积,两者中大的。
        }
 
   cout<<ans<<endl;        
   }
    return 0;
}
Scroll to Top