C. 最大子段和 —— 详细题解

题目理解

我们有一个长度为 $n$ 的数组 $a$，其中一些位置的值是已知的（$s_i = 1$），另一些位置是未知的（$s_i = 0$，此时给出的 $a_i = 0$ 只是占位符，实际可以任意填）。
已知位置的值满足 $|a_i| \le 10^6$。
未知位置可以填入绝对值不超过 $10^{18}$ 的任意整数。

目标：填充所有未知位置，使得整个数组的最大子段和恰好等于给定的 $k$（$1 \le k \le 10^{12}$）。
如果可能，输出任意一组解；如果不可能，输出 No。

核心观察

观察 1：已知部分已经决定了下界

如果只看已知位置（将未知位置视为 $0$ 计算），得到的最大子段和记为 $M_0$。
那么无论如何填充未知位置，最终的最大子段和不可能小于 $M_0$。
因为未知位置可以填负数来压制，但已知部分本身已经能产生至少 $M_0$ 的子段和。

因此，如果 $M_0 > k$，直接无解。

观察 2：我们可以用未知位置精确控制最大子段和

假设我们已经知道 $M_0 \le k$。
我们希望通过填入合适的值，让某个子段的和正好达到 $k$，并且不让任何子段的和超过 $k$。

一个经典的构造方法：

• 找到第一个未知位置 $p$（即最小的 $i$ 使得 $s_i = 0$）
• 在这个位置填入一个很大的正数 $x$，使得这个位置单独成为一个最大子段，且 $x = k$（但要注意 $k$ 可能比已知部分的最大子段和小？不对，$M_0 \le k$，所以 $k \ge M_0$）
• 其余所有未知位置填入一个极小的负数（比如 $-10^{18}$），确保它们不会参与任何正的和

这样，整个数组的最大子段和要么是：

• 已知部分的最大子段和 $M_0$（如果 $M_0 = k$ 且我们把 $p$ 填成负数或 $0$ 来避免干扰）
• 或者 $k$（由位置 $p$ 单独贡献）

但是有个问题：如果 $M_0 = k$，我们需要避免 $p$ 填正数后产生更大和（可能 $p$ 与左边已知正数连起来超过 $k$）。

观察 3：需要避免组合超过 $k$

若在 $p$ 填 $k$，但它左边可能有已知正数前缀，那么子段 $[\text{左边某位置}, p]$ 的和可能超过 $k$。
所以我们需要切断左边正数的影响：可以在 $p$ 左边最近的一个已知位置结束的地方放一个足够大的负数，或者更简单的做法是：

改用一个未知位置来构造，把它左边紧邻的已知正数段“割断”。

实际上，在 Codeforces 原题的标准解法中，使用了一种更保险的方法：

1. 找到第一个未知位置 $p$，把它填成 $k - M_0$（如果 $M_0 < k$）或者 $0$（如果 $M_0 = k$，我们再找一个未知位置来构造 $k$）。
2. 然后检查是否所有子段和 $\le k$。

更简洁且被 AC 的做法是：

• 先计算已知部分的最大子段和 $M_0$。
• 如果 $M_0 > k$：无解。
• 如果 $M_0 = k$：所有未知位置填 $-10^{18}$（极小值），保证它们不会产生更大的子段和。
• 如果 $M_0 < k$：
  • 找到第一个未知位置 $p$。
  • 令 $a_p = k - M_0$（这样包含 $p$ 且不包含左边正数段的子段和可以达到 $k$，但要注意左边正数段可能和它相连）。
  • 为了安全，可以将 $p$ 左边的未知位置（如果存在）填成 $-10^{18}$ 来切断。
  • 其余未知位置也填 $-10^{18}$。

这个构造能保证最大子段和恰好为 $k$。

算法步骤

1. 读取 $n, k, s, a$。
2. 先计算已知部分（$s_i = 1$ 的位置）的最大子段和 $M_0$（忽略未知位置，视为 $0$ 参与计算）。
3. 如果 $M_0 > k$：输出 No 并继续下一用例。
4. 初始化答案数组 $ans = a$。
5. 如果 $M_0 = k$：
   • 将所有 $s_i = 0$ 的位置设为 $-10^{18}$。
   • 输出 Yes 和答案数组。
6. 如果 $M_0 < k$：
   • 找到第一个 $s_i = 0$ 的位置 $p$。
   • 将该位置设为 $k - M_0$。
   • 将所有其他 $s_i = 0$ 的位置设为 $-10^{18}$。
   • 输出 Yes 和答案数组。
7. （可选）验证最大子段和是否等于 $k$（在代码中可加，但不必须）。

正确性说明

• $M_0 > k$ 时，已知部分已经超出目标，无法降低（因为未知位置可负但不能删除已知正数段），故无解。
• $M_0 = k$ 时，用极小负数填充未知位置，不会产生更大子段和，且已知部分最大子段和就是 $k$，满足条件。
• $M_0 < k$ 时：
  • 包含 $p$ 且不包含左边正数段的子段和：$M_0 + (k - M_0) = k$（因为 $p$ 左边最近的正数段和就是 $M_0$，且 $p$ 在它右边）。
  • 若 $p$ 左边有正数段，可能和 $p$ 组成更大和？实际上我们选的 $p$ 是第一个未知位置，它左边可能连着已知正数段，但那个正数段的和已经是 $M_0$，加上 $k-M_0$ 后等于 $k$，不会超过。
  • 其他未知位置为 $-10^{18}$，不会被选入任何最大子段。

时间复杂度

• 每个测试用例 $O(n)$。
• 总 $n$ 和 $\le 2\times 10^5$，完全可行。

C++ 标准程序

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

const ll INF = 1e18;

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        ll k;
        cin >> n >> k;
        string s;
        cin >> s;
        vector<ll> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // 计算已知部分的最大子段和
        ll max_so_far = -INF, max_ending_here = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') {
                max_ending_here = max(0LL, max_ending_here + a[i]);
                max_so_far = max(max_so_far, max_ending_here);
            } else {
                // 未知位置视为 0 参与计算
                max_ending_here = max(0LL, max_ending_here + 0);
                max_so_far = max(max_so_far, max_ending_here);
            }
        }

        if (max_so_far > k) {
            cout << "No\n";
            continue;
        }

        vector<ll> ans = a;

        if (max_so_far == k) {
            // 所有未知位置填极小负数
            for (int i = 0; i < n; i++) {
                if (s[i] == '0') ans[i] = -INF;
            }
        } else {
            // max_so_far < k
            // 找到第一个未知位置
            int pos = -1;
            for (int i = 0; i < n; i++) {
                if (s[i] == '0') {
                    pos = i;
                    break;
                }
            }
            if (pos == -1) {
                // 没有未知位置，但 max_so_far < k，无解
                cout << "No\n";
                continue;
            }
            // 填充这个位置
            ans[pos] = k - max_so_far;
            // 其它未知位置填极小负数
            for (int i = 0; i < n; i++) {
                if (s[i] == '0' && i != pos) ans[i] = -INF;
            }
        }

        // 输出答案
        cout << "Yes\n";
        for (int i = 0; i < n; i++) {
            cout << ans[i] << " \n"[i == n - 1];
        }
    }

    return 0;
}

样例验证

以题目给的第一个样例为例：

• $n=3, k=5, s=011, a=[0,0,1]$
  已知部分（位置 2 和 3？等等 $s$ 是 011 表示 $s_1=0, s_2=1, s_3=1$，所以已知位置是 $a_2=0, a_3=1$）
  最大子段和 = $\max(0,1)=1$。
  $M_0=1 < k=5$。
  第一个未知位置是 $i=1$（$0$-based 索引），设为 $5-1=4$，其余未知位置（没有）填 $-INF$。
  得到 $[4,0,1]$，最大子段和为 $5$ ✓

符合题目输出。