主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：P8818 [CSP-S 2022] 策略游戏
最后更新于 2025-08-28 09:06:25
作者
2huk
分类
题解
题解
P8818
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
## 题意 小 L 和小 Q 绝顶聪明。 给定长度为 $n$ 的 $a$ 和长度为 $m$ 的 $b$。$q$ 次询问，给定 $l_1,r_1,l_2,r_2$。小 L 要选择一个 $x \in [l_1, r_1]$，小 Q 要选择一个 $y \in [l_2,r_2]$。小 L 希望最大化 $a_x \times b_y$，小 Q 希望最小化 $a_x \times b_y$。求最后的 $a_x \times b_y$。 ## 做法 小 L 希望最大化。若令 $f(x)$ 表示当小 L 选择 $x$ 时，小 Q 最小能将得分变成多少。即 $f(x) = \min_y a_x \times b_y$。那么答案为 $\max f(x)$。 有负数很恶心。分类讨论一下，发现如果两人都绝顶聪明的话，它们所选择的数一定数区间： - 最大值 - 最小值 - 最大负数（如果存在） - 最小负数（如果存在） 所以一次询问可以将复杂度从 $n^2$ 优化至 $4^2$。 维护这四个值是基础 ST 表。
正在渲染内容...
点赞
0
收藏
0
