2022 策略游戏 · 方案一暴力扫描

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 1482 字

每次询问暴力扫描两序列的区间极值

2022
ST表

正文

// CSP-S 2022 复赛 T2 · 策略游戏（方案一：每次询问暴力扫描，部分分）
// 原题：https://oj.yecheng.tv/p/CSPS2022B
// 题意：A、B 两序列。L0 选 A 的子段 [l1,r1] 中的一个数 a，L1 选 B 的
//       子段 [l2,r2] 中的一个数 b（L0 让 a·b 小、L1 让 a·b 大）。
//       L0 先选、L1 后选（知道 a）。Q 次询问每次给两组子段，求
//       博弈结果 a·b。数组值可为负与 0。
// 思路（暴力）：
//   每次询问：枚举 a ∈ A 段、对每个 a 枚举 b ∈ B 段取 max，再取 min。
//   O(q · len1 · len2)，q ≤ 200 / 长度小时可过（测试点 1~5）。
// 复杂度：O(q · n · m)。
// 易错点：
//   1. 负数乘法：L0 想小可能选正数也可能选负数，不能只看一侧；
//   2. L1 是在"看到 a 之后"选 max —— 内层对每个 a 取 max(b·a)；
//   3. 结果可能超 int（1e9·1e9），用 long long。
#include <cstdio>

int n, m, q;
long long A[100005], B[100005];

int main() {
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++) scanf("%lld", &A[i]);
    for (int i = 1; i <= m; i++) scanf("%lld", &B[i]);
    while (q--) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        long long best = 0;
        bool first = true;
        for (int i = l1; i <= r1; i++) {
            long long worst = 0;
            bool f2 = true;
            for (int j = l2; j <= r2; j++) {
                long long cur = A[i] * B[j];
                if (f2 || cur > worst) {
                    worst = cur;
                    f2 = false;
                }
            }
            if (first || worst < best) {
                best = worst;
                first = false;
            }
        }
        printf("%lld\n", best);
    }
    return 0;
}

2022 策略游戏 · 方案一 暴力扫描

正文

CSP-S 标程 · 复赛真题的其它内容

2022 策略游戏 · 方案一暴力扫描