「Addition Chains」加成序列

形式化题目

满足如下条件的序列 $X$ （序列中元素被标号为 $1, 2, \dots, m$ ）被称为“加成序列”：

$X[1] = 1$
$X[m] = n$
$X[1] < X[2] < \dots < X[m-1] < X[m]$
对于每个 $k$ （ $2 \le k \le m$ ）都存在两个整数 $i$ 和 $j$ （ $1 \le i,j \le k-1$ ， $i$ 和 $j$ 可相等），使得 $X[k]=X[i]+X[j]$ 。

给定一个整数 $n$ ( $1 \le n \le 100$ )，找出符合上述条件的长度 $m$ 最小的“加成序列”。如果有多个满足要求的答案，只需要找出任意一个可行解。

多组测试数据，每行一个 $n$ 。当输入 $0$ 时表示输入结束。对于每个测试用例，按特殊格式（见下方总结）输出这个最短的序列。

正解

思路

这是一道搜索题，要求找到使序列末尾为 $n$ 的最短长度。因为要求寻找最短步数，且每次状态分岔极多，普通的 DFS 容易陷入深层的死胡同，而 BFS 的状态空间又过大，因此可以考虑使用迭代加深搜索（IDDFS）。

我们从小到大枚举序列的长度 depth，在限定的长度下进行 DFS：

序列第一个元素固定为 1。
每次扩展新的元素 $X[u]$ 时，我们从 $X[1]$ 到 $X[u-1]$ 中选取两个数相加。
为了尽快逼近目标，选择相加的两个数时可以从大到小枚举，先尝试较大的数。
剪枝1（可行性剪枝）：当前元素最大只能是前一个元素的 2 倍。如果当前最大元素 $X[u-1]$ 不断翻倍，直到序列长度达到限制 depth 时，产生的值仍然小于 $n$ ，说明在当前长度限制下绝不可能达到 $n$ ，可直接剪枝返回 false。
剪枝2（排除等效冗余）：同一个 $X[u]$ 可能由多组不同的 $i, j$ 相加得到。我们可以用一个布尔数组 st 记录在当前深度下已经尝试过的值，避免重复搜索同样的 $X[u]$ 。

由于题目中说明只需任意一个可行解，因此一旦找到一个合法的加成序列，就可以立即结束搜索并输出。

代码

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#!/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-09 09:00
# update_at: 2026-10-09 18:44

import sys

MAXM = 20  # n <= 100 时最短链长最多 10，留够任意搜索路径


def dfs(u: int, depth: int, n: int, path: list[int], tried: set[int]) -> bool:
    """在长度恰好 depth 的限制下填 path[u]；tried 是本帧已试过候选值的集合（等效冗余剪枝）。"""
    if u == depth:
        return path[u - 1] == n
    max_val = path[u - 1]
    if max_val << (depth - u) < n:  # 后面每步最多翻倍，翻满仍够不到 n 就剪掉
        return False
    for i in range(u - 1, -1, -1):  # 候选值从大到小枚举，优先逼近 n
        for j in range(i, -1, -1):  # i, j 允许相等
            nxt = path[i] + path[j]
            if nxt > n or nxt <= max_val or nxt in tried:
                continue
            tried.add(nxt)
            path[u] = nxt
            if dfs(u + 1, depth, n, path, set()):
                return True
    return False


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    path = [0] * MAXM
    out: list[str] = []
    for n in data:
        if n == 0:  # 单行 0 表示输入结束
            break
        depth = 1
        path[0] = 1
        while not dfs(1, depth, n, path, set()):  # 迭代加深：长度不够就加一
            depth += 1
        out.append(f"{depth}   {' '.join(map(str, path[:depth]))}")  # 长度 m + 3 个空格 + 序列
    sys.stdout.write('\n'.join(out) + '\n' if out else '')


if __name__ == '__main__':
    solve()

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/**
 * 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-09 09:00
 * update_at: 2026-10-09 18:44
 */
// roj 3065《Addition Chains 加成序列》：迭代加深搜索(IDDFS)求最短加成序列。
// 从小到大枚举序列长度 depth，在限定长度内 DFS；第一次找到解时的 depth 就是最小长度。
#include <iostream>

using namespace std;

typedef long long ll;

const int MAXM = 20;   // n <= 100 时最短链长最多 10，20 足够放下任意搜索路径
const int MAXV = 105;  // 值域上界，n <= 100

ll path[MAXM];         // 当前搜索路径 path[0..depth-1]
bool st[MAXM][MAXV];   // st[u][v]：第 u 层这一帧是否已试过候选值 v（按层隔离，等效于每帧一个局部数组）

bool dfs(int u, int depth, ll n) {
    if (u == depth) {
        return path[u - 1] == n;
    }
    // 剪枝1（可行性）：每一步最多让末尾翻倍，
    // 若一路翻倍到序列末尾仍够不到 n，则当前深度一定无解。
    ll max_val = path[u - 1];
    if (max_val * (1 << (depth - u)) < n) {
        return false;
    }
    // 剪枝2（等效冗余）：同一个候选值可能由多组 (i, j) 拼出，本帧内只搜一次。
    for (int v = 1; v <= n; v++) {
        st[u][v] = false;
    }
    // 候选值从大到小枚举，优先逼近 n；i, j 允许相等（i 从 u-1 往 0 扫，j 从 i 往 0 扫）
    for (int i = u - 1; i >= 0; i--) {
        for (int j = i; j >= 0; j--) {
            ll nxt = path[i] + path[j];
            if (nxt > n || nxt <= path[u - 1] || st[u][nxt]) {
                continue;
            }
            st[u][nxt] = true;
            path[u] = nxt;
            if (dfs(u + 1, depth, n)) {
                return true;
            }
        }
    }
    return false;
}

void solve() {
    ll n;
    while (cin >> n && n != 0) {   // 多组测试数据，读到 0 结束
        int depth = 1;
        path[0] = 1;
        while (!dfs(1, depth, n)) {  // 迭代加深：长度不成立就加一
            depth++;
        }
        cout << depth << "   ";      // 题面格式：长度 m 后接 3 个空格
        for (int i = 0; i < depth; i++) {
            cout << path[i] << (i == depth - 1 ? "" : " ");
        }
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度

时间复杂度：迭代加深搜索的时间复杂度取决于解的深度和分支因子，由于采用了强力的可行性剪枝，搜索树被大幅修剪。最大 $n=100$ ，最坏情况下的状态数也不多，时间复杂度在指数级但常数小，在此规模下完全能通过。
空间复杂度：递归深度最大不超过 $m$ （实际上当 $n \le 100$ 时， $m$ 最大仅为 10）。空间复杂度主要来自于递归调用栈与剪枝用的访问标记数组 $O(n \times m)$ ，极其微小。

总结

本题是典型的题面与数据实际格式脱节、且伴随严重多解性的题目。

1. 题面样例与数据的格式不一致

这是本题最大的坑点。「最短长度 m + 3 个空格 + 序列」是从数据反推的格式，题面中完全未定义该格式。

S1：题面的输出样例首行为 1 2 4 5（无 m 前缀）。但对应的 .out 数据中为 4 1 2 4 5。
S2：逐行对比每行 token 数发现，数据的 token 数量恒比题面样例多 1，多出来的正是最前方的 m。
S3：题面「输出格式」段落仅描述为“输出一个满足需求的整数序列，数字之间用空格隔开”，完全未提及 m 以及 3 个空格。
反向验证：如果把数据的 m 与 3 空格前缀去掉，则样例数据与 .out 逐行完全相同。这就排除了“理解错题意”的可能，确系数据作者在生成数据时带了前缀而未在题面中写明。

2. 多解确证（本题强烈需要 spj）

经过异源独立 BFS 验证（穷举 n = 1..100，非抽样）：

存在多解性：在 $1 \dots 100$ 中，拥有【唯一】最优解的 $n$ 只有 8 个：1, 2, 3, 4, 8, 16, 32, 64（即 2 的幂次与 1…4）。
多解情况多发：剩余 92 个 $n$ 均存在多解。例如 $n=100$ 存在 62 条不同的最优链， $n=5$ 也存在 (1,2,3,5) 与 (1,2,4,5) 等。
闸门适应性缺陷：题面明确要求“任意一个可行解”，但由于当前库中缺乏 spj 脚本（spj/3065.py 缺失），如果随便输出另一条合法的最优链，也会被字节级闸门判错。当前代码能 AC 完全是因为“反序枚举”恰好命中了所有 .out 答案中的最大字典序解——这是数据运气，并非该实现方式有多安全。

V8 相邻候选表：

候选 tie-breaker / 算法	失败点集合	失败行数
反序枚举候选（现实现）	∅	0
最优集中字典序最大（穷举）	∅	0
正序枚举候选	`[1..10]`	187
最优集中字典序最小（穷举）	`[1..10]`	187
优先最接近 n/2 的候选	`[1..10]`	163
贪心翻倍 / 贪心优先跳 n	`[2,4,5,6,7,8,10]`	66

（注：反序枚举与字典序最大的行级失败集完全相同，说明是同一解而并非区分出的候选。）

3. 独立最小长度 vs `.out` 的 `m`

经过完全核实：

全局所有数据的 210 行中，每行的 m 精确等于经过独立 BFS 计算出的最少长度。
$n = 1 \dots 100$ 的数据规模中，最大的最短长度 $m = 10$ （对应于 $n \in \{71,79,87,89,91,93,94,95\}$ ）。
全部 10 个测试点共包含 210 行查询：C1=6、C2=5、C3=11、C4=14、C5=20、C6=15、C7=16、C8=14、C9=9、C10=100。

4. 数据缺陷（CRLF）与闸门鉴别力

测试数据文件存在较为严重的回车换行混淆问题：

.in 与 .out 的 10/10 个点全部是纯 CRLF（\r\n），完全没有单纯的 LF。
这导致原始字节比较闸门被 CRLF 完全淹没，导致连 baseline 的准确输出也是 0/10 的通过率。
归一后才可信：在将 .out 复制并执行 CRLF $\to$ LF 的归一操作后，baseline 才达到逐字节 10/10 通过。这证实原始报错是【数据缺陷】而非程序缺陷。
此外，token 闸门对于空白符的判断存在免疫性缺陷。如果把前缀后的“3 个空格”替换为“1 空格”、“2/4 空格”或“tab”，token 闸门均能判定通过。

V1 反事实表：

变体	token 闸门失败点	原始字节	归一字节（去 CRLF）
baseline	∅	[1…10]	∅
3 空格→1 空格	∅ ⚠	[1…10]	[1…10]
3 空格→tab	∅ ⚠	[1…10]	[1…10]
3 空格→2/4 空格	∅ ⚠	[1…10]	[1…10]
去掉每组末尾换行	[1…10]	[1…10]	[1…10]
强制输出 CRLF	∅	∅	∅
不输出 `m`	[1…10]	[1…10]	[1…10]
`m` 写错（m+1）	[1…10]	[1…10]	[1…10]
候选改升序（另一 tie-breaker）	∅ ⚠	[1…10]	[1…10]
去掉剪枝2（`st` 去重）	∅	[1…10]	∅
去掉剪枝1（可行性）	∅	[1…10]	∅
强制深度+1（非最优）	[1…10]	[1…10]	[1…10]
序列漏首项	[1…10]	[1…10]	[1…10]
另一条最优链	[1…10]	[1…10]	[1…10]
更长合法链（非最小）	[1…10]	[1…10]	[1…10]
非法链（末项非两数之和）	[1…10]	[1…10]	[1…10]
`m` 与序列长度不符	[1…10]	[1…10]	[1…10]

（注：“强制输出 CRLF”在三列全为 ∅，是唯一不需要归一化就能同时通过原始字节闸门的方法，但根据纪律，我们不应为了迁就异常数据而在代码中故意硬编码回车符。）

5. 探针与不变量验证

V2 静态常量探测：main.cpp 常量 {0, 1, 20, 105} 与 main.py 常量 {0, 1, 20} 与实际序列解 {2,4,5,6,…,96,98,99} 无任何重叠，非硬编码。
V4 结构不变量：每行 .in 被完整消费且末 token 恒为 0。每行 .out 的行数完全对应 $n$ 的个数；m 恰好等于序列长度；首项为 1、末项为对应 $n$ ，序列均严格递增，且每一项均为前序某两数之和（实测全满足）。
V6 异源对拍：通过穷举 $n = 1..100$ 的非抽样对拍，两种实现产生的数据均：m 错 0 处，非最优链 0 处。
V9 UB与越界：UBSan 的 stderr 10 个点全空；-ftrapv 全 0；ASan+UBSan 全空。对照组（将 INT_MIN 取反）则确实报错，探针有效，说明代码无越界无未定义行为。

6. T9 检查项

整数越界/溢出：本题要求计算到 100，完全在常规 32 位甚至 8 位整数范围，不涉及大数和越界。
数组/边界与越界：本题数组在 $n \le 100$ 情况下，最深层递归不超过 20 层（实际最大解 $m=10$ ），数组大小开为 105 和 20 绝对充足。
多组数据/重复初始化：在每轮进入 DFS 前均会对状态和 path 初始化，不会导致多组数据污染。
特例处理： $n=1$ 时特例不影响（此时 depth = 1，序列正确输出 1）。
行末空格等格式问题：由于特殊要求，已使用了 m 与 3 个空格分隔的格式正确复刻数据格式。