[CSP-S 2022] 策略游戏
[CSP-S 2022] 策略游戏
题目描述
小 L 和小 Q 在玩一个策略游戏。
有一个长度为 n n n 的数组 A A A 和一个长度为 m m m 的数组 B B B,在此基础上定义一个大小为 n × m n \times m n×m 的矩阵 C C C,满足 C i j = A i × B j C_{i j} = A_i \times B_j Cij=Ai×Bj。所有下标均从 1 1 1 开始。
游戏一共会进行 q q q 轮,在每一轮游戏中,会事先给出 4 4 4 个参数 l 1 , r 1 , l 2 , r 2 l_1, r_1, l_2, r_2 l1,r1,l2,r2,满足 1 ≤ l 1 ≤ r 1 ≤ n 1 \le l_1 \le r_1 \le n 1≤l1≤r1≤n、 1 ≤ l 2 ≤ r 2 ≤ m 1 \le l_2 \le r_2 \le m 1≤l2≤r2≤m。
游戏中,小 L 先选择一个 l 1 ∼ r 1 l_1 \sim r_1 l1∼r1 之间的下标 x x x,然后小 Q 选择一个 l 2 ∼ r 2 l_2 \sim r_2 l2∼r2 之间的下标 y y y。定义这一轮游戏中二人的得分是 C x y C_{x y} Cxy。
小 L 的目标是使得这个得分尽可能大,小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家,每次都会采用最优的策略。
请问:按照二人的最优策略,每轮游戏的得分分别是多少?
输入格式
第一行输入三个正整数 n , m , q n, m, q n,m,q,分别表示数组 A A A,数组 B B B 的长度和游戏轮数。
第二行: n n n 个整数,表示 A i A_i Ai,分别表示数组 A A A 的元素。
第三行: m m m 个整数,表示 B i B_i Bi,分别表示数组 B B B 的元素。
接下来 q q q 行,每行四个正整数,表示这一次游戏的 l 1 , r 1 , l 2 , r 2 l_1, r_1, l_2, r_2 l1,r1,l2,r2。
输出格式
输出共 q q q 行,每行一个整数,分别表示每一轮游戏中,小 L 和小 Q 在最优策略下的得分。
样例 #1
样例输入 #1
3 2 2
0 1 -2
-3 4
1 3 1 2
2 3 2 2
样例输出 #1
0
4
样例 #2
样例输入 #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
提示
【样例解释 #1】
这组数据中,矩阵 C C C 如下:
[ 0 0 − 3 4 6 − 8 ] \begin{bmatrix} 0 & 0 \\ -3 & 4 \\ 6 & -8 \end{bmatrix} 0−3604−8
在第一轮游戏中,无论小 L 选取的是 x = 2 x = 2 x=2 还是 x = 3 x = 3 x=3,小 Q 都有办法选择某个 y y y 使得最终的得分为负数。因此小 L 选择 x = 1 x = 1 x=1 是最优的,因为这样得分一定为 0 0 0。
而在第二轮游戏中,由于小 L 可以选 x = 2 x = 2 x=2,小 Q 只能选 y = 2 y = 2 y=2,如此得分为 4 4 4。
【样例 #3】
见附件中的 game/game3.in
与 game/game3.ans
。
【样例 #4】
见附件中的 game/game4.in
与 game/game4.ans
。
【数据范围】
对于所有数据, 1 ≤ n , m , q ≤ 10 5 1 \le n, m, q \le {10}^5 1≤n,m,q≤105, − 10 9 ≤ A i , B i ≤ 10 9 -{10}^9 \le A_i, B_i \le {10}^9 −109≤Ai,Bi≤109。对于每轮游戏而言, 1 ≤ l 1 ≤ r 1 ≤ n 1 \le l_1 \le r_1 \le n 1≤l1≤r1≤n, 1 ≤ l 2 ≤ r 2 ≤ m 1 \le l_2 \le r_2 \le m 1≤l2≤r2≤m。
测试点编号 | n , m , q ≤ n, m, q \le n,m,q≤ | 特殊条件 |
---|---|---|
1 1 1 | 200 200 200 | 1, 2 |
2 2 2 | 200 200 200 | 1 |
3 3 3 | 200 200 200 | 2 |
4 ∼ 5 4 \sim 5 4∼5 | 200 200 200 | 无 |
6 6 6 | 1000 1000 1000 | 1, 2 |
7 ∼ 8 7 \sim 8 7∼8 | 1000 1000 1000 | 1 |
9 ∼ 10 9 \sim 10 9∼10 | 1000 1000 1000 | 2 |
11 ∼ 12 11 \sim 12 11∼12 | 1000 1000 1000 | 无 |
13 13 13 | 10 5 {10}^5 105 | 1, 2 |
14 ∼ 15 14 \sim 15 14∼15 | 10 5 {10}^5 105 | 1 |
16 ∼ 17 16 \sim 17 16∼17 | 10 5 {10}^5 105 | 2 |
18 ∼ 20 18 \sim 20 18∼20 | 10 5 {10}^5 105 | 无 |
其中,特殊性质 1 为:保证
A
i
,
B
i
>
0
A_i, B_i > 0
Ai,Bi>0。
特殊性质 2 为:保证对于每轮游戏而言,要么
l
1
=
r
1
l_1 = r_1
l1=r1,要么
l
2
=
r
2
l_2 = r_2
l2=r2。
分析
此题题目描述并不清晰,甚至用了矩阵和博弈论的描述,很难读懂,不妨对两人的方案分类讨论,若小L已经选择了a,那么小Q就会只关注正负问题:
条件 | a ≤ 0 a \le 0 a≤0 | a > 0 a> 0 a>0 |
---|---|---|
选择 | y m a x y_{max} ymax | y m i n y_{min} ymin |
那么我们需要维护B的最大和最小值
对于小L,他会考虑小Q会怎么走,所以我们需要分类讨论小L的思考:
条件 | 选择 |
---|---|
a > 0 , b > 0 a>0,b>0 a>0,b>0 | a m a x a_{max} amax |
a > 0 , b < 0 a>0,b<0 a>0,b<0 | a m i n a_{min} amin |
a < 0 , b > 0 a<0,b>0 a<0,b>0 | a m a x a_{max} amax |
a < 0 , b < 0 a<0,b<0 a<0,b<0 | a m i n a_{min} amin |
总共维护4个
对于维护,没有比st表更方便的了,不仅,他也是静态的
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e5 + 5;
const int K = 25;
inline bool gmx(int& a, int b) {
return b > a ? a = b, true : false;
}
int n, m, q, x, la, ra, lb, rb;
int lg[M];
const int maxinf = LONG_LONG_MAX, mininf = LONG_LONG_MIN;
struct st {
int f[M][K],i;
void init(int n) {
for (int j = 1; j <= lg[n]; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
int p = i + (1 << (j - 1));
if(i) f[i][j] = max(f[i][j - 1], f[p][j - 1]);
if(!i) f[i][j] = min(f[i][j - 1], f[p][j - 1]);
}
}
}
int query(int l, int r) {
int sa = lg[r - l + 1];
int pa = r - (1 << sa) + 1;
if (i) return max(f[l][sa], f[pa][sa]);
else return min(f[l][sa], f[pa][sa]);
}
}amax,amin,afx,azn,bmin,bmax;
signed main() {
amax.i = afx.i = bmax.i = 1;
amin.i = bmin.i = azn.i = 0;
cin >> n >> m >> q;
for (int i = 1; i <= n; ++i) {
cin >> x;
amax.f[i][0] = amin.f[i][0] = x;
afx.f[i][0] = (x < 0 ? x : mininf);
azn.f[i][0] = (x >= 0 ? x : maxinf);
}
for (int i = 1; i <= m; ++i) {
cin >> x;
bmax.f[i][0] = bmin.f[i][0] = x;
}
for (int i = 2; i <= max(n, m); ++i)
lg[i] = lg[i >> 1] + 1;
amax.init(n); afx.init(n);bmax.init(m);
for (int j = 1; j <= lg[n]; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
int p = i + (1 << (j - 1));
amin.f[i][j] = min(amin.f[i][j - 1], amin.f[p][j - 1]);
azn.f[i][j] = min(azn.f[i][j - 1], azn.f[p][j - 1]);
}
}
for (int j = 1; j <= lg[m]; ++j) {
for (int i = 1; i + (1 << j) - 1 <= m; ++i) {
int p = i + (1 << (j - 1));
// bmax.f[i][j] = max(bmax.f[i][j - 1], bmax.f[p][j - 1]);
bmin.f[i][j] = min(bmin.f[i][j - 1], bmin.f[p][j - 1]);
}
}
while (q--) {
cin >> la >> ra >> lb >> rb;
int amax = ::amax.query(la,ra),amin = ::amin.query(la,ra),afmx = ::afx.query(la,ra);
int azmn = ::azn.query(la,ra),bmax = ::bmax.query(lb,rb),bmin = ::bmin.query(lb,rb);
int ans = mininf;
gmx(ans, amax * (amax >= 0 ? bmin : bmax));
gmx(ans, amin * (amin >= 0 ? bmin : bmax));
if (afmx != mininf)
gmx(ans, afmx * (afmx >= 0 ? bmin : bmax));
if (azmn != maxinf)
gmx(ans, azmn * (azmn >= 0 ? bmin : bmax));
printf("%lld\n", ans);
}
return 0;
}
原文地址:https://blog.csdn.net/2301_77920554/article/details/136020031
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!