「Substract」减操作

题目描述

给定数组 $a_1\sim a_n$ 与目标 $t$ 。一次减操作把相邻两项 $a_i,a_{i+1}$ 替换为 $a_i-a_{i+1}$ ，数组长度减一。经过 $n-1$ 次操作后只剩一个数，要求输出每次操作的位置 $p_k$ （当前数组中的 1-based 位置），使最终结果等于 $t$ ；无解则不输出。

输入： $n,t$ ，随后 $n$ 行各一个 $a_i$ 。输出： $n-1$ 行，每行一个操作位置。数据范围 $1\le n\le100$ ， $1\le a_i\le100$ ， $-10^4\le t\le10^4$ 。

样例： $n=5,t=4,a=[12,10,4,3,5]$ ，输出 2 3 2 1 为合法方案之一。

思路

每次合并 $x-y$ 时，减数所在块的系数整体变号，因此最终结果可写成 $a_1\pm a_2\pm\dots\pm a_n$ ， $a_1$ 恒正、 $a_2$ 恒负。用线性 DP 求一组能凑出 $t$ 的符号，再按固定规则还原操作位置：先依次消去取正号的项，最后从位置 1 连续消去取负号的项。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59"""ROJ 3167 减操作：给每次减操作输出一个合法位置序列。

核心观察：无论操作顺序如何，a[1] 的最终系数恒为 +1，且 a[2] 必为 -1，
故答案形如 t = a[1] - a[2] ± a[3] ± ... ± a[n]，只需 DP 求一组符号，
再按固定规则还原操作序列（先消 +1 项，最后从 1 号位消掉全部 -1 项）。
f[i][v] = 前缀 a[1..i] 凑出 v 时 a[i] 的符号（+1/-1/0 不可达），
回溯时优先取 +1，与题目约定保持一致；无解时 f 全 0，恰好什么都不输出。
"""
import sys

OFF = 10_000  # 值域 [-10000, 10000] 的下标平移常数


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, t = next(data), next(data)
    a = [next(data) for _ in range(n)]
    if n == 1:
        return  # 长度 1 无操作，不输出

    # f[i][v]：凑出 v 时 a[i] 取的符号；0 表示该状态不可达
    f: list[list[int]] = [[0] * (2 * OFF + 1) for _ in range(n + 1)]
    f[1][OFF + a[0]] = 1
    f[2][OFF + a[0] - a[1]] = -1  # a[2] 只能作为减数
    for i in range(3, n + 1):
        fi, fp, ai = f[i], f[i - 1], a[i - 1]
        for j in range(2 * OFF + 1):
            if fp[j]:
                if j + ai <= 2 * OFF:
                    fi[j + ai] = 1  # a[i] 取 +：上一步和为 j - a[i]
                if j >= ai:
                    fi[j - ai] = -1  # a[i] 取 -：上一步和为 j + a[i]

    # 回溯符号（优先 +1）；无解时 ans 全 0，输出恰为空
    s = OFF + t
    ans = [0] * (n + 1)
    for i in range(n, 1, -1):
        ans[i] = f[i][s]
        if ans[i] == 1:
            s -= a[i - 1]
        elif ans[i] == -1:
            s += a[i - 1]

    # 还原操作序列：先依次消去每个 +1 项，末尾再从 1 号位消掉所有 -1 项
    ops: list[str] = []
    cnt = 0  # 已消去的 +1 个数，其后位置整体左移
    for i in range(2, n + 1):
        if ans[i] == 1:
            ops.append(str(i - cnt - 1))
            cnt += 1
    for i in range(2, n + 1):
        if ans[i] == -1:
            ops.append("1")
    if ops:
        sys.stdout.write("\n".join(ops) + "\n")


if __name__ == "__main__":
    main()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:58
 * update_at: 2026-10-06 11:58
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int OFF = 10000;          // 值域平移量，把 [-10000,10000] 映射到 [0,20000]
const int MAXV = 2 * OFF + 1;   // DP 值域大小

int n;
ll t;
ll a[105];          // 原始数组，下标从 1 开始
int f[105][MAXV];   // f[i][v]：前缀到 i 凑出值 v 时 a[i] 的符号（1=+，-1=-，0=不可达）
int s[105];         // 回溯得到的符号序列，s[1] 恒为 +1

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

    if (!(cin >> n >> t)) return 0;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    if (n == 1) return 0;   // 无操作，不输出

    // 初始化：a[1] 系数恒为 +1；a[2] 必为 -1（第一次操作只能在位置 1）
    f[1][OFF + (int)a[1]] = 1;
    f[2][OFF + (int)(a[1] - a[2])] = -1;

    // 线性 DP：f[i][v] 由 f[i-1][v-a[i]]（取 +）或 f[i-1][v+a[i]]（取 -）转移
    for (int i = 3; i <= n; ++i) {
        for (int j = 0; j < MAXV; ++j) {
            if (f[i - 1][j] == 0) continue;
            if (j + (int)a[i] < MAXV) f[i][j + (int)a[i]] = 1;   // 取 +
            if (j >= (int)a[i])       f[i][j - (int)a[i]] = -1;  // 取 -
        }
    }

    int cur = OFF + (int)t;
    if (f[n][cur] == 0) return 0;   // 无解，静默输出 0 行

    // 倒推符号，优先取 +1（与标程约定一致）
    for (int i = n; i >= 1; --i) {
        s[i] = f[i][cur];
        if (s[i] == 1) cur -= (int)a[i];
        else if (s[i] == -1) cur += (int)a[i];
    }

    // 还原操作位置：先依次消去每个 +1 项，末尾再从 1 号位消掉所有 -1 项
    int cnt = 0;    // 已消去的 +1 个数，其后元素位置整体左移
    for (int i = 2; i <= n; ++i) {
        if (s[i] == 1) {
            cout << (i - cnt - 1) << "\n";
            ++cnt;
        }
    }
    for (int i = 2; i <= n; ++i) {
        if (s[i] == -1) {
            cout << "1\n";
        }
    }

    return 0;
}