《算法竞赛进阶指南》0x02 递推与递归

递推、递归与分治基础概念

一个实际问题的各种可能情况构成的 集合 称为 “状态空间”，递推和递归 就是程序遍历 状态空间 的两种基本方式。

我们把每个状态看作一个节点，根据递推和递归的法则：

1. 对于 递归 来说，每个 状态节点 都有 唯一 的 父节点（从父节点递归下来的），这些节点就会构成一棵 树
2. 对于 递推 来说，给个 状态节点 都有 多个 父节点（视递推式而定），这些节点就会构成一个 DAG

从 状态空间 的角度来看，递归和递推 实际上就是对一个 状态图/树 的遍历，并求解 问题边界 的行为

如果我们把 同类型 的 状态节点 合并，以 一个节点 代表 一类节点，从而省掉重复的搜索分枝，那个行为就是我们常用的 记忆化搜索 算法

这也是我之前在某篇博客里提到过的，动态规划 作为具有 递推性质 的算法，本质上是在一个 DAG 上找 “问题边界” 的 变换路线

递归 算法中，程序在每个变换步骤中要执行的三个操作：

1. 缩小问题状态空间的规模 程序尝试寻找“原问题”与“问题边界”之间的变换路线，并向正在探索的路线上迈出一步
2. 尝试求解规模缩小以后的问题，结果可能成功，也可能失败
3. 结果
   1. 如果成功，即找到了规模缩小后的问题的答案，那么将问题扩展到当前问题
   2. 如果失败，那么重新回到当前问题，程序可能会继续寻找当前问题的其他变换路线，直至最终确定当前问题无法求解

上述三个操作中有亮点颇为关键，一是 “如何尝试求解规模缩小以后的问题”。由于问题规模缩小为原问题的一个子问题，因此可以把它视为一个新的“原问题”，并由相同的程序进行求解，也就形成了“自身调用自身”的递归。二是求解子问题失败后，程序需要回到当前问题并去寻找其他的变换路线，因此把当前问题缩小为子问题时所做的对当前问题状态 产生影响的事情应该全部失效，这就是所谓的“回溯时还原现场”。

分治法 则是把一个问题划分为若干个规模更小的同类子问题，对这些子问题递归求解，然后在回溯时通过它们推导出原问题的解

常见的枚举形式和遍历方式

枚举形式	状态空间规模	一般遍历方式
多项式	(n^k)，(k) 为常数	循环(for)、递推
指数	(k^n)，(k) 为常数	递归、位运算
排列	(n!)	递归、C next_permutation
组合	(C_n^m)	递归 剪枝

n^k

，

k

为常数 循环(for)、递推 指数

k^n

，

k

为常数 递归、位运算 排列

n!

递归、C next_permutation 组合

C_n^m

递归 剪枝

习题

递归实现指数型枚举

题目描述

从

1∼n

这

n

个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数

n

。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好

1

个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1≤n≤15

输入样例：

代码语言：javascript复制

3

输出样例：

代码语言：javascript复制

3
2
2 3
1
1 3
1 2
1 2 3

解析

代码语言：javascript复制

vector<int> chosen;
void calc(int x)
{
    if (x == n   1)
    {
        for (int i = 0; i < chosen.size(); i    )
            printf("%d ", chosen[i]);
        puts("");
        return;
    }
    calc(x   1);
    chosen.push_back(x);
    calc(x   1);
    chosen.pop_back();
}
int main()
{
    scanf("%d", &n);
    calc(1);
    return 0;
}

递归实现组合型枚举

题目描述

从

1∼n

这

n

个整数中随机选出

m

个，输出所有可能的选择方案。

输入格式

两个整数

n,m

,在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行

1

个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围

n>0

,

0≤m≤n

,

n (n−m)≤25

输入样例：

代码语言：javascript复制

5 3

输出样例：

代码语言：javascript复制

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

解析

代码语言：javascript复制

void calc(int u)
{
    if (chosen.size() > m || chosen.size()   (n - u   1) < m) return;
    // 除了上面一步剪枝，剩余部分同上一题一摸一样
    ...
}

递归实现排列型枚举

题目描述

把

1∼n

这

n

个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数

n

。

输出格式

按照从小到大的顺序输出所有方案，每行

1

个。

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

1≤n≤9

输入样例：

代码语言：javascript复制

3

输出样例：

代码语言：javascript复制

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

解析

代码语言：javascript复制

int order[20];
bool chosen[20];
void calc(int u)
{
    if (u == n   1)
    {
        for (int i = 1; i <= n; i    )
            printf("%d ", order[i]);
        puts("");
        return;
    }
    for (int i = 1; i <= n; i    )
    {
        if (chosen[i]) continue;
        chosen[i] = true;
        order[u] = i;
        calc(u   1);
        order[u] = 0;
        chosen[i] = false;
    }
}

费解的开关

题目描述

你玩过“拉灯”游戏吗？

25

盏灯排成一个

5×5

的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字

1

表示一盏开着的灯，用数字

0

表示关着的灯。

下面这种状态

代码语言：javascript复制

10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成：

代码语言：javascript复制

01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成：

代码语言：javascript复制

01111
11001
11001
10100
11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在

6

步以内使所有的灯都变亮。

输入格式

第一行输入正整数

n

，代表数据中共有

n

个待解决的游戏初始状态。

以下若干行数据分为

n

组，每组数据有

5

行，每行

5

个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

一共输出

n

行数据，每行有一个小于等于

6

的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若

6

步以内无法使所有灯变亮，则输出

−1

。

数据范围

0<n≤500

输入样例：

代码语言：javascript复制

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例：

代码语言：javascript复制

3
2
-1

解析

易发现三个简单性质：

1. 每个位置至多只会被点击一次
2. 若固定了第一行，则满足题意的点击方案至多只有 1 种 当第 i 行某一位为 1 时，若前 i 行已被固定，只能点击第 i 1 行该位置上的数字才能使第 i 行的这一位变成 0 从上到下使用归纳法可得上述结论
3. 点击的先后顺序不影响最终结果

根据上述性质而生的枚举策略：先确定第一行的状态，共

2^5=32

种可能

然后根据第 i 行确定的状态，递推出第 i 1 行的方案

最后检查最后一行的状态是否合法，即可确定该方案是否合法

代码语言：javascript复制

int dx[5] = {0, -1, 0, 1, 0};
int dy[5] = {0, 0, 1, 0, -1};
char g[N][N], b[N][N];
void turn(int i, int j)
{
    for (int d = 0; d < 5; d    )
    {
        int x = i   dx[d], y = j   dy[d];
        if (x < 0 || x >= n || y < 0 || y >= n) continue;
        g[x][y] ^= 1;
    }
}
void solve()
{
    for (int i = 0; i < n; i    ) cin >> b[i];
    int res = -1;
    for (int op = 0, cnt; cnt = 0, op < 1 << n; op    )
    {
        memcpy(g, b, sizeof g);
        for (int i = 0; i < n; i    )
            if (op >> i & 1)
                turn(0, i), cnt    ;
        for (int i = 1; i < n; i    )
            for (int j = 0; j < n; j    )
                if (g[i - 1][j] == '0')
                    turn(i, j), cnt    ;
        if (cnt > 6) continue;
        bool flag = true;
        for (int i = 0; i < n; i    )
            if (g[n - 1][i] == '0')
                flag = false;
        if (flag && (res == -1 || res > cnt))
            res = cnt;
    }
    cout << res << endl;
}

奇怪的汉诺塔

题目描述

汉诺塔问题，条件如下：

1. 这里有 A、B、C 和 D 四座塔。
2. 这里有

n

个圆盘，

n

的数量是恒定的。

1. 每个圆盘的尺寸都不相同。
2. 所有的圆盘在开始时都堆叠在塔 A 上，且圆盘尺寸从塔顶到塔底逐渐增大。
3. 我们需要将所有的圆盘都从塔 A 转移到塔 D 上。
4. 每次可以移动一个圆盘，当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时，可将圆盘移至这座塔上。

请你求出将所有圆盘从塔 A 移动到塔 D，所需的最小移动次数是多少。

输入格式

没有输入

输出格式

对于每一个整数

n

，输出一个满足条件的最小移动次数，每个结果占一行。

数据范围

1≤n≤12

解析

易知 3 根柱子的情况下，汉诺塔的递推公式为：

[ d[n] = 2 * d[n - 1] - 1 ]

即考虑最后一步：

1. 先把

n-1

个盘子用 B、C 两柱 轮流操作，从 A柱 移到 B柱

1. 再把最下面最大的底盘从 A柱 移到 C柱
2. 最后将 B柱 剩余部分用A、C 两柱 轮流操作，从 B柱 移到 C柱

接着我们用 3柱 情况推导 4柱 情况

1. 先把

i

个盘子用 B、C、D 三柱 轮流操作，从 A柱 移到 B柱

1. 再把

n - i - 1

个盘子用 C、D 两柱 轮流操作，从 A柱 移到 C柱

1. 然后把最下面最大的底盘从 A柱 移到 D柱
2. 接着用 A、D 两柱 轮流操作，把 C柱 上

n - i - 1

个盘子从 C柱 移到 D柱

1. 最后用 A、C、D 三柱 轮流操作，把 B柱 上

i

个盘子从 B柱 移到 D柱

有递推式：

[ f[n] = min {2 * (f[i] d[n - i - 1]) 1} = min {2 * f[i] d[n - i]} ]

根据上述推导，继续套循环递推，可以解时间允许条件下的任意

n

柱

m

盘的问题

代码语言：javascript复制

int f[15], d[15];
int main()
{
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int n = 1; n <= 12; n    )
    {
        d[n] = 2 * d[n - 1]   1;
        for (int i = 0; i < n; i    )
            f[n] = min(f[n], 2 * f[i]   d[n - i]);
        cout << f[n] << endl;
    }
    return 0;
}

约数之和

题目描述

假设现在有两个自然数

A

和

B

，

S

是

A^B

的所有约数之和

请你求出

S bmod 9901

的值

输入格式

在一行中输入用空格隔开的两个整数

A

和

B

输出格式

输出一个整数，代表

S bmod 9901

的值

数据范围

0≤A,B≤5×10^7

输入样例：

代码语言：javascript复制

2 3

输出样例：

代码语言：javascript复制

15

注意:

A

和

B

不会同时为

0

解析

考虑直接模拟，有

A = p_1^{c_1} cdot p_2^{c_2} cdots p_n^{c_n}

，由此易得

A^B = p_1^{Bc_1} cdot p_2^{Bc_2} cdots p_n^{Bc_n}

由乘法分配律，易得

A^B

的所有约数之和为：

[ S = (1 p_1 cdot p_{1}^{Bc_1}) cdot (1 p_2 cdot p_{2}^{Bc_2}) cdots (1 p_n cdot p_{n}^{Bc_n}) ]

如果直接模拟这个过程，根据公式去求解

S

，直接迭代求，显然复杂度会爆掉

易想到的一个优化是对每一个括号用等比数列求和公式，但是公式中有除法，在模运算下做等效除法需要求逆元

不过本题的模数

9901

是质数，可以用 费马小定理 结合 快速幂 求逆元，否则就要用 BSGS 了

不妨换一种思路考虑本题，采用 分治 的思想来求解

mathrm{sum}(p, c) = 1 p cdots p^c

，不妨设

c

为奇数，则

[ begin{aligned} mathrm{sum}(p, c 1) &= mathrm{sum}(p, c) p^{c 1} \\ mathrm{sum}(p, c) &= (1 cdots p^{frac{c-1}{2}}) (p^{frac{c 1}{2}} cdots p^c) \\ &= mathrm{sum}(p, frac{c-1}{2}) p^{frac{c 1}{2}} cdot mathrm{sum}(p, frac{c-1}{2}) \\ &= mathrm{sum}(p, frac{c-1}{2}) cdot (1 p^{frac{c 1}{2}}) end{aligned} ]

状态空间 的 问题边界 为

mathrm{sum}(p, 0) = 1

利用该分治思想，求解本问题

代码语言：javascript复制

int calc(int p, int c)
{
    if (!c) return 1;
    if (c & 1) return (calc(p, c / 2) * (power(p, (c   1) / 2) % mod   1)) % mod;
    return (power(p, c)   calc(p, c - 1)) % mod;
}

分形之城

题目描述

城市的规划在城市建设中是个大问题。

不幸的是，很多城市在开始建设的时候并没有很好的规划，城市规模扩大之后规划不合理的问题就开始显现。

而这座名为 Fractal 的城市设想了这样的一个规划方案，如下图所示：

当城区规模扩大之后，Fractal 的解决方案是把和原来城区结构一样的区域按照图中的方式建设在城市周围，提升城市的等级。

对于任意等级的城市，我们把正方形街区从左上角开始按照道路标号。

虽然这个方案很烂，Fractal 规划部门的人员还是想知道，如果城市发展到了等级

N

，编号为

A

和

B

的两个街区的直线距离是多少。

街区的距离指的是街区的中心点之间的距离，每个街区都是边长为

10

米的正方形。

输入格式

第一行输入正整数

n

，表示测试数据的数目。

以下

n

行，输入

n

组测试数据，每组一行。

每组数据包括三个整数

N

,

A

,

B

，表示城市等级以及两个街区的编号，整数之间用空格隔开。

输出格式

一共输出

n

行数据，每行对应一组测试数据的输出结果，结果四舍五入到整数。

数据范围

1≤N≤31

,

1≤A,B≤2^{2N}

,

1≤n≤1000

输入样例：

代码语言：javascript复制

3 
1 1 2 
2 16 1 
3 4 33 

输出样例：

代码语言：javascript复制

10 
30 
50 

解析

显然，

n

级城市由四座

n-1

级城市组成，其中左上的

n-1

级城市顺时针旋转了90度再左右翻转，左下的

n-1

级城市逆时针旋转了90度再左右翻转，其余两座

n-1

级城市没有发生变化。

因此，在求解

mathrm{calc}(n, m)

时，因为

n-1

级城市有

2^{2n-2}

座房屋

所以可以先递归求解

mathrm{calc}(n-1, n bmod 2^{2n-2})

，找出在

n-1

级城市中，目标的位置

记为

(x,y)

再根据

m

推断出目标所在的

n-1

级城市的编号，并根据该编号对

(x,y)

进行坐标变换

四个编号的具体变换：(从0开始编号，

n-1

级城市边长为

2^{n-1}

)

1. 处于左上角的

n-1

级城市

1. 顺时针旋转90度，坐标变为：

(y, 2^{n-1} - x - 1)

1. 左右翻转，坐标变为：

(y, x)

1. 绝对位置上不用移动，坐标变为：

(y,x)

1. 处于右上角的

n-1

级城市

1. 绝对位置上向右移一个

n-1

级城市单位，坐标变为：

(x, y 2^{n-1})

1. 处于右下角的

n-1

级城市

1. 绝对位置上向右下移一个

n-1

级城市单位，坐标变为：

(x 2^{n-1}, y 2^{n-1})

1. 处于左下角的

n-1

级城市

1. 逆时针旋转90度，坐标变为：

(2^{n-1} - 1 - y, x)

1. 左右翻转，坐标变为：

(2^{n-1} - 1 - y, 2^{n-1} - 1 - x)

1. 绝对位置上向下移一个

n-1

级城市单位，坐标变为：

(2^{n} - 1 - y, 2^{n-1} - 1 - x)

代码语言：javascript复制

pair<long long, long long> calc(int n, long long m)
{
    if (!n) return {0, 0};
    long long len = 1ll << (n - 1), cnt = 1ll << (2 * n - 2);
    pair<long long, long long> pos = calc(n - 1, m % cnt);
    long long x = pos.x, y = pos.y;
    long long z = m / cnt;
    if (z == 0) return {y, x};
    if (z == 1) return {x, y   len};
    if (z == 2) return {x   len, y   len};
    if (z == 3) return {2 * len - 1 - y, len - 1 - x};
}

编程算法 游戏

0 人点赞