和为零

题目描述

给定 $N$ （ $3 \le N \le 9$ ），在递增数列 $1, 2, \ldots, N$ 的每相邻两数之间插入 +、- 或空格，空格表示把这两个数字拼接成一个多位数，再对整个表达式求和。

输入一行一个整数 $N$ ；按 ASCII 码顺序输出所有和为 $0$ 的表达式，每行一个，空格要原样保留。样例 $N=7$ 的第一条解为 1+2-3+4-5-6+7，最后一条为 1-2-3-4-5+6+7。

思路

每相邻两数间只有 3 种填法，共 $3^{N-1} \le 6561$ 种方案，全部枚举即可。让靠后的空隙变化更快、并按 ' ' < '+' < '-' 的顺序枚举，产出的表达式天然就是 ASCII 序；求值时按 +/- 切项、项内去掉空格再拼成整数累加。

参考代码

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#!/usr/bin/env python3
# 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-01 04:02
# update_at: 2026-10-01 04:02

import re
import sys
from itertools import product


def value(expr: str) -> int:
    """把空格当“拼接”求表达式的值：带空格的项整项转 int，如 '-2 3' = -23。"""
    return sum(int(term.replace(' ', '')) for term in re.findall(r'[+-]?[^+-]+', expr))


def zero_sum(n: int) -> list[str]:
    """枚举每对数字间的符号并返回所有和为 0 的表达式（按 ASCII 序）。"""
    digits = ''.join(map(str, range(1, n + 1)))
    # 符号串 ' +-' 已按 ASCII 排好，product 产出的顺序天然就是题目要求的输出顺序
    candidates = (
        ''.join(a + b for a, b in zip(digits, syms)) + digits[-1]
        for syms in product(' +-', repeat=n - 1)
    )
    return [expr for expr in candidates if value(expr) == 0]


def solve() -> None:
    n = int(sys.stdin.read())
    print('\n'.join(zero_sum(n)))


if __name__ == "__main__":
    solve()

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84/**
 * 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 09:51
 * update_at: 2026-10-06 09:51
 */

// main.cpp：和为零（USACO zerosum）
// 做法：每对相邻数字之间填 '+', '-', ' ' 三种符号，共 3^(n-1) 种方案，
// 全部枚举并求值，输出结果为 0 的表达式。
// 按 ' ' < '+' < '-' 的顺序从前往后枚举，正好就是题目要求的 ASCII 输出顺序。

#include <cstdio>

typedef long long ll;

const int MAXN = 15;

ll n;                              // 数列长度
char sym[MAXN];                    // sym[i]：第 i 个空隙填入的符号
char buf[2 * MAXN + 5];            // 拼接出的表达式字符串
ll len;                            // buf 的当前长度

char order[3] = {' ', '+', '-'};   // 三种符号按 ASCII 从小到大排列

// 根据当前 sym[] 拼出完整表达式，空格直接跳过（表示把相邻数字拼成一个多位数）
void build() {
    len = 0;
    for (ll i = 1; i <= n; ++i) {
        buf[len] = '0' + i;
        ++len;
        if (i < n) {
            buf[len] = sym[i];
            ++len;
        }
    }
    buf[len] = '\0';
}

// 扫描表达式求值：先累加当前项，遇到 + / - 时把当前项结算进总和
ll calc() {
    ll total = 0;
    ll cur = 0;    // 当前项正在拼接的数值
    ll sign = 1;   // 当前项的符号，第一项默认为正
    for (ll i = 0; i < len; ++i) {
        char c = buf[i];
        if (c == '+') {
            total += sign * cur;
            cur = 0;
            sign = 1;
        } else if (c == '-') {
            total += sign * cur;
            cur = 0;
            sign = -1;
        } else if (c == ' ') {
            continue;  // 空格表示拼接，忽略即可
        } else {
            cur = cur * 10 + (c - '0');
        }
    }
    total += sign * cur;
    return total;
}

// 第 dep 个空隙选择符号，选完 n-1 个后检查表达式是否等于 0
void dfs(ll dep) {
    if (dep == n) {
        build();
        if (calc() == 0)
            printf("%s\n", buf);
        return;
    }
    for (int k = 0; k < 3; ++k) {
        sym[dep] = order[k];
        dfs(dep + 1);
    }
}

int main() {
    scanf("%lld", &n);
    dfs(1);
    return 0;
}

目录

题目描述

思路

参考代码