AtCoder Beginner Contest 464 题解

项目	内容
比赛时间	2026-06-27
比赛链接	https://atcoder.jp/contests/abc464
题目数量	A–G 共 7 题

比赛概览

本场整体难度属于 ABC 的中等偏上水平。A、B 两题为纯签到，主要考察基本的字符串与二维网格处理；C 题把"颜色变化"拆解成"加一/减一"事件，是一种很有代表性的差分思想；D 题是经典的"只记前一天天气"的线性 DP；E 题需要把"覆盖操作"转化为二维后缀最大值，思路巧妙；F 题是期望与 meet-in-the-middle 的结合，是本场最有区分度的题目之一；G 题则是把天气操作转化为差分序列上的"配对"问题，最终归约到 JOISC 2018 的经典贪心（"飴"），转化链很长，很考验思维。建议重点掌握 C 的事件拆分、D 的 O(1) 状态 DP、E 的后缀 max 技巧，以及 F 的 meet-in-the-middle 期望计数。

---

A - Decisive Battle

题目链接：https://atcoder.jp/contests/abc464/tasks/abc464_a

题目大意

给定一个只由字符 E 和 W 组成的字符串 $S$，其中 E 的个数代表东军士兵数，W 的个数代表西军士兵数。保证 $S$ 的长度为奇数（因此两军人数必然不相等）。若东军人多输出 East，否则输出 West。

思路

这是非常直接的统计题。由于 $|S|$ 是奇数，E 与 W 的个数不可能相等，所以只需比较谁更多即可。

官方题解给出了一种只用单个变量的写法：用一个计数器 $h$ 从 $0$ 开始，遇到 E 就 $+1$，遇到 W 就 $-1$。扫描完整个字符串后：

• 若 $h > 0$，说明 E 比 W 多，输出 East；
• 否则 $h < 0$，说明 W 比 E 多，输出 West。

之所以可以这样写，是因为我们并不关心两军具体的人数，只关心差值的符号。这个技巧避免了分别统计两种字符个数再比较的代码量，虽然对本题来说两种写法差别不大。

需要注意的边界情况：$S$ 的长度最小为 $1$，此时 $S$ 只含一个字符，直接判断即可，上述代码自然覆盖。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;

    int h = 0;                       // E 的个数减去 W 的个数
    for (char c : S) {
        if (c == 'E') h++;
        else h--;
    }
    cout << (h > 0 ? "East" : "West") << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(|S|)$，只需线性扫描一遍字符串。
• 空间复杂度：$O(1)$，仅使用常数个变量。

---

B - Crop

题目链接：https://atcoder.jp/contests/abc464/tasks/abc464_b

题目大意

给定一个 $H \times W$ 的黑白图像，. 表示白色，# 表示黑色。依次执行以下操作直到不能再执行：

1. 若最上面一行全为白，删除该行（重复）；
2. 若最下面一行全为白，删除该行（重复）；
3. 若最左一列全为白，删除该列（重复）；
4. 若最右一列全为白，删除该列（重复）。

输出处理后的图像。保证原图中至少有一个黑色像素。

思路

关键观察：题述的裁剪过程，结果恰好就是"包含所有黑色像素的最小矩形"。理由如下：

• 一个白行能否被删除，只取决于它是否位于所有黑格的行跨度之外。顶端全白的行，其行号必然严格小于所有黑格的最小行号；删除它之后，下一个顶端行号依然小于所有黑格的行号，所以"删除顶端白行"这一过程会一直持续到顶端恰好变成黑格所在的最小行。
• 同理，底端、左端、右端的删除分别对应黑格所在的最大行号、最小列号、最大列号。

于是我们不需要真正模拟删除过程，只需一次性扫描全图，找出所有黑格的行、列四个极值：

• 最小行号 $u = \min_{(i,j)\in B} i$，最大行号 $d = \max_{(i,j)\in B} i$；
• 最小列号 $l = \min_{(i,j)\in B} j$，最大列号 $r = \max_{(i,j)\in B} j$。

然后输出第 $u$ 行到第 $d$ 行、第 $l$ 列到第 $r$ 列的子矩形即可。

正确性：裁剪过程与"直接取包围矩形"等价，因为在任意时刻，最外层待删除的行/列都对应着极值尚未被"顶到"的一侧；四类操作互不干扰，最终停在四个极值处。

边界情况：题目保证至少有一个黑格，因此 $u \le d$、$l \le r$ 总是成立，不会出现输出空图的情况。

官方题解还给出另一种写法：把"删上边"这一操作泛化为——每轮旋转 $90^\circ$ 后删除顶端全白行，重复 4 次即可。这种做法不需要记录极值，直接模拟，但需要实现一个旋转函数。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W;
    cin >> H >> W;
    vector<string> C(H);
    for (int i = 0; i < H; i++) cin >> C[i];

    // 求所有黑格的最小包围矩形
    int u = H, d = -1, l = W, r = -1;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (C[i][j] == '#') {
                u = min(u, i);
                d = max(d, i);
                l = min(l, j);
                r = max(r, j);
            }
        }
    }

    for (int i = u; i <= d; i++) {
        cout << C[i].substr(l, r - l + 1) << '\n';
    }
    return 0;
}

官方题解还提供了基于"旋转删除"的简洁 Python 写法（本题官方题解思路二）：

def rotate(a):
    return ["".join(row) for row in zip(*a[::-1])]

H, W = map(int, input().split())
C = [input() for _ in range(H)]

for _ in range(4):
    while "#" not in C[0]:
        C = C[1:]
    C = rotate(C)

print(*C, sep="\n")

复杂度分析

• 时间复杂度：$O(HW)$，只需一次全图扫描。
• 空间复杂度：$O(HW)$，需要存下整幅图像（若不存图而边读边算，可做到 $O(1)$ 额外空间，但实现上直接用原图更简单）。

---

C - Plumage Palette

题目链接：https://atcoder.jp/contests/abc464/tasks/abc464_c

题目大意

Takahashi 观察了 $N$ 只鸟，编号 $1\sim N$，共 $M$ 天。第 $i$ 只鸟在第 $D_i-1$ 天及之前颜色为 $A_i$，在第 $D_i$ 天及之后颜色为 $B_i$（若 $D_i=1$ 则第一天起就是 $B_i$；若 $A_i=B_i$ 则颜色不变）。对每一天 $j$，输出当天出现的不同颜色的种数。

思路

如果对每一天都重新统计一次全部 $N$ 只鸟的颜色，复杂度为 $O(NM)$，不可行。关键在于把每只鸟的颜色信息拆成若干个可以增量维护的事件。

问题转化：第 $i$ 只鸟的信息等价于三个事件：

1. 初始时刻，颜色为 $A_i$ 的鸟增加 $1$ 只；
2. 在第 $D_i$ 天，颜色为 $A_i$ 的鸟减少 $1$ 只；
3. 在第 $D_i$ 天，颜色为 $B_i$ 的鸟增加 $1$ 只。

于是只需维护两个量：

• $cnt[c]$：当前颜色为 $c$ 的鸟的只数；
• $kind$：当前满足 $cnt[c] > 0$ 的颜色个数。

增量维护规则：

• 颜色 $c$ 的鸟数 $+1$：若 $cnt[c]$ 原来为 $0$，则 $kind$ 加 $1$；然后 $cnt[c] \gets cnt[c]+1$。
• 颜色 $c$ 的鸟数 $-1$：先 $cnt[c] \gets cnt[c]-1$；若 $cnt[c]$ 变为 $0$，则 $kind$ 减 $1$。

这两个操作互为逆操作（先加后减、先减后加都恢复到原状态），这正可以用于检查算法的正确性。

算法流程：

1. 读入每只鸟的信息，先把初始的"颜色 $A_i$ 加一只"处理掉（即初始化 $cnt$ 与 $kind$），并把 $(A_i, B_i)$ 这个"在第 $D_i$ 天切换颜色"的事件放进按天分桶的数组 $change[D_i]$ 中。
2. 依次处理第 $j=1,\dots,M$ 天：先应用 $change[j]$ 里的全部事件（先减 $A_i$、后加 $B_i$），此时 $kind$ 就是第 $j$ 天不同颜色的种数，输出即可。

注意读入顺序是 $A_i \quad D_i \quad B_i$，不要读错。

正确性：每个事件都在恰好的时间点发生，$cnt$ 与 $kind$ 的增量维护保证其始终准确反映"当天每只鸟的颜色"，因此每步输出的 $kind$ 就是当天答案。

边界情况：当 $A_i = B_i$ 时，第 $D_i$ 天的两个事件相互抵消（$cnt$ 先减后加，$kind$ 先减后加），$kind$ 不变，符合题意。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<int> cnt(N + 1, 0);            // cnt[c]: 当前颜色为 c 的鸟的只数
    int kind = 0;                          // 当前出现的不同颜色种数
    vector<vector<pair<int, int>>> change(M + 1);

    for (int i = 0; i < N; i++) {
        int a, d, b;
        cin >> a >> d >> b;                // 注意输入顺序是 A D B
        // 初始：颜色 a 增加一只
        if (cnt[a] == 0) kind++;
        cnt[a]++;
        // 第 d 天发生：a -> b 的切换
        change[d].push_back({a, b});
    }

    for (int day = 1; day <= M; day++) {
        for (auto [a, b] : change[day]) {
            // 一只鸟从颜色 a 变为颜色 b
            cnt[a]--;
            if (cnt[a] == 0) kind--;
            if (cnt[b] == 0) kind++;
            cnt[b]++;
        }
        cout << kind << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(N + M)$，每只鸟贡献固定数量的事件，每天输出一次。
• 空间复杂度：$O(N + M)$，需要 $cnt$ 数组和按天分桶的事件数组。

---

D - Celester

题目链接：https://atcoder.jp/contests/abc464/tasks/abc464_d

题目大意

给定长度为 $N$ 的天气串 $S$，第 $i$ 个字符为 S（晴）或 R（雨）。初始快乐值为 $0$。可以进行任意次操作：选择一天 $i$，把它的天气翻转（晴变雨、雨变晴），代价是快乐值减少 $X_i$。操作结束后，对每个 $i=1,\dots,N-1$，若第 $i$ 天为雨且第 $i+1$ 天为晴，则快乐值增加 $Y_i$。求快乐值的最大值。共有 $T$ 组测试数据。

思路

关键观察：最终快乐值只与"相邻两天的最终天气"有关，而某一天的决策只会影响它自身以及它与前后两天的关系。因此当我们从左到右依次决定每一天的天气时，为了计算后续的收益，只需记住前一天的天气，更早的信息都可以丢弃。这启发我们使用状态为"前一天天气"的 DP。

DP 定义：

• $dp[0]$：已经决定完前 $i$ 天、且第 $i$ 天的最终天气为晴时，能获得的最大快乐值（含所有已发生的代价与收益）；
• $dp[1]$：同样条件，但第 $i$ 天的最终天气为雨。

初始化（第 $1$ 天）：

• 若 $S_1 = $ R（原为雨）：第 1 天定晴需要花费 $X_1$，所以 $dp[0] = -X_1$，$dp[1] = 0$。
• 若 $S_1 = $ S（原为晴）：第 1 天定雨需要花费 $X_1$，所以 $dp[0] = 0$，$dp[1] = -X_1$。

转移（第 $i$ 天，$i \ge 2$）：

设第 $i$ 天的天气定为晴时的新状态为 $ndp[0]$，定为雨时为 $ndp[1]$。

• 第 $i$ 天定为晴：若前一天是雨（对应 $dp[1]$），则得到 $Y_{i-1}$；若前一天是晴则没有额外收益。故

  $$ndp[0] = \max(dp[0],\; dp[1] + Y_{i-1}).$$

• 第 $i$ 天定为雨：无论前一天天气如何都没有额外收益。故

  $$ndp[1] = \max(dp[0],\; dp[1]).$$

• 再补上翻转第 $i$ 天的代价：
  • 若 $S_i = $ R，则定为晴要多花 $X_i$，于是 $ndp[0] \gets ndp[0] - X_i$；
  • 若 $S_i = $ S，则定为雨要多花 $X_i$，于是 $ndp[1] \gets ndp[1] - X_i$。

最后答案即为 $\max(dp[0], dp[1])$（第 $N$ 天定晴或定雨两种情况取优）。

为什么正确：每一步转移只用到 $dp[0], dp[1]$ 和 $Y_{i-1}$，这正是"收益只取决于相邻两天的天气"所决定的；把同状态的多种方案合并成最优值不会丢失信息，因为未来的收益对过去的依赖仅通过"第 $i$ 天天气"这一信息传递。

易错点：

• 答案可能超过 $32$ 位整数（如样例 5 达到 $5.2\times 10^9$），必须使用 64 位整数。
• 不执行任何操作也是合法方案，因此最终答案恒 $\ge 0$（DP 天然能取到不翻转任何天的方案）。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        string S;
        cin >> S;
        vector<ll> X(N), Y(N - 1);
        for (int i = 0; i < N; i++) cin >> X[i];
        for (int i = 0; i < N - 1; i++) cin >> Y[i];

        // dp0: 前一天的最终天气为晴时的最优值
        // dp1: 前一天的最终天气为雨时的最优值
        ll dp0 = 0, dp1 = 0;
        if (S[0] == 'R') dp0 = -X[0];     // 第 1 天定为晴需要付出 X_1
        else             dp1 = -X[0];     // 第 1 天定为雨需要付出 X_1

        for (int i = 1; i < N; i++) {
            ll ndp0 = max(dp0, dp1 + Y[i - 1]);  // 第 i 天定晴，前一天是雨则得 Y_{i-1}
            ll ndp1 = max(dp0, dp1);             // 第 i 天定雨，无额外收益
            if (S[i] == 'R') ndp0 -= X[i];
            else             ndp1 -= X[i];
            dp0 = ndp0;
            dp1 = ndp1;
        }
        cout << max(dp0, dp1) << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(N)$（单组数据），每组数据只线性扫描一遍。
• 空间复杂度：$O(N)$（存储 $X$、$Y$）；若改为边读边转移可做到 $O(1)$ 额外空间，这里为清晰起见直接存储。

---

E - Fill-Rect Query

题目链接：https://atcoder.jp/contests/abc464/tasks/abc464_e

题目大意

有一个 $H \times W$ 的网格，初始每个格子写着 A。按顺序执行 $Q$ 个操作，第 $i$ 个操作为：把左上角 $(1,1)$、右下角 $(R_i, C_i)$ 的矩形内所有格子都覆盖写成字母 $X_i$。输出所有操作结束后每个格子上的字母。

思路

关键转化：把第 $i$ 个操作使用的字母 $X_i$ 替换成操作编号 $i$，最后再统一映射回字母。这样一来，格子 $(r,c)$ 上的最终值就是"所有覆盖到 $(r,c)$ 的操作中编号最大者"。

某个操作 $i$（覆盖 $[1,R_i] \times [1,C_i]$）覆盖到 $(r,c)$ 当且仅当

$$r \le R_i \quad \text{且} \quad c \le C_i.$$

所以对于每个格子 $(r,c)$，问题变成：求满足上述条件的所有操作编号的最大值，也就是求"以 $(r,c)$ 为左上角、以 $(H,W)$ 为右下角的矩形区域"内所有写在格子上的标记的最大值。

算法：把每个操作写在它覆盖矩形的右下角 $(R_i, C_i)$ 处，即 $a[R_i][C_i] = i$（多个操作写同一格时，编号大的最后写，直接赋值即可）。然后从右下角往左上角做一遍"二维后缀最大值"：

$$a[r][c] = \max\big(a[r][c],\; a[r+1][c],\; a[r][c+1]\big).$$

这正是一维前缀和思想的二维版本，只是方向相反。实现时从 $r = H-1$ 递减到 $0$、$c = W-1$ 递减到 $0$，处理到格子 $(r,c)$ 时它的下、右邻居已经存好了各自区域的"右下后缀最大值"，于是：

$$a[r][c] = \max\big(a[r][c],\; a[r+1][c],\; a[r][c+1]\big),$$

把它再向上、向左传播：$a[r-1][c] = \max(a[r-1][c], a[r][c])$，$a[r][c-1] = \max(a[r][c-1], a[r][c])$。

最终每个格子 $a[r][c]$ 存的就是覆盖它的最大操作编号 $i$，映射回字母 $X_i$ 输出即可。

正确性：按该扫描顺序，任意格子 $(r,c)$ 的右下方向区域都能被（由它下方与右方两格递推得到的）最大值覆盖，归纳可得 $a[r][c]$ 恰为满足 $r' \ge r,\ c' \ge c$ 的所有写有标记格子中的最大值。

边界情况：

• 当 $r = 0$ 或 $c = 0$ 时，不需要再向上/向左传播（会越界）。
• $H \times W \le 10^6$，可以用一维数组压平存储；$a$ 的初值为 $0$，对应字母 A。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W, Q;
    cin >> H >> W >> Q;

    vector<int> a(H * W, 0);       // 记录"覆盖该格的最大操作编号"，0 表示没被覆盖过
    vector<char> xs(Q + 1);
    xs[0] = 'A';                    // 初始字母

    auto id = [&](int r, int c) { return r * W + c; };

    for (int i = 1; i <= Q; i++) {
        int R, C;
        char X;
        cin >> R >> C >> X;
        xs[i] = X;
        a[id(R - 1, C - 1)] = i;    // 只把操作"标记"在矩形的右下角
    }

    // 从右下往左上做二维后缀最大值
    for (int r = H - 1; r >= 0; r--) {
        for (int c = W - 1; c >= 0; c--) {
            int v = a[id(r, c)];
            if (r > 0) a[id(r - 1, c)] = max(a[id(r - 1, c)], v);
            if (c > 0) a[id(r, c - 1)] = max(a[id(r, c - 1)], v);
        }
    }

    for (int r = 0; r < H; r++) {
        string line;
        line.reserve(W);
        for (int c = 0; c < W; c++) line.push_back(xs[a[id(r, c)]]);
        cout << line << '\n';
    }
    return 0;
}

本题官方题解提供的 Python（PyPy）实现如下：

h, w, q = map(int, input().split())

a = [[0] * w for _ in range(h)]
xs = ["A"]
for i in range(1, q + 1):
    r, c, x = input().split()
    xs.append(x)
    a[int(r) - 1][int(c) - 1] = i

for r in range(h - 1, -1, -1):
    for c in range(w - 1, -1, -1):
        if r != 0:
            a[r - 1][c] = max(a[r][c], a[r - 1][c])
        if c != 0:
            a[r][c - 1] = max(a[r][c], a[r][c - 1])

for r in range(h):
    print("".join(xs[a[r][c]] for c in range(w)))

复杂度分析

• 时间复杂度：$O(HW + Q)$，后缀最大值的扫描只需遍历全部 $HW$ 个格子。
• 空间复杂度：$O(HW)$，用于存储网格与字母映射。

---

F - Random Vault Heist

题目链接：https://atcoder.jp/contests/abc464/tasks/abc464_f

题目大意

银行有 $N$ 个保险箱，第 $i$ 个保险箱里有 $A_i$ 日元。强盗不断从尚未打开的保险箱中均匀随机地选一个打开并拿走里面的钱，直到累计金额达到至少 $X$ 日元为止。求被偷走的总金额的期望值（对 $998244353$ 取模）。满足 $1 \le N \le 40$，$1 \le A_i \le 10^{16}$。

思路

第一步：重述为"随机排列取前缀"

随机地从未打开的箱子中依次选择，等价于把 $N$ 个保险箱随机打乱成一个排列，强盗按排列顺序从前往后取，直到前缀和达到 $X$。设 $A_{\text{all}} = \sum_{i} A_i$。

用 $S$ 表示"已经偷走的保险箱集合"。强盗在集合 $S$ 处停下来的前提是 $\sum_{i \in S} A_i < X$（否则早就停了），此时他会再开下一个箱子。

期望的线性分解：总偷窃金额等于各"开箱步"偷到的金额之和，于是

$$E = \sum_{\substack{S\subseteq [N]\\ \sum_{i\in S}A_i < X}} \Pr(\text{已偷集合恰为 } S) \cdot \mathbb{E}\big[\text{下一步偷到的金额} \big| \text{集合为 } S\big].$$

• 随机排列中，前 $|S|$ 个元素恰为集合 $S$ 的概率为

  $$\Pr(\text{前 } |S| \text{个恰为 } S) = \frac{|S|!\,(N-|S|)!}{N!} = \frac{1}{\binom{N}{|S|}}.$$

• 下一步从剩余 $N-|S|$ 个箱子中均匀随机取一个，期望金额为

  $$\frac{A_{\text{all}} - \sum_{i\in S}A_i}{N - |S|}.$$

因此

$$E = \sum_{\substack{S\\ \sum_{i\in S}A_i < X}} \frac{A_{\text{all}} - \sum_{i\in S}A_i}{\binom{N}{|S|}\,(N-|S|)}.$$

直接枚举 $S$ 有 $2^N$ 种，$N$ 最大为 $40$，不可行，需要 meet-in-the-middle。

第二步：按大小分组

对于大小为 $k$ 的集合，分母 $\binom{N}{k}(N-k)$ 是公共的，因此只需对每个 $k$ 统计两类量：

• 满足 $\sum_{i\in S}A_i < X$ 的大小为 $k$ 的子集个数 $c_k$；
• 所有这些子集的 $\sum_{i\in S}A_i$ 之和 $t_k$。

那么贡献为 $(c_k \cdot A_{\text{all}} - t_k) / \big(\binom{N}{k}(N-k)\big)$。

第三步：meet-in-the-middle

把集合分成左半 $T_l$（大小 $l$）与右半 $T_r$（大小 $r$，$l + r = N$）。

• 预处理：对右半，按子集大小 $k$ 分组，把每组内的子集和排序，并维护前缀和 $\mathit{pre}_k$。这样给定一个阈值，就能快速查出"大小恰为 $k$、子集和小于阈值"的子集个数及其和。
• 枚举左半的每个子集 $S_l$（和为 $s_l$、大小为 $i$），再枚举右半大小 $k$（$0 \le k \le r$）：用二分/滑动窗口求出右半中满足

  $$\sum_{i\in S_r}A_i < X - s_l$$

  的大小为 $k$ 的子集个数 $c$ 与和 $p$，则它们与 $S_l$ 合并后，对答案的贡献为

  $$\frac{c\cdot(A_{\text{all}} - s_l) - p}{\binom{N}{i+k}\,(N-i-k)}.$$

滑动窗口优化：对固定的 $(i,k)$，把 $L[i]$（左半大小为 $i$ 的所有子集和）排序后，随着 $s_l$ 递增，阈值 $X - s_l$ 单调递减，满足条件的右半子集个数单调不增，因此可用一个指针从右往左单调移动，把单次二分 $O(\log 2^r)$ 降到均摊 $O(1)$。

取模细节：所有分母模 $998244353$ 后均可逆（由题意保证）。$A_i$ 高达 $10^{16}$，需用 64 位整数存子集和，取模时再对 $MOD$ 取余。注意当 $i + k = N$ 时（子集为全集），其和 $A_{\text{all}} \ge X$，不会被计数，贡献为 $0$，对应的分母 $(N-i-k)=0$ 也不会被实际用到（在实现中用占位的 $q[N]=0$ 规避）。

参考代码

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

const ll MOD = 998244353;

ll modpow(ll a, ll e) {
    ll r = 1;
    a %= MOD;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

// 枚举 arr 的所有子集，按子集大小分组返回"每组的子集和列表"
vector<vector<ll>> enumerate(const vector<ll>& arr) {
    int m = (int)arr.size();
    vector<vector<ll>> res(m + 1);
    res[0].push_back(0);
    for (ll x : arr) {
        for (int k = m - 1; k >= 0; k--) {
            if (res[k].empty()) continue;
            for (ll s : res[k]) res[k + 1].push_back(s + x);
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll X;
    cin >> N >> X;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    int l = N / 2, r = N - l;
    vector<ll> Al(A.begin(), A.begin() + l);
    vector<ll> Ar(A.begin() + l, A.end());

    auto L = enumerate(Al);     // L[i]: 左半大小为 i 的所有子集和
    auto R = enumerate(Ar);     // R[k]: 右半大小为 k 的所有子集和

    for (auto& v : L) sort(v.begin(), v.end());

    ll Aall = 0;
    for (ll v : A) Aall = (Aall + v) % MOD;

    // q[k] = (C(N,k) * (N-k))^{-1} (mod MOD)；q[N] 为占位（该情形贡献恒为 0）
    vector<ll> q(N + 1, 0);
    for (int k = 0; k < N; k++) {
        ll c = 1;
        for (int i = 1; i <= k; i++) c = c * (N - k + i) / i;   // C(N,k)
        ll den = (ll)(N - k) % MOD * (c % MOD) % MOD;
        q[k] = modpow(den, MOD - 2);
    }

    ll ans = 0;
    for (int k = 0; k <= r; k++) {
        vector<ll>& tr = R[k];
        sort(tr.begin(), tr.end());
        vector<ll> pre(tr.size() + 1, 0);
        for (size_t i = 0; i < tr.size(); i++) pre[i + 1] = (pre[i] + tr[i]) % MOD;

        for (int i = 0; i <= l; i++) {
            const vector<ll>& tls = L[i];
            int p = (int)tr.size();          // 满足 sum(右) < X - sl 的个数
            for (ll sl : tls) {              // sl 递增，阈值递减，指针 p 单调左移
                ll lim = X - sl;
                while (p > 0 && tr[p - 1] >= lim) p--;
                ll base = (Aall - sl % MOD + MOD) % MOD;
                ll term = ((ll)p * base % MOD - pre[p] + MOD) % MOD;
                ans = (ans + term * q[i + k]) % MOD;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

本题官方题解给出的 Python（PyPy）参考实现（使用二分，而非滑动窗口）：

from math import comb
from bisect import bisect_left

n, x = map(int, input().split())
a = list(map(int, input().split()))

mod = 998244353

def gen(a):
    n = len(a)
    r = [[] for _ in range(n + 1)]
    r[0].append(0)
    for x in a:
        for k in reversed(range(n)):
            if r[k]:
                r[k + 1].extend(s + x for s in r[k])
    return r

h = n // 2
tls, trs = gen(a[:h]), gen(a[h:])

a_all = sum(a) % mod
q = [pow((n - k) * comb(n, k), -1, mod) for k in range(n)] + [0]  # 分母的逆元

ans = 0
for k, tr in enumerate(trs):
    tr.sort()

    pre = [0] * (len(tr) + 1)   # 前缀和
    for i in range(len(tr)):
        pre[i + 1] = (pre[i] + tr[i]) % mod

    for i, tl in enumerate(tls):
        for sl in tl:
            c = bisect_left(tr, x - sl)
            p = (c * (a_all - sl % mod) - pre[c]) % mod
            ans += q[i + k] * p % mod
            ans %= mod

print(ans)

复杂度分析

• 时间复杂度：设 $l = \lfloor N/2 \rfloor$，$r = N - l$。预处理（枚举子集并排序）为 $O(2^l \log 2^l + 2^r \log 2^r)$；滑动窗口查询为 $O((r+1)\,2^l + (l+1)\,2^r)$。总体上为 $O(N\cdot 2^{N/2})$。若使用逐次二分，则为 $O(N^2 \cdot 2^{N/2})$，官方题解也提示了这一点。
• 空间复杂度：$O(2^{N/2})$，需要存储两半所有子集和。

---

G - Celester 2

题目链接：https://atcoder.jp/contests/abc464/tasks/abc464_g

题目大意

给定长度为 $N$ 的天气串 $S$（S 晴、R 雨）。可以执行 $0$ 到 $k$ 次操作：选择一天 $i$，把它的天气翻转。操作结束后，快乐值为"相邻两天为'雨、晴'"的个数。对每个 $k = 0,1,\dots,N$，输出最多用 $k$ 次操作能得到的最大快乐值。共有 $T$ 组测试数据，$\sum N \le 10^6$。

思路

本题的转化链很长，我们逐步推导。

第一步：加哨兵，把目标换成"相邻不同对"的个数

在 $S$ 前补一个 S、后补一个 R，得到

$$T = \text{`S'} + S + \text{`R'},$$

并规定 $T$ 首尾的字符不可修改。设：

• $b$ 为 $T$ 中相邻字符不同的位置数；
• $a$ 为 $T$ 中相邻字符为"雨、晴"（即 R 在前、S 在后）的位置数。

由于 $T$ 从 S 开始、以 R 结束，相邻字符发生 $b$ 次变化，其中"$S\to R$"与"$R\to S$"交替出现，而最后一步变化必然是 $R\to S$，因此

$$a = \frac{b - 1}{2}.$$

注意 $a$ 恰好等于原题中的快乐值（首尾两对哨兵对绝不会构成"雨、晴"），所以最大化快乐值等价于最大化 $b$（即相邻不同对的数量）。

第二步：转成 0/1 序列，看清一次操作的"效果"

把长度 $N+1$ 的"相邻是否相同"序列记为 $D$：

$$D_i = \begin{cases}1, & T_i \ne T_{i+1},\\ 0, & T_i = T_{i+1},\end{cases}\qquad i = 0,1,\dots,N.$$

那么 $b = \sum_i D_i$。

翻转 $T$ 内部的一个字符 $T_i$（$1 \le i \le N$，非首尾），只会改变 $T_{i-1}$ 与 $T_i$、$T_i$ 与 $T_{i+1}$ 这两对是否相同，也就是同时翻转 $D_{i-1}$ 和 $D_i$ 这两个相邻位。例如 SR[S]SRRRRSR $\to$ SR[R]SRRRRSR 对应 1[10]100011 $\to$ 1[01]100011。

于是问题变成：给定一个 0/1 序列 $D$，每次操作翻转相邻两位，最多 $k$ 次，最大化 1 的个数。对 0/1 序列翻转相邻两位，效果只有三种：

• 00 → 11：1 的个数 $+2$；
• 01 → 10 或 10 → 01：1 的个数不变（相当于把 0 移动一格）；
• 11 → 00：1 的个数 $-2$。

显然 11 → 00 永远不会出现在最优解中。因此增加 1 的唯一手段是"把两个 0 移到一起并翻转成 11"，而 01 ↔ 10 的作用只是移动 0 的位置（每移动一格花费 1 次操作）。官方题解通过"操作序列标准化"证明了：最优操作序列中，不需要操作两个相邻的 1，且每个位置至多被操作一次。于是问题归结为把 0 两两配对并消除。

第三步：化为"选距离、不相邻"

设 $D$ 中 0 的位置为 $p_1 < p_2 < \dots < p_z$。为了把位置 $p$ 和 $q$ 的两个 0 变成 1，需要先把它们移到相邻（花费 $q - p - 1$ 次移动），再翻转一次（花费 $1$ 次），总代价恰为 $q - p$，即两个 0 之间的间距。

因此定义数组

$$D' = (p_2 - p_1,\ p_3 - p_2,\ \dots,\ p_z - p_{z-1}),$$

其中第 $j$ 个元素表示"把第 $j$ 个和第 $j+1$ 个 0 配对"的代价。由于每个 0 至多出现在一对中，所以被选择的 $D'$ 元素不能有相邻下标。

目标变为：在 $D'$ 中选择 $t$ 个互不相邻的元素，使得其和最小（记为 $\mathit{cost}_t$）；选择了 $t$ 对 0 会带来 $2t$ 个 1，即快乐值增加 $t$。于是 $k$ 次操作内的最大快乐值为

$$\text{ans}(k) = a + \max\{t : \mathit{cost}_t \le k\}.$$

第四步：Candies 贪心（JOISC 2018 经典问题）

"在数组中选 $t$ 个互不相邻的元素，最小化总和"正是 JOISC 2018 Day 4 Problem 1 "飴 (Candies)" 的模型，用如下贪心求解：

1. 维护一个最小堆与双向链表。反复取出当前最小元素 $d_i$，计入总代价；
2. 选中 $d_i$ 后，它左右相邻的 $d_{i-1}, d_{i+1}$ 都不能再选，把它们从链表中删除；
3. 但为了保留"反悔"（改选两个邻居）的机会，插入一个权值为

   $$d_{i-1} + d_{i+1} - d_i$$

   的合并元素顶替到原位置。这样在后续轮次若选中它，就等价于"撤销 $d_i$、改选 $d_{i-1}$ 与 $d_{i+1}$"，净花费恰好是 $d_{i-1}+d_{i+1}-d_i$。

重复该过程，第 $t$ 轮结束时累计的代价就是 $\mathit{cost}_t$。借助哨兵（数组两端插入 $+\infty$）避免边界特判。该贪心的正确性可由交换论证证明：任何最优选择的交换都会把方案变成贪心得到的结构，且每一步都维护了"所有 $t$ 都能取到最优"的不变量。

实现细节：

• $T = \text{`S'}+S+\text{`R'}$ 中"相同相邻对"的位置即 $D$ 中的 0；把它们收集到 $sam$，再由相邻 0 的位置差构造 $D'$。
• 初始快乐值 $a = \lfloor b/2 \rfloor$（$b$ 为 $T$ 中不同相邻对的个数）。
• 由于 $T$ 以 S 开头、以 R 结尾，最多能达到的快乐值是 $\lfloor N/2 \rfloor$（对应全交替串），因此最多配对 $\lfloor N/2 \rfloor - a$ 次，循环以 $val < N/2$ 为终止条件，且能证明该循环恰好用完所有真实配对，不会误取哨兵。
• 用 $\mathit{res}[\mathit{cost}] = \text{快乐值}$ 记录"恰好花费 $\mathit{cost}$ 次操作"能达到的快乐值，最后做一遍前缀最大值，得到"至多 $k$ 次"的答案。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        string s;
        cin >> n >> s;
        s = "S" + s + "R";            // 首尾加哨兵，且不可修改

        int val = 0;                  // b = 相邻不同对的个数
        vector<int> sam;              // D 中为 0（相邻相同）的位置
        for (int i = 0; i <= n; i++) {
            if (s[i] == s[i + 1]) sam.push_back(i);
            else val++;
        }
        val /= 2;                     // 初始快乐值 a = (b-1)/2

        // 0 之间两两距离 D'，两端各放两个"无穷大"哨兵
        vector<int> d;
        d.push_back(1e8);
        d.push_back(1e8);
        for (size_t i = 1; i < sam.size(); i++) {
            d.push_back(sam[i] - sam[i - 1]);
        }
        d.push_back(1e8);
        d.push_back(1e8);

        int dl = (int)d.size();
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<int> lef(dl), rig(dl), alive(dl, 1);
        for (int i = 0; i < dl; i++) {
            lef[i] = i - 1;
            rig[i] = i + 1;
            pq.push({d[i], i});
        }

        vector<int> res(n + 1, 0);    // res[cost] = 恰好花 cost 次操作的最大快乐值
        int hand = 0;
        res[hand] = val;

        while (val < n / 2) {
            auto od = pq.top();
            pq.pop();
            if (!alive[od.second]) continue;
            hand += od.first;
            val++;
            res[hand] = val;

            int id = od.second, el = lef[id], er = rig[id];
            // 合并：插入 d[el] + d[er] - d[id]，表示"改选两个邻居"的方案
            d[id] = d[el] + d[er] - d[id];
            pq.push({d[id], id});

            alive[el] = 0;
            {
                int x = lef[el], y = rig[el];
                lef[y] = x;
                rig[x] = y;
            }
            alive[er] = 0;
            {
                int x = lef[er], y = rig[er];
                lef[y] = x;
                rig[x] = y;
            }
        }

        for (int i = 1; i <= n; i++) res[i] = max(res[i], res[i - 1]);  // 前缀最大 => 至多 k 次
        for (int i = 0; i <= n; i++) {
            if (i) cout << ' ';
            cout << res[i];
        }
        cout << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(N \log N)$（单组数据）。构造 $D'$ 为 $O(N)$；贪心每轮取出并删除两个元素、插入一个元素，堆操作共 $O(N \log N)$。
• 空间复杂度：$O(N)$，用于存储 $D'$、链表与答案数组。

---

（完）