AcWing 4733. 策略游戏

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 4733. 策略游戏原题链接困难

作者：

清风qwq , 2022-10-30 13:22:07 , 所有人可见 , 阅读 749

RMQ,线段树,Splay

[CSP-S 2022] 策略游戏（民间数据）

题目描述

小 L 和小 Q 在玩一个策略游戏。

有一个长度为 $n$ 的数组 $A$ 和一个长度为 $m$ 的数组 $B$ ，在此基础上定义一个大小为 $n \times m$ 的矩阵 $C$ ，满足 $C_{i j} = A_i \times B_j$ 。所有下标均从 $1$ 开始。

游戏一共会进行 $q$ 轮，在每一轮游戏中，会事先给出 $4$ 个参数 $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 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。

请问：按照二人的最优策略，每轮游戏的得分分别是多少？

输入格式

第一行输入三个正整数 $n, m, q$ ，分别表示数组 $A$ ，数组 $B$ 的长度和游戏轮数。

第二行： $n$ 个整数，表示 $A_i$ ，分别表示数组 $A$ 的元素。

第三行： $m$ 个整数，表示 $B_i$ ，分别表示数组 $B$ 的元素。

接下来 $q$ 行，每行四个正整数，表示这一次游戏的 $l_1, r_1, l_2, r_2$ 。

输出格式

输出共 $q$ 行，每行一个整数，分别表示每一轮游戏中，小 L 和小 Q 在最优策略下的得分。

样例 #1

样例输入 #1

样例输出 #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

提示

【样例解释 #1】

这组数据中，矩阵 $C$ 如下：

$\begin{bmatrix} 0 & 0 \\ -3 & 4 \\ 6 & -8 \end{bmatrix}$

在第一轮游戏中，无论小 L 选取的是 $x = 2$ 还是 $x = 3$ ，小 Q 都有办法选择某个 $y$ 使得最终的得分为负数。因此小 L 选择 $x = 1$ 是最优的，因为这样得分一定为 $0$ 。

而在第二轮游戏中，由于小 L 可以选 $x = 2$ ，小 Q 只能选 $y = 2$ ，如此得分为 $4$ 。

【样例 #3】

见附件中的 game/game3.in 与 game/game3.ans。

【样例 #4】

见附件中的 game/game4.in 与 game/game4.ans。

【数据范围】

对于所有数据， $1 \le n, m, q \le {10}^5$ ， $-{10}^9 \le A_i, B_i \le {10}^9$ 。对于每轮游戏而言， $1 \le l_1 \le r_1 \le n$ ， $1 \le l_2 \le r_2 \le m$ 。

测试点编号	$n, m, q \le$	特殊条件
$1$	$200$	1, 2
$2$	$200$	1
$3$	$200$	2
$4 \sim 5$	$200$	无
$6$	$1000$	1, 2
$7 \sim 8$	$1000$	1
$9 \sim 10$	$1000$	2
$11 \sim 12$	$1000$	无
$13$	$10^5$	1, 2
$14 \sim 15$	$10^5$	1
$16 \sim 17$	$10^5$	2
$18 \sim 20$	$10^5$	无

其中，特殊性质 1 为：保证 $A_i, B_i > 0$ 。
特殊性质 2 为：保证对于每轮游戏而言，要么 $l_1 = r_1$ ，要么 $l_2 = r_2$ 。

分析

对于一组给定的l1,r1,l2,r2

$ans = Max_{i=l1}^{i\leq r1} {Min_{j=l2}^{j\leq r2}C_{ij}}$
$j$ 只能选 $b$ 数组中 $[l2,r2]$ 区间的最大值或最小值
若i固定,j也固定

由于有可能都为正数或负数,分为9种情况

不同情况对应最优策略不同

$_a$ \ $^b$	$-2$	$-1$	$0$	$1$	$2$
$-2$	$4$	$2$	$0$	$-2$	$-4$
$-1$	$2$	$1$	$0$	$-1$	$-2$
$0$	$0$	$0$	$0$	$0$	$0$
$1$	$-2$	$-1$	$0$	$1$	$2$
$2$	$-4$	$-2$	$0$	$2$	$4$

本题还考查区间最值,RMQ,线段树等都可以

此处使用RMQ

$考场代码$

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 25;
int a[N], b[N];
int f1[N][M], f2[N][M];//f1表示正数中最小的，f2表示负数中最大的(a数组)
int g1[N][M], g2[N][M];//g1表示最小值,g2表示最大值(b数组)
int g3[N][M], g4[N][M];//g3表示最大值,g4表示最小值(a数组)

int Maxg2(int l, int r)
{
    int len = log2(r - l + 1);
    return max(g2[l + (1 << len) - 1][len], g2[r][len]);
}

int Maxg3(int l, int r)
{
    int len = log2(r - l + 1);
    return max(g3[l + (1 << len) - 1][len], g3[r][len]);
}

int Minf1(int l, int r)
{
    int len = log2(r - l + 1);
    return min(f1[l + (1 << len) - 1][len], f1[r][len]);
}

int Minf2(int l, int r)
{
    int len = log2(r - l + 1);
    return min(f2[l + (1 << len) - 1][len], f2[r][len]);
}

int Ming1(int l, int r)
{
    int len = log2(r - l + 1);
    return min(g1[l + (1 << len) - 1][len], g1[r][len]);
}

int Ming4(int l, int r)
{
    int len = log2(r - l + 1);
    return min(g4[l + (1 << len) - 1][len], g4[r][len]);
}

int main()
{
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);

    int n, m, q;
    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]);

    memset(f1, 0x3f, sizeof f1);
    memset(f2, 0x3f, sizeof f2);
    for (int i = 1; i <= n; i ++ )
    {
        if (a[i] >= 0)f1[i][0] = a[i];
        if (a[i] < 0)f2[i][0] = -a[i];
        for (int j = 1; j <= 20; j ++ )
            if (i - (1 << j) + 1 >= 0)
            {
                f1[i][j] = min(f1[i][j - 1], f1[i - (1 << j - 1)][j - 1]);
                f2[i][j] = min(f2[i][j - 1], f2[i - (1 << j - 1)][j - 1]);              
            }
    }

    memset(g1, 0x3f, sizeof g1);
    memset(g2, -0x3f, sizeof g2);
    memset(g3, -0x3f, sizeof g3);
    memset(g4, 0x3f, sizeof g4);
    for (int i = 1; i <= m; i ++ )
    {
        g1[i][0] = g2[i][0] = b[i];
        for (int j = 1; j <= 20; j ++ )
            if (i - (1 << j) + 1 >= 0)
            {
                g1[i][j] = min(g1[i][j - 1], g1[i - (1 << j - 1)][j - 1]);
                g2[i][j] = max(g2[i][j - 1], g2[i - (1 << j - 1)][j - 1]);              
            }
    }
    for (int i = 1; i <= n; i ++ )
    {
        g3[i][0] = g4[i][0] = a[i];
        for (int j = 1; j <= 20; j ++ )
            if (i - (1 << j) + 1 >= 0)
            {
                g3[i][j] = max(g3[i][j - 1], g3[i - (1 << j - 1)][j - 1]);
                g4[i][j] = min(g4[i][j - 1], g4[i - (1 << j - 1)][j - 1]);              
            }
    }

    while (q -- )
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        long long t1 = Minf1(l1, r1), t2 = Minf2(l1, r1);
        long long t3 = Ming1(l2, r2), t4 = Maxg2(l2, r2);
        long long t5 = Maxg3(l1, r1), t6 = Ming4(l1, r1);
        int flag1 = 0, flag2 = 0;
        if (t3 >= 0)flag2 = 1;
        if (t4 < 0)flag2 = 2;
        if (t6 >= 0)flag1 = 1;
        if (t5 < 0)flag1 = 2;
        //flag为0表示存在负数和正数,为1表示只存在正数,为2表示只存在负数
        if (flag1 == 0 && flag2 == 0)printf("%lld\n", max(t1 * t3, t2 * t4 * (-1)));
        if (flag1 == 0 && flag2 == 1)printf("%lld\n", t5 * t3);
        if (flag1 == 0 && flag2 == 2)printf("%lld\n", t6 * t4);
        if (flag1 == 1 && flag2 == 0)printf("%lld\n", t6 * t3);
        if (flag1 == 1 && flag2 == 1)printf("%lld\n", t5 * t3);
        if (flag1 == 1 && flag2 == 2)printf("%lld\n", t6 * t3);
        if (flag1 == 2 && flag2 == 0)printf("%lld\n", t5 * t4);
        if (flag1 == 2 && flag2 == 1)printf("%lld\n", t5 * t4);
        if (flag1 == 2 && flag2 == 2)printf("%lld\n", t6 * t4);
    }

    return 0;
}