历年CSP-S复赛真题解析 | 2022年CSP-S复赛

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总贴：历年CSP-S复赛真题解析 | 汇总

---

P8818 策略游戏

【题目来源】

洛谷：[P8818 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 在最优策略下的得分。

【输入样例】

3 2 2
0 1 -2
-3 4
1 3 1 2
2 3 2 2

【输出样例】

0
4

【算法标签】

《洛谷 P8818 策略游戏》 #贪心# #线段树# #ST表# #CSP-S提高级# #2022# #O2优化#

【代码详解】

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

// 定义int为long long类型
#define int long long
// 定义常量
const int N = 100005;

// 变量定义
int n, m, q;  // n: 第一个序列长度, m: 第二个序列长度, q: 查询次数

// ST表数组
int azmax[N][32];  // 存储序列a中非负数的最大值
int azmin[N][32];  // 存储序列a中非负数的最小值
int afmax[N][32];  // 存储序列a中负数的最大值
int afmin[N][32];  // 存储序列a中负数的最小值
int bmax[N][32];   // 存储序列b的最大值
int bmin[N][32];   // 存储序列b的最小值

signed main()
{
    // 读入n, m, q
    cin >> n >> m >> q;
    
    // 读入序列a并初始化ST表
    for (int i = 1; i <= n; i++)
    {
        cin >> azmax[i][0];  // 读入序列a的第i个元素
        
        if (azmax[i][0] < 0)  // 如果是负数
        {
            // 负数存储在afmax和afmin中
            afmax[i][0] = afmin[i][0] = azmax[i][0];
            // 非负数表设为无效值
            azmax[i][0] = -1;       // 非负最大值设为-1
            azmin[i][0] = INT_MAX;  // 非负最小值设为极大值
        }
        else  // 如果是非负数
        {
            // 非负数存储在azmax和azmin中
            azmin[i][0] = azmax[i][0];
            // 负数表设为无效值
            afmax[i][0] = -INT_MAX;  // 负最大值设为负无穷
            afmin[i][0] = 0;         // 负最小值设为0
        }
    }
    
    // 读入序列b并初始化ST表
    for (int i = 1; i <= m; i++)
    {
        cin >> bmax[i][0];  // 读入序列b的第i个元素
        bmin[i][0] = bmax[i][0];  // 同时赋值给最小值
    }
    
    // 计算log2值
    int lena = log2(n);  // 序列a的ST表最大层数
    int lenb = log2(m);  // 序列b的ST表最大层数
    
    // 构建序列a的非负数最大值ST表
    for (int j = 1; j <= lena; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            azmax[i][j] = max(azmax[i][j - 1], azmax[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    // 构建序列a的非负数最小值ST表
    for (int j = 1; j <= lena; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            azmin[i][j] = min(azmin[i][j - 1], azmin[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    // 构建序列a的负数最大值ST表
    for (int j = 1; j <= lena; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            afmax[i][j] = max(afmax[i][j - 1], afmax[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    // 构建序列a的负数最小值ST表
    for (int j = 1; j <= lena; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            afmin[i][j] = min(afmin[i][j - 1], afmin[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    // 构建序列b的最大值ST表
    for (int j = 1; j <= lenb; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= m; i++)
        {
            bmax[i][j] = max(bmax[i][j - 1], bmax[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    // 构建序列b的最小值ST表
    for (int j = 1; j <= lenb; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= m; i++)
        {
            bmin[i][j] = min(bmin[i][j - 1], bmin[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    // 查询变量
    int x1, y1, x2, y2;  // 查询区间：a的[x1,y1]，b的[x2,y2]
    int maxy, miny;      // 序列b在查询区间的最大值和最小值
    int maxzx, maxfx, minzx, minfx;  // 序列a在查询区间的四种极值
    
    // 处理每个查询
    while (q--)
    {
        int ans = -1e18;  // 初始化答案为负无穷
        
        // 读入查询区间
        cin >> x1 >> y1 >> x2 >> y2;
        
        // 查询序列b在[x2,y2]区间的最大值和最小值
        int k2 = log2(y2 - x2 + 1);
        maxy = max(bmax[x2][k2], bmax[y2 - (1 << k2) + 1][k2]);
        miny = min(bmin[x2][k2], bmin[y2 - (1 << k2) + 1][k2]);
        
        // 查询序列a在[x1,y1]区间的四种极值
        int k1 = log2(y1 - x1 + 1);
        maxzx = max(azmax[x1][k1], azmax[y1 - (1 << k1) + 1][k1]);  // 非负数最大值
        minzx = min(azmin[x1][k1], azmin[y1 - (1 << k1) + 1][k1]);  // 非负数最小值
        maxfx = max(afmax[x1][k1], afmax[y1 - (1 << k1) + 1][k1]);  // 负数最大值
        minfx = min(afmin[x1][k1], afmin[y1 - (1 << k1) + 1][k1]);  // 负数最小值
        
        // 根据序列a和b的极值计算最大乘积
        if (minzx != INT_MAX)  // 如果存在非负数
        {
            ans = max(ans, maxzx * miny);  // 最大非负数 × 最小b
            ans = max(ans, minzx * miny);  // 最小非负数 × 最小b
        }
        if (maxfx != -INT_MAX)  // 如果存在负数
        {
            ans = max(ans, maxfx * maxy);  // 最大负数 × 最大b
            ans = max(ans, minfx * maxy);  // 最小负数 × 最大b
        }
        
        // 输出结果
        cout << ans << endl;
    }
    
    return 0;
}

【运行结果】

3 2 2
0 1 -2
-3 4
1 3 1 2
0
2 3 2 2
4