复赛二：策略游戏(game)
洛谷P8818
OJ：P5942
小 L 和小 Q 在玩一个策略游戏。
有一个长度为 n 的数组 A 和一个长度为 m 的数组 B，在此基础上定义一个大小为 n×m 的矩阵 C，满足 Cij=Ai×Bj。所有下标均从 1 开始。
游戏一共会进行 q 轮，在每一轮游戏中，会事先给出 4 个参数 l1,r1,l2,r2，满足 1≤l1≤r1≤n、1≤l2≤r2≤m。
游戏中，小 L 先选择一个 l1∼r1之间的下标 x，然后小 Q 选择一个 l2∼r2之间的下标 y。定义这一轮游戏中二人的得分是 Cxy。
小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。
请问：按照二人的最优策略，每轮游戏的得分分别是多少？
输入格式
第一行输入三个正整数 n,m,q，分别表示数组 A，数组 B 的长度和游戏轮数。
第二行：n 个整数，表示 Ai，分别表示数组 A 的元素。
第三行：m 个整数，表示 Bi，分别表示数组 B的元素。
接下来 q行，每行四个正整数，表示这一次游戏的 l1,r1,l2,r2。
输出格式
输出共 q 行，每行一个整数，分别表示每一轮游戏中，小 L 和小 Q 在最优策略下的得分。
输入输出样例
输入 #1
3 2 2 0 1 -2 -3 4 1 3 1 2 2 3 2 2
输出 1
0
4
输入 #2
6 4 5
3 -1 -2 1 2 0
1 2 -1 -3
1 6 1 4
1 5 1 4
1 4 1 2
2 6 3 4
2 5 2 3
输出 #2
0
-2
3
2
-1
若 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的最大值乘积，两者中大的。
若A有零时， 取A为零
代码实现：
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 | /**************************************************************** * 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; } |