《进阶指南》0x24 A

upd23/1/9 初稿发布。

upd 23/5/12 将题意第四点补充完整，修改部分表述。

其实这道题剪枝非常多。

Part 1 题意

• 定义 "addition chain" 为满足如下条件的序列（为方便表示，这里序列下表从1开始记）：
  1. $a_1=1a\_1\; =\; 1$；
  2. $a_m=na\_m\; =\; n$；
  3. （单调上升序列）；
  4. 对于每个 $kk$（$2\le k\le m2\; \backslash le\; k\; \backslash le\; m$）都存在两个整数 $ii$ 和 $jj$（$1\le i,j\le k-11\; \backslash le\; i,\; j\; \backslash le\; k\; -\; 1$，$ii$ 和 $jj$ 可以相等）使得 $a_k=a_i+a_{j}a\_k=a\_i+a\_j$。
• 已知整数 $nn$（UVa $1\le n\le 10^{4}1\; \backslash le\; n\; \backslash le\; 10^4$，NowCoder $1\le n\le 10^{2}1\; \backslash le\; n\; \backslash le\; 10^2$），输出符合上述条件的 $mm$ 最小的 "addition chain"，如有多个解，只需输出一个解

Part 2 思路

2.1 离线做法（NowCoder AC, UVa TLE）

起初，考虑到多组数据会有重复搜索，想到把所有询问记录下来，离线求解所有情况，在最后统一输出。然而，这样的话，虽然一定程度上减少了重复计算，但是可以剪枝的内容非常小，小数据还能 AC，强化版 TLE 得很厉害，pass 掉！

2.2 在线做法

从小到大将序列的每一个位置 $kk$ 作为层次，枚举 $a_k=a_i+a_{j}a\_k\; =\; a\_i\; +\; a\_j$ 作为分支，然后递归填写下一个位置。

剪枝：

1. 优化搜索顺序：
   • 为了让序列中的数尽快逼近 $nn$，我们在枚举 $ii$ 和 $jj$ 时从大到小枚举
2. 排除等效冗余1：
   • 因为 $a_i+a_j=a_j+a_{i}a\_i\; +\; a\_j\; =\; a\_j\; +\; a\_i$，所以 $jj$ 可以从 $j=ij\; =\; i$ 开始枚举
3. 排除等效冗余2：
   • 在此基础上，对于不同的 $ii$ 和 $jj$，$a_i+a_{j}a\_i\; +\; a\_j$ 仍可能相等
   • 我们可以在枚举时用一个 bool 数组对 $a_i+a_{j}a\_i\; +\; a\_j$ 进行判重，避免重复搜索同一个和
4. 可行性剪枝1：
   • 根据序列的单调上升性，
   • 当 $a_i+a_j\le a_{k-1}a\_i\; +\; a\_j\; \backslash le\; a\_\{k-1\}$ 时，显然有
   • 所以，我们在发现 $a_i+a_j\le a_{k-1}a\_i\; +\; a\_j\; \backslash le\; a\_\{k-1\}$ 之后不需要往下继续枚举（往下肯定更小），直接退出内层循环
5. 可行性剪枝2：
   • 考虑到序列的单调上升性，易得 $2a_k\ge a_{k+1}2\; a\_k\; \backslash ge\; a\_\{k+1\}$，那么 $2^{m-k}{a}_k\ge a_{m}2^\{m-k\}\; a\_k\; \backslash ge\; a\_m$
   • 所以，当发生 的情况时，剪枝
   • 也就是说，在枚举过程中，根据单调上升，当 时，退出内层循环

（第 1、3 条为书上内容，其它为我补充的剪枝）

Part 3 实现

老规矩，只要是交到 UVa 上去，就一定要注意格式，行末不能有多余的空格。此外根据那五条剪枝来写就行了。本题没有什么别的坑点。

代码里有一些变量名和我上文表述的有所出入，这里说明一下：

1. x 数组表示上文 a 数组
2. depth 表示上文 k - 1
3. v 数组就是上文说的用作hash的 bool 数组

最终的代码：

#include <stdio.h>
#define MAXN 10005
#define SIZE 25

int n, m, x[SIZE];

bool dfs(int depth) {
    if (depth == m) {
        if (x[m] == n) {
            for (int i = 1; i <= m; ++i) {
                if (i > 1) printf(" ");
                printf("%d", x[i]);
            }
            printf("\n");
            return 1;
        } else {
            return 0;
        }
    }
    bool v[MAXN] = {0};
    for (int i = depth; i > 0; --i) {      // 优化搜索顺序
        for (int j = i; j > 0; --j) {      // 排除等效冗余1
            int nxt = x[i] + x[j];
            if (nxt<=x[depth]) break;      // 可行性剪枝1
            if (nxt<<(m-depth-1)<n) break; // 可行性剪枝2
            if (nxt>n||v[nxt]) continue;   // 排除等效冗余2
            v[nxt] = 1;
            x[depth + 1] = nxt;
            if (dfs(depth + 1)) return 1;
        }
    }
    return 0;
}

int main() {
    x[1] = 1;
    while (scanf("%d", &n), n) {
        for (m = 1; !dfs(1); ++m);
    }
    return 0;
}

Part 4 验证

上面这份代码，不管是 弱化版 NowCoder 还是 加强版 Luogu-UVa，都在 0~5ms 之内输出正确答案。效率已经算是比较高的了。