AtCoder Beginner Contest 348
Toyota Programming Contest 2024#4（AtCoder Beginner Contest 348）
年轻人的第一场 abc
2024/04/06 打的，2024/06/20 补了下题解
| Problems | AC |
|---|---|
| A. Penalty Kick | ○ |
| B. Farthest Point | ○ |
| C. Colorful Beans | ○ |
| D. Medicines on Grid | ○ |
| E. Minimize Sum of Distances | ○ |
| F. Oddly Similar | ⊕ |
| G. Max (Sum - Max) | ⊕ |
A
B
C
D
二维网格，起点终点，有障碍物，有一些格子有药，药的作用是将体力值变为 c[i][j]，可以选择用不用
初始起点，体力值为 0，问能否走到终点。
<censored>就一个点 WA 有点搞心态
采用类似 SPFA 的写法
E
F
有 n 个长 m 的序列，问有多少对序列“相似”
假如两个序列相似，说明有奇数个位置相同
n <= 2e3
朴素做法是 O(n^2m)，（吸氧能跑过 at 的机子）
这种 bool 数组想办法搞搞 bitset 优化
$cnt[j][k]$ 是一个大小为 n 的 bitset，假如 a[i][j] = k，则 cnt[j][k][i] = 1
枚举每一行，把每一列的情况 xor 在一起，统计一下 xor 结果中 1 的个数
G
您有两个整数序列 $A$ 和 $B$ ，长度为 $N$ 。对于 $k = 1, 2, \ldots, N$ ，解决以下问题：
- 考虑在 $1$ 和 $N$ 之间选择 $k$ 个不同的整数（含）。让 $S$ 成为所选整数的集合。找出 $\displaystyle (\sum_{i \in S} A_i) - \max_{i \in S} B_i$ 的最大值。
赛后听说是 2023 CCPC 网络赛的原题 QOJ # 7523. Partially Free Meal
首先考虑 $k$ 固定时的答案。将所有盘子按照 $b$ 从小到大排序，枚举第 $x (k \le x \le n)$ 个盘子作为 $\max_{i \in S} B_i$，那么剩下要选的 $k - 1$ 个盘子就是 前 $x - 1$ 个盘子中最大的 $k - 1$ 个。给定 $k$ 和 $x$，可以通过可持久线段树在 $O(log n)$ 的时间内求出对应方案的值 $w(k, x)$。
接下来精彩的一步是证明决策单调性：随着 $k$ 增大，最优情况下的 $B_{max}$ 是非严格单调递增的。
感性理解一下，当你选的数越来越多，你的 $B_{max}$ 会不得不越来越大。因为假如 k’ = k + 1, 那么假如 $B_{max}$ 变小了。意味着你放弃了那个最大的，改选了一个小一点的数。那这样的话他在 k 的时候应该就不是最优的了。
令 $f(k)$ 表示使 $k$ 取到最优解的 $x$。对于两个不同的决策 $x, y (x < y)$，若 $w(k, x) \leq w(k, y)$，那么增大 $k$ 之后由于 $y$ 的可选择范围严格包含了 $x$ 的可选择范围，因此 $y$ 新选的 $a$ 值一定不小于 $x$ 所选的，即 $w(k′, x) \leq w(k′, y)$ 对于 $k \leq k′ \leq n$ 恒成立。由此可得 $f (1) \leq f (2) \leq f (3) \leq \ldots \leq f(n)$，最优决策具有单调性，可以分治求解，共需计算 $O(n log n)$ 个 $w(k, x)$ 的值。
AtCoder Beginner Contest 348