「题解」CSP-S 2022 策略游戏

更新时间：2022.11.04

原题链接

题目描述

小 L 和小 Q 在玩一个策略游戏。
给定一个长度为 $n$ 的数组 $A$ ，一个长度为 $m$ 的数组 $B$ ，在此基础上定义一个大小为 $n \times m$ 的矩阵 $C$ ，满足 $C_{i j} = A_i \times B_i$ ，接下来会进行 $q$ 次游戏，每次游戏给出 $l_1,r_1,l_2,r_2$ 四个参数，满足 $1 \le l_1 \le r_1 \le n$ 、 $1 \le l_2 \le r_2 \le m$ 。
游戏中，小 L 先选择一个 $l_1 \sim r_1$ 之间的下标 $x$ ，然后小 Q 选择一个 $l_2 \sim r_2$ 之间的下标 $y$ 。定义这一轮游戏中二人的得分是 $C_{x y}$ 。
小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。则，每次游戏最终的得分是多少？

50 tps

小 L 控制行号，小 Q 控制列号，由于小 Q 是后手，所以是小 Q 最终决定的这个数，那么小 Q 一定会在小 L 选择的第 $x$ 行中选择一个最小的数。
也就是说，无论小 L 选择的 $x$ 为何值，最终的得分一定是这一行的最小值。
那么我们就可以枚举 $l_1 \sim r_1$ 的每一行，找出这一行的最小值，对所有最小值取 $max$ 即为最终的答案。
如何才能找到每一行的最小值呢？由于存在负数，进行如下分类讨论：

若 $A[x]>0$ ，则 $B$ 取最小值是为最小值
若 $A[x]<0$ ，则 $B$ 取最大值是为最小值
若 $A[x]=0$ ，则最小值为 $0$

区间求最值可以用线段树来实现。
部分代码如下：

// query_max(l,r,1) 为查询 l~r 的区间最大值
// query_min(l,r,1) 为查询 l~r 的区间最小值
int main() {
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    for (int i = 1; i <= m; i++)
        scanf("%d", &b[i]);

    // 建树
    build(1, m, 1);

    while (q--) {
        int l1, r1, l2, r2;
        LL ans = -INF;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

        for (int i = l1; i <= r1; i++)
            if (a[i] > 0)
                ans = max(ans, (LL)a[i] * query_min(l2, r2, 1));
            else if (a[i] < 0)
                ans = max(ans, (LL)a[i] * query_max(l2, r2, 1));
            else if (a[i] == 0)
                ans = max(ans, (LL)0);

        printf("%lld\n", ans);
    }

    return 0;
}

100 tps

接下来考虑100分的做法：
我们可以发现对于 50tps 的做法，列的选择效率已经很高了，但是对于行的遍历，时间复杂度是我们没办法接受的。
那么我们就可以考虑一下如何去掉行的遍历。
假设小 L 已经选择了一个数 $x$ 。

如果 $x\ge0$ $x \geq 0$ ，那么小 Q 一定会选择一个最小的 $y$ $y$ 。
- 若 $y\ge0$ ，为了是最终结果最大，小 L 选择的 $x$ 一定是最大值
- 若 $y<0$ ，为了是最终结果最大，小 L 选择的 $x$ 一定是满足 $x\ge0$ 的最小值
如果 $x<0$ $x < 0$ ，那么小 Q 一定会选择一个最大的 $y$ $y$ 。
- 若 $y\ge0$ ，为了是最终结果最大，小 L 选择的 $x$ 一定是满足 $x<0$ 的最大值
- 若 $y<0$ ，为了是最终结果最大，小 L 选择的 $x$ 一定是最小值

由上述分析可知：
对于 $A$ 数组，我们需要求出 $l_1 \sim r_1$ 范围内的最大值，最小值，负数最大值，非负数最小值。
对于 $B$ 数组，我们需要求出 $l_2 \sim r_2$ 范围内的最大值，最小值。
可用 ST表提前预处理
完整代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 25;
const LL MAX_INF = LONG_LONG_MAX, MIN_INF = LONG_LONG_MIN;
int n, m, q;
// 分别表示  A的最大值  A的最小值  A的非负数最小值  A的负数最大值  B的最大值  B的最小值
LL a_max[N][M], a_min[N][M], pos_min[N][M], neg_max[N][M], b_max[N][M], b_min[N][M];
void ST_prework_a() {
    int t = log(n) / log(2) + 1;

    for (int j = 1; j < t; j++)
        for (int i = 1; i <= n - (1 << j) + 1; i++) {
            a_max[i][j] = max(a_max[i][j - 1], a_max[i + (1 << (j - 1))][j - 1]);
            a_min[i][j] = min(a_min[i][j - 1], a_min[i + (1 << (j - 1))][j - 1]);
            pos_min[i][j] = min(pos_min[i][j - 1], pos_min[i + (1 << (j - 1))][j - 1]);
            neg_max[i][j] = max(neg_max[i][j - 1], neg_max[i + (1 << (j - 1))][j - 1]);
        }
}
void ST_prework_b() {
    int t = log(m) / log(2) + 1;

    for (int j = 1; j < t; j++)
        for (int i = 1; i <= m - (1 << j) + 1; i++) {
            b_max[i][j] = max(b_max[i][j - 1], b_max[i + (1 << (j - 1))][j - 1]);
            b_min[i][j] = min(b_min[i][j - 1], b_min[i + (1 << (j - 1))][j - 1]);
        }
}
LL ST_query_max(LL st[][M], int l, int r) {
    int k = log(r - l + 1) / log(2);
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}
LL ST_query_min(LL st[][M], int l, int r) {
    int k = log(r - l + 1) / log(2);
    return min(st[l][k], st[r - (1 << k) + 1][k]);
}
int main() {
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i++) {
        LL x;
        scanf("%lld", &x);
        a_min[i][0] = a_max[i][0] = x;

        // 若 x 为负数，则将 pos_min[i][0] 设为正无穷
        pos_min[i][0] = (x >= 0 ? x : MAX_INF);

         // 若 x 为正数，则将 neg_max[i][0] 设为负无穷
        neg_max[i][0] = (x < 0 ? x : MIN_INF);
    }

    for (int i = 1; i <= m; i++) {
        LL x;
        scanf("%lld", &x);
        b_min[i][0] = b_max[i][0] = x;
    }

    ST_prework_a();
    ST_prework_b();

    while (q--) {
        int l1, r1, l2, r2;
        LL ans = MIN_INF;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        LL res_a_max = ST_query_max(a_max, l1, r1);        // A的最大值
        LL res_a_min = ST_query_min(a_min, l1, r1);        // A的最小值
        LL res_neg_max = ST_query_max(neg_max, l1, r1);    // A的负数最大值
        LL res_pos_min = ST_query_min(pos_min, l1, r1);    // A的非负数最小值
        LL res_b_max = ST_query_max(b_max, l2, r2);        // B的最大值
        LL res_b_min = ST_query_min(b_min, l2, r2);        // B的最小值

        if (res_a_min >= 0)
            ans = max(ans, res_a_min * res_b_min);
        else
            ans = max(ans, res_a_min * res_b_max);

        if (res_a_max >= 0)
            ans = max(ans, res_a_max * res_b_min);
        else
            ans = max(ans, res_a_max * res_b_max);

        if (res_neg_max != MIN_INF)
            ans = max(ans, res_neg_max * (res_neg_max >= 0 ? res_b_min : res_b_max));

        if (res_pos_min != MAX_INF)
            ans = max(ans, res_pos_min * (res_pos_min >= 0 ? res_b_min : res_b_max));

        printf("%lld\n", ans);
    }

    return 0;
}

「题解」CSP-S 2022 策略游戏

原题链接

题目描述

50 tps

100 tps

完结撒花