网硕互联帮助中心欢迎大家订阅我的专栏：算法题解：C++与Python实现！ 本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色 1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。 2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：历年CSP-S复赛真题解析 | 汇总
P8818 策略游戏
【题目来源】
洛谷：[P8818 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 在最优策略下的得分。
【输入样例】
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
评论前必须登录！
注册