J-L24 递归与递推¶

覆盖词条：KJ-31b/c/21d ｜先修：J-L11/L09

递归入门¶

递归求和¹¶

递归求和

题目描述

输入一个正整数 $n$，用递归计算 $1 + 2 + \cdots + n$ 的和并输出。

输入格式

一个正整数 $n$。

输出格式

一个整数，为 $1$ 到 $n$ 的和。

样例输入

样例输出

数据范围

$1 \le n \le 1000$

⬇ 点击下载数据包

递归求和 AC 代码

解题思路

递归基本型：$sum(n) = n + sum(n-1)$，边界 $sum(1) = 1$。

AC代码

#include <bits/stdc++.h>
using namespace std;

long long sum(int n) {
    if (n == 1) return 1;                    // 递归边界
    return n + sum(n - 1);
}

int main() {
    int n;
    cin >> n;
    cout << sum(n) << "\n";
    return 0;
}

递归数组求和²¶

递归数组求和

题目描述

输入 $n$ 个整数，用递归计算这 $n$ 个数的和并输出。

输入格式

第一行一个整数 $n$；第二行 $n$ 个整数，用空格分隔。

输出格式

一个整数，为这 $n$ 个数的和。

样例输入

1 2	`5 3 -7 9 -2 9`

样例输出

数据范围

$1 \le n \le 100$，整数绝对值 $\le 10^9$（和可能超出 int 范围，请用 long long）

⬇ 点击下载数据包

递归数组求和 AC 代码

解题思路

递归基本型：前 $i$ 个数的和 $= a_i + $ 前 $i-1$ 个数的和，边界 $sum(0) = 0$。与「递归求和」成对：一个算公式和，一个算任意数组的和。

AC代码

#include <bits/stdc++.h>
using namespace std;

long long a[105];

// 前 i 个数的和 = a[i] + 前 i-1 个数的和
long long sum(int i) {
    if (i == 0) return 0;
    return a[i] + sum(i - 1);
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << sum(n) << endl;
    return 0;
}

计算阶乘³¶

计算阶乘

题目描述

输入一个正整数 $n$，输出 $n! = n \times (n-1) \times \cdots \times 1$。要求用递归函数实现。

输入格式

一个正整数 $n$。

输出格式

一个整数，为 $n!$。

样例输入

样例输出

数据范围

$1 \le n \le 15$（long long 范围内）

计算阶乘 AC 代码

解题思路

递归基本型：$n! = n \times (n-1)!$，边界 $1! = 1$。注意 $n \ge 13$ 时超出 int，用 long long。

AC代码

#include <bits/stdc++.h>
using namespace std;

long long fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);                  // 递归函数基本型
}

int main() {
    int n;
    cin >> n;
    cout << fact(n) << "\n";
    return 0;
}

数位之和⁴¶

数位之和

题目描述

输入一个非负整数 $n$，用递归计算它的十进制各位数字之和并输出。例如 $12345$ 的数位之和为 $1+2+3+4+5 = 15$；$n = 0$ 时数位之和为 $0$。

输入格式

一个非负整数 $n$。

输出格式

一个整数，为 $n$ 的数位之和。

样例输入

样例输出

数据范围

$0 \le n \le 10^{18}$（请用 long long）

⬇ 点击下载数据包

数位之和 AC 代码

解题思路

递归基本型：数位和 $= n \bmod 10 + $ 数位和$(n \div 10)$，边界 $dsum(0) = 0$。与「输出二进制」同一模型——除基取余：一个除 2 输出二进制，一个除 10 累加数位。

AC代码

#include <bits/stdc++.h>
using namespace std;

// 数位和 = 个位 + 剩余部分的数位和
long long dsum(long long n) {
    if (n == 0) return 0;
    return n % 10 + dsum(n / 10);
}

int main() {
    long long n;
    cin >> n;
    cout << dsum(n) << endl;
    return 0;
}

斐波那契数列⁵¶

斐波那契数列

题目描述

斐波那契数列 $f_1 = f_2 = 1$，$f_i = f_{i-1} + f_{i-2}$。输入 $n$，输出 $f_n$。

输入格式

一个正整数 $n$。

输出格式

一个整数，为 $f_n$。

样例输入

样例输出

数据范围

$1 \le n \le 90$

⬇ 点击下载数据包

斐波那契数列 AC 代码

解题思路

递推：$f_i = f_{i-1} + f_{i-2}$，两个变量滚动即可。不要写朴素递归——$f(90)$ 的递归调用次数是天文数字，直接超时；这正是「递归会爆炸、递推才是正解」的第一个例证。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    // 朴素递归在 n=90 时算不完，必须递推
    long long a = 1, b = 1;                  // f(1)=1, f(2)=1
    for (int i = 3; i <= n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    cout << b << "\n";                       // n=1 时 b 也是 1
    return 0;
}

汉诺塔⁶¶

汉诺塔

题目描述

三根柱子 A、B、C，A 柱上从下到上叠着 $n$ 个大小互不相同的盘子（大盘在下）。要把所有盘子移到 C 柱：每次只能移动最顶端的一个盘，且大盘不能压在小盘上，可借助 B 柱。输出每一步移动和总步数。

输入格式

一行一个整数 $n$。

输出格式

每行输出一步移动，格式为 X->Y（表示从柱 X 移到柱 Y）；最后一行输出总步数。

样例输入

样例输出

A->B
A->C
B->C
3

数据范围

$1 \le n \le 10$

⬇ 点击下载数据包

汉诺塔 AC 代码

解题思路

递归分治：要把 $n$ 个盘从 A 移到 C，先把上面 $n-1$ 个盘从 A 借 C 移到 B，再把最大盘 A→C，最后把 $n-1$ 个盘从 B 借 A 移到 C；总步数 $2^n-1$。

AC代码

#include <bits/stdc++.h>
using namespace std;

int cnt = 0;

// 把 n 个盘从 from 柱经 via 柱移到 to 柱
void hanoi(int n, char from, char via, char to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, via);
    cout << from << "->" << to << "\n";
    cnt++;
    hanoi(n - 1, via, from, to);
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    cout << cnt << "\n";
    return 0;
}

赦免战俘⁷¶

赦免战俘

题目描述

有一个 $2^n \times 2^n$ 的矩阵（初始全 0）。不断进行如下操作：把当前矩阵四等分，左上角那一块整块赦免（保持 0），对其余三块重复上述操作，直到划分到单个格子。最后被「处理到」的格子为 1。输出整个矩阵。

输入格式

一个整数 $n$。

输出格式

共 $2^n$ 行，每行 $2^n$ 个数（用空格分隔），为最终矩阵。

样例输入

样例输出

数据范围

$0 \le n \le 10$

赦免战俘 AC 代码

解题思路

递归分治填充：对 $(x, y)$ 处的 $2^k$ 级方块，递归填右上、左下、右下三块（各为 $2^{k-1}$ 级），左上不填（保持 0）；递归到单格时置 1。

AC代码

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> g;                       // 1 = 未被赦免

// 分治：左上象限赦免（保持 0），其余三块递归，到 1×1 才置 1
void solve(int x, int y, int k) {
    if (k == 0) {
        g[x][y] = 1;
        return;
    }
    int half = 1 << (k - 1);
    solve(x, y + half, k - 1);               // 右上
    solve(x + half, y, k - 1);               // 左下
    solve(x + half, y + half, k - 1);        // 右下
    // 左上象限保持 0（赦免），不递归
}

int main() {
    cin >> n;
    int sz = 1 << n;
    g.assign(sz, vector<int>(sz, 0));
    solve(0, 0, n);
    for (int i = 0; i < sz; i++)
        for (int j = 0; j < sz; j++)
            cout << g[i][j] << " \n"[j == sz - 1];
    return 0;
}

递归分解与构造¶

字符串逆序⁸¶

字符串逆序

题目描述

输入一行字符串（可含空格），用递归输出它的逆序。

输入格式

一行字符串，长度不超过 1000。

输出格式

一行，为输入字符串的逆序。

样例输入

1	`hello world`

样例输出

1	`dlrow olleh`

数据范围

字符串长度 $\le 1000$

⬇ 点击下载数据包

字符串逆序 AC 代码

解题思路

递归基本型：先递归逆序打印前 $i-1$ 个字符，再打印第 $i$ 个字符——「先递归后输出」就是倒序。

AC代码

#include <bits/stdc++.h>
using namespace std;

string s;

// 递归：先打印最后一个字符，再倒序打印前 i 个
void rev(int i) {
    if (i < 0) return;
    cout << s[i];
    rev(i - 1);
}

int main() {
    getline(cin, s);
    rev((int)s.size() - 1);
    return 0;
}

递归判断回文⁹¶

递归判断回文

题目描述

输入一个只含小写字母的字符串，用递归判断它是否为回文串（正着读与倒着读完全一样）。是回文串输出 Yes，否则输出 No。

输入格式

一行一个字符串。

输出格式

一行，Yes 或 No。

样例输入

level

样例输出

Yes

数据范围

$1 \le$ 字符串长度 $\le 1000$

⬇ 点击下载数据包

递归判断回文 AC 代码

解题思路

区间收缩型递归：两端字符 $s_l$ 与 $s_r$ 不等则不是回文；相等就递归检查内层 $(l+1, r-1)$；区间缩到空或只剩一个字符即为真。与「字符串逆序」成对：一个倒序输出，一个两端对撞判断。

AC代码

#include <bits/stdc++.h>
using namespace std;

string s;

// 区间 [l, r] 是否回文：两端相等则收缩区间
bool pal(int l, int r) {
    if (l >= r) return true;          // 空串或只剩一个字符
    if (s[l] != s[r]) return false;
    return pal(l + 1, r - 1);
}

int main() {
    cin >> s;
    cout << (pal(0, (int)s.size() - 1) ? "Yes" : "No") << endl;
    return 0;
}

输出二进制¹⁰¶

输出二进制

题目描述

输入一个非负整数 $n$，输出它的二进制表示（不含前导零；$n=0$ 输出 0）。

输入格式

一个非负整数 $n$。

输出格式

$n$ 的二进制表示。

样例输入

样例输出

数据范围

$0 \le n \le 1000$

⬇ 点击下载数据包

输出二进制 AC 代码

解题思路

递归分解：先递归输出 $n/2$ 的二进制（高位），再输出 $n \bmod 2$（本位）——「先递归后输出」天然得到从高位到低位的顺序。

AC代码

#include <bits/stdc++.h>
using namespace std;

// 递归：先输出 n/2 的二进制，再输出本位
void tob(int n) {
    if (n == 0) return;
    tob(n / 2);
    cout << n % 2;
}

int main() {
    int n;
    cin >> n;
    if (n == 0) cout << 0;
    else tob(n);
    return 0;
}

递归求最大值¹¹¶

递归求最大值

题目描述

输入 $n$ 个整数，用递归输出其中的最大值。

输入格式

第一行一个整数 $n$；第二行 $n$ 个整数。

输出格式

一个整数，为最大值。

样例输入

1 2	`5 3 -7 9 -2 9`

样例输出

数据范围

$1 \le n \le 100$，整数绝对值 $\le 10^9$

⬇ 点击下载数据包

递归求最大值 AC 代码

解题思路

递归分治基本型：前 $i$ 个数的最大值 $= \max(a_i, $ 前 $i-1$ 个数的最大值$)$，边界为第一个数本身。

AC代码

#include <bits/stdc++.h>
using namespace std;

int n;
long long a[105];

// 前 i 个数的最大值 = max(a[i], 前 i-1 个的最大值)
long long mx(int i) {
    if (i == 1) return a[1];
    return max(a[i], mx(i - 1));
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << mx(n) << "\n";
    return 0;
}

幂次方¹²¶

幂次方

题目描述

任何一个正整数都可以用 2 的幂次方表示，且约定 $a^b$ 写作 $a(b)$：如 $137 = 2^7+2^3+2^0$ 表示为 2(7)+2(3)+2(0)；进一步 $7=2^2+2+2^0$，所以 137 最终表示为 2(2(2)+2+2(0))+2(2+2(0))+2(0)。给出 $n$，输出它的 0、2 表示（指数部分同样要递归表示；$2^1$ 用 2 表示）。

输入格式

一行一个正整数 $n$。

输出格式

符合约定的表示（无空格）。

样例输入

样例输出

1	`2(2(2)+2+2(0))+2(2+2(0))+2(0)`

数据范围

$1 \le n \le 2 \times 10^4$

幂次方 AC 代码

解题思路

递归分解：从高位到低位扫描 $n$ 的二进制位，第 $k$ 位为 1 就产生一项——$k=1$ 记 2，$k=0$ 记 2(0)，其余记 2(rep(k))（指数递归分解），项间用 + 连接。

AC代码

#include <bits/stdc++.h>
using namespace std;

// n 的 0/2 表示：拆二进制位，指数本身也要递归表示
string rep(int n) {
    if (n == 0) return "0";                  // 只在作为指数时出现：2(0)
    string s;
    for (int k = 31; k >= 0; k--) {          // 从高位到低位拆
        if (!(n >> k & 1)) continue;
        if (!s.empty()) s += "+";
        if (k == 1) s += "2";
        else s += "2(" + rep(k) + ")";
    }
    return s;
}

int main() {
    int n;
    cin >> n;
    cout << rep(n) << "\n";
    return 0;
}

外星密码¹³¶

外星密码

题目描述

外星人对连续若干个相同子串 $\texttt{X}$ 压缩为 [DX]（$D$ 为重复次数，$1 \le D \le 99$），且可以嵌套压缩（如 [2[2CB]]）。给出压缩串，输出解压结果。

输入格式

一行一个字符串，只含数字、大写字母、[ 和 ]。

输出格式

一行，解压后的字符串。

样例输入

1	`ac[3fun]`

样例输出

1	`acfunfunfun`

数据范围

解压后长度 $\le 20000$，最多十重嵌套

外星密码 AC 代码

解题思路

递归解码：逐字符扫描，遇 [ 先读次数 $D$，再递归解码到配对 ]，把结果重复 $D$ 遍拼接——嵌套压缩天然由递归处理。

AC代码

#include <bits/stdc++.h>
using namespace std;

// 解压缩：[DX] → D 份 decode(X)，可嵌套
string decode(const string& s, int& i) {
    string out;
    while (i < (int)s.size() && s[i] != ']') {
        if (s[i] == '[') {
            i++;                              // 跳过 '['
            int d = 0;
            while (isdigit(s[i])) d = d * 10 + (s[i++] - '0');
            string inner = decode(s, i);
            i++;                              // 跳过 ']'
            for (int k = 0; k < d; k++) out += inner;
        } else {
            out += s[i++];
        }
    }
    return out;
}

int main() {
    string s;
    cin >> s;
    int i = 0;
    cout << decode(s, i) << "\n";
    return 0;
}

南蛮图腾¹⁴¶

南蛮图腾

题目描述

按样例输出 $n$ 级的分形图腾（$n=1$ 为一个底宽 4、高 2 的小三角形，之后每级图形由上一级「上方居中一份 + 下方左右两份」构成）。

输入格式

一个正整数 $n$。

输出格式

若干行字符画。

样例输入

样例输出

   /\
  /__\
 /\  /\
/__\/__\

数据范围

$1 \le n \le 10$

南蛮图腾 AC 代码

解题思路

递归画在 $2^n \times 2^{n+1}$ 的字符网格上：$k$ 级图腾 = 上方偏右 $2^{k-1}$ 处画 $k-1$ 级 + 左下、右下各画一份 $k-1$ 级；基础图形是 /\ 与 /__\。输出时去掉行尾空格。

AC代码

#include <bits/stdc++.h>
using namespace std;

int n;
vector<string> g;

// 在 (x, y) 处画 k 级图腾（占 2^k 行、2^(k+1) 列）
void draw(int x, int y, int k) {
    if (k == 1) {                            // 基础图形：塔尖在块内第 1~2 列
        g[y][x + 1] = '/';
        g[y][x + 2] = '\\';
        g[y + 1][x] = '/';
        g[y + 1][x + 1] = '_';
        g[y + 1][x + 2] = '_';
        g[y + 1][x + 3] = '\\';
        return;
    }
    int half = 1 << (k - 1);
    draw(x + half, y, k - 1);                // 上方（居中）
    draw(x, y + half, k - 1);                // 左下
    draw(x + (1 << k), y + half, k - 1);     // 右下
}

int main() {
    cin >> n;
    int height = 1 << n, width = 1 << (n + 1);
    g.assign(height, string(width, ' '));
    draw(0, 0, n);
    for (auto& r : g) {
        while (!r.empty() && r.back() == ' ') r.pop_back();   // 去行尾空格
        cout << r << "\n";
    }
    return 0;
}

Function¹⁵¶

Function

题目描述

定义递归函数 $w(a,b,c)$：

若 $a \le 0$ 或 $b \le 0$ 或 $c \le 0$，返回 1；
若 $a>20$ 或 $b>20$ 或 $c>20$，返回 $w(20,20,20)$；
若 $a<b<c$，返回 $w(a,b,c-1)+w(a-1,b,c-1)-w(a-1,b-1,c-1)$；
其余返回 $w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)$。

多组询问，按格式输出 $w(a,b,c)$ 的值，以 -1 -1 -1 结束。

输入格式

若干行，每行三个整数；最后一行为 -1 -1 -1。

输出格式

每组一行：w(a, b, c) = ans（注意空格）。

样例输入

样例输出

w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576

数据范围

询问数 $1 \le T \le 10^5$，整数在 long long 范围内

Function AC 代码

解题思路

朴素递归大量重复计算会超时——加一个记忆化数组（因为超过 20 会截断到 20，只需 $21^3$ 个格子），算过的直接返回。这就是「朴素递归 vs 记忆化」的分水岭标本。

AC代码

#include <bits/stdc++.h>
using namespace std;

long long memo[21][21][21];
bool seen[21][21][21];

long long w(long long a, long long b, long long c) {
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
    if (seen[a][b][c]) return memo[a][b][c];   // 记忆化：算过直接返回
    seen[a][b][c] = true;
    long long& res = memo[a][b][c];
    if (a < b && b < c)
        res = w(a, b, c - 1) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
    else
        res = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1)
            - w(a - 1, b - 1, c - 1);
    return res;
}

int main() {
    long long a, b, c;
    while (cin >> a >> b >> c) {
        if (a == -1 && b == -1 && c == -1) break;
        cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << "\n";
    }
    return 0;
}

线性递推¶

爬楼梯¹⁶¶

爬楼梯

题目描述

楼梯共 $n$ 阶，每一步可以上 1 阶或 2 阶。从地面走到第 $n$ 阶，共有多少种不同的走法？

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，方案数。

样例输入

样例输出

（三种走法：1+1+1、1+2、2+1。）

数据范围

$1 \le n \le 90$

⬇ 点击下载数据包

爬楼梯 AC 代码

解题思路

递推。设 $f_i$ 为走到第 $i$ 阶的方案数，最后一步要么跨 1 阶、要么跨 2 阶，故 $f_i = f_{i-1} + f_{i-2}$，边界 $f_0 = f_1 = 1$。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    // f[i]：走到第 i 阶的方案数，f[i] = f[i-1] + f[i-2]
    vector<unsigned long long> f(n + 1);
    f[0] = 1;
    if (n >= 1) f[1] = 1;
    for (int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
    cout << f[n] << "\n";
    return 0;
}

铺地砖¹⁷¶

铺地砖

题目描述

有一段 $2 \times n$ 的走廊要铺地砖，手头有足够多的 $1 \times 2$ 地砖（可以竖着用，也可以横着用）。要求恰好铺满整个走廊且地砖互不重叠，共有多少种不同的铺法？

输入格式

一行一个整数 $n$。

输出格式

一个整数，为铺法总数。

样例输入

样例输出

（三种铺法：三列全竖放；左边两枚横放 + 右边一枚竖放；左边一枚竖放 + 右边两枚横放。）

数据范围

$1 \le n \le 90$

⬇ 点击下载数据包

铺地砖 AC 代码

解题思路

递推：看走廊的最后一列——竖放一枚地砖盖住它（剩 $2\times(n-1)$，$f_{n-1}$ 种），或横放两枚盖住最后两列（剩 $2\times(n-2)$，$f_{n-2}$ 种），故 $f_n = f_{n-1} + f_{n-2}$，边界 $f_1 = 1$、$f_2 = 2$。与「爬楼梯」同一模型：换一身外衣的斐波那契递推，专门练「识别递推关系」的眼力。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    // f[1]=1（竖放一列），f[2]=2；第 n 列要么竖放一枚（f[n-1]），要么横放两枚盖住 n-1、n 列（f[n-2]）
    long long f1 = 1, f2 = 2;
    if (n == 1) { cout << 1 << endl; return 0; }
    for (int i = 3; i <= n; i++) {
        long long f = f1 + f2;
        f1 = f2;
        f2 = f;
    }
    cout << f2 << endl;
    return 0;
}

杨辉三角¹⁸¶

杨辉三角

题目描述

输出杨辉三角的前 $n$ 行（第 $i$ 行有 $i$ 个数，行内用空格分隔）。

输入格式

一个正整数 $n$。

输出格式

$n$ 行杨辉三角。

样例输入

样例输出

数据范围

$1 \le n \le 20$

杨辉三角 AC 代码

解题思路

二维递推：$c_{i,j} = c_{i-1,j-1} + c_{i-1,j}$，边界 $c_{i,0} = 1$——杨辉三角就是组合数表。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<long long>> c(n + 1, vector<long long>(n + 1, 0));
    for (int i = 0; i <= n; i++) {
        c[i][0] = 1;                            // 边界：行首为 1
        for (int j = 1; j <= i; j++)
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];   // 杨辉三角递推
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            cout << c[i][j] << " \n"[j == i];
    return 0;
}

猴子吃桃¹⁹¶

猴子吃桃

题目描述

猴子第 1 天摘下若干桃子，当即吃了一半又多吃一个；以后每天早上都吃前一天剩下的一半零一个；到第 $n$ 天早上想再吃时，发现只剩下一个桃子。求第 1 天共摘了多少个桃子。

输入格式

一个正整数 $n$。

输出格式

一个整数，第 1 天摘的桃子数。

样例输入

样例输出

（22 → 10 → 4 → 1。）

数据范围

$1 \le n \le 30$

猴子吃桃 AC 代码

解题思路

反向递推：设第 $d$ 天早上有 $x_d$ 个，吃一半多一个后剩 $x_{d+1} = x_d/2 - 1$，反推 $x_d = 2(x_{d+1}+1)$，从 $x_n = 1$ 往回推 $n-1$ 次（闭式 $x_1 = 3 \cdot 2^{n-1} - 2$ 可对账）。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long x = 1;
    for (int day = 1; day < n; day++)
        x = 2 * (x + 1);                        // 反向递推：前一天 = (当天 + 1) × 2
    cout << x << "\n";
    return 0;
}

车站²⁰¶

车站

题目描述

火车从第 1 站开出时车上有 $a$ 人；第 2 站上下车人数相同，开出时仍是 $a$ 人；从第 3 站起，每站上车人数 = 前两站上车人数之和，下车人数 = 上一站上车人数，直到第 $n-1$ 站。已知终点站（第 $n$ 站）全部下车共 $m$ 人，求火车从第 $x$ 站开出时车上的人数。

输入格式

一行四个整数 $a, n, m, x$。

输出格式

一个整数，为从第 $x$ 站开出时车上的人数。

样例输入

1	`5 7 32 4`

样例输出

数据范围

$1 \le a \le 20$，$1 \le x \le n \le 20$，$1 \le m \le 2 \times 10^4$

车站 AC 代码

解题思路

记第 $i$ 站上车人数 $on_i$：$on_1 = a$，$on_2 = u$（未知），$on_i = on_{i-1} + on_{i-2}$。可推出开离第 $i$ 站时车上人数 $= a + on_i - on_2$；由 $m = a + on_{n-1} - u$ 是关于 $u$ 的一次方程，先解出 $u$，再代入求 $pass_x$。系数随斐波那契式递推同步算出。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a;
    int n, m, x;
    cin >> a >> n >> m >> x;
    if (x == 1 || x == 2 || n == 2) {           // 前 2 站车上恒为 a
        cout << a << "\n";
        return 0;
    }
    // on[1]=a, on[2]=u，on[i]=on[i-1]+on[i-2]（i≥3）
    // 车上人数 pass[i] = a + on[i] - on[2]；由 m = pass[n-1] 反解 u
    long long A = 0, B = 0;                     // on[i] = A*a + B*u
    long long a1 = 1, b1 = 0;                   // on[1]
    long long a2 = 0, b2 = 1;                   // on[2]
    for (int i = 3; i <= n - 1; i++) {
        long long an = a1 + a2, bn = b1 + b2;
        a1 = a2; b1 = b2;
        a2 = an; b2 = bn;
    }
    // m = a + on[n-1] - u = a + a2*a + (b2-1)*u
    long long coefU = b2 - 1;
    long long constPart = a + a2 * a;
    long long u = (m - constPart) / coefU;      // 保证整除
    long long ax = 0, bx = 0;                   // on[x]
    if (x >= 2) {
        long long pa = 1, pb = 0, qa = 0, qb = 1;
        for (int i = 3; i <= x; i++) {
            long long an = pa + qa, bn = pb + qb;
            pa = qa; pb = qb;
            qa = an; qb = bn;
        }
        ax = qa; bx = qb;
    } else {
        ax = 1;
    }
    cout << a + ax * a + bx * u - u << "\n";
    return 0;
}

约瑟夫问题²¹¶

约瑟夫问题

题目描述

$n$ 个人围成一圈，从第 1 个人开始报数，数到 $m$ 的人出列，下一个人重新从 1 开始报数，直到所有人出圈。按顺序输出每个出圈人的编号。

输入格式

一行两个整数 $n, m$。

输出格式

一行 $n$ 个整数，为出圈编号序列。

样例输入

10 3

样例输出

1	`3 6 9 2 7 1 8 5 10 4`

数据范围

$1 \le m, n \le 100$

约瑟夫问题 AC 代码

解题思路

队列模拟（L17）：报数时把队首挪到队尾计数，数到 $m$ 就出列输出——循环圈被「搬尾巴」天然处理。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    queue<int> q;                               // 队列模拟（L17）
    for (int i = 1; i <= n; i++) q.push(i);
    int cnt = 0;
    while (!q.empty()) {
        cnt++;
        if (cnt == m) {                         // 数到 m 出列
            cout << q.front() << " ";
            q.pop();
            cnt = 0;
        } else {
            q.push(q.front());
            q.pop();
        }
    }
    return 0;
}

数的计算²²¶

数的计算

题目描述

按如下规则构造数列：只含一个数 $n$ 的数列合法；在合法数列末尾添加一个不超过末项一半的正整数，得到新的合法数列。求合法数列的总数。

输入格式

一行一个整数 $n$。

输出格式

一个整数，合法数列个数。

样例输入

样例输出

（6；6,1；6,2；6,3；6,2,1；6,3,1。）

数据范围

$1 \le n \le 10^3$

数的计算 AC 代码

解题思路

递归定义改递推：$f_i = 1 + \sum_{j \le i/2} f_j$（每个后继 $j$ 都能接出 $f_j$ 种）。朴素递归在此会超时——这正是「改递推 / 记忆化」的分水岭练习。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    // 朴素递归会爆炸；改递推：f[n] = 1 + f[1] + ... + f[n/2]
    vector<long long> f(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        f[i] = 1;                               // 数列只有 i 本身
        for (int j = 1; j <= i / 2; j++) f[i] += f[j];
    }
    cout << f[n] << "\n";
    return 0;
}

递归与二叉树¶

二叉树深度²³¶

二叉树深度

题目描述

给出一棵二叉树（根为 1 号结点）的 $n$ 行结点信息：每行为「结点编号左儿子编号右儿子编号」（0 表示空）。求这棵树的深度（根的深度为 1）。

输入格式

第一行一个整数 $n$；接下来 $n$ 行，每行三个整数 $x, l, r$。

输出格式

一个整数，为树的深度。

样例输入

样例输出

数据范围

结点编号不超过 1000

二叉树深度 AC 代码

解题思路

递归：子树深度 $= 1 + \max(\text{左深}, \text{右深})$，空结点深度 0——树的最大深度就是从根一路取 max。

AC代码

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> L, R;

int depth(int x) {
    if (!x) return 0;                          // 空结点深度 0
    return 1 + max(depth(L[x]), depth(R[x]));
}

int main() {
    cin >> n;
    L.assign(1001, 0);
    R.assign(1001, 0);
    for (int i = 0; i < n; i++) {
        int x, l, r;
        cin >> x >> l >> r;
        L[x] = l;
        R[x] = r;
    }
    cout << depth(1) << "\n";                  // 根为 1
    return 0;
}

二叉树叶子数²⁴¶

二叉树叶子数

题目描述

给出一棵二叉树（根为 1 号结点）的 $n$ 行结点信息（同二叉树深度的输入格式，0 表示空儿子）。统计这棵树叶子结点（左右儿子都为空）的个数。

输入格式

第一行一个整数 $n$；接下来 $n$ 行，每行三个整数 $x, l, r$。

输出格式

一个整数，为叶子结点个数。

样例输入

样例输出

（叶子为 3、4、5 号结点。）

数据范围

结点编号不超过 1000

⬇ 点击下载数据包

二叉树叶子数 AC 代码

解题思路

递归：空结点贡献 0；左右儿子都空的结点是叶子，贡献 1；否则叶子数 = 左子树叶子数 + 右子树叶子数。

AC代码

#include <bits/stdc++.h>
using namespace std;

vector<int> L, R;

// 叶子 = 左右儿子都为空的结点
int leaf(int x) {
    if (!x) return 0;
    if (!L[x] && !R[x]) return 1;
    return leaf(L[x]) + leaf(R[x]);
}

int main() {
    int n;
    cin >> n;
    L.assign(1001, 0);
    R.assign(1001, 0);
    for (int i = 0; i < n; i++) {
        int x, l, r;
        cin >> x >> l >> r;
        L[x] = l;
        R[x] = r;
    }
    cout << leaf(1) << "\n";                 // 根为 1
    return 0;
}

新二叉树²⁵¶

新二叉树

题目描述

输入一串二叉树（每个结点一行：结点名、左儿子、右儿子，* 表示空；第一行的结点为根），输出其前序遍历。

输入格式

第一行一个整数 $n$（结点数）；接下来 $n$ 行，每行三个字符。

输出格式

二叉树的前序遍历。

样例输入

7
a b c
b d *
c e f
d * g
e * *
f * *
g * *

样例输出

abdgcef

数据范围

$1 \le n \le 26$

新二叉树 AC 代码

解题思路

用结点字符本身作下标存左右儿子（ASCII 数组），第一行确定根后递归先序输出；* 映射为 0 表示空。

AC代码

#include <bits/stdc++.h>
using namespace std;

struct Node {
    char val;
    int l = 0, r = 0;
} t[1005];                                     // 结点为字母，按下标存

void pre(int x) {
    if (!x) return;                            // 0 = 空结点
    cout << t[x].val;
    pre(t[x].l);
    pre(t[x].r);
}

int main() {
    int n;
    cin >> n;
    int root = 0;
    for (int i = 0; i < n; i++) {
        char ch, l, r;
        cin >> ch >> l >> r;                   // 空格分隔的三个字符
        t[ch].val = ch;
        t[ch].l = l == '*' ? 0 : l;
        t[ch].r = r == '*' ? 0 : r;
        if (i == 0) root = ch;                 // 第一行必为根
    }
    pre(root);
    return 0;
}

FBI 树²⁶¶

FBI 树

题目描述

全 0 串称 B 串，全 1 串称 I 串，混合串称 F 串。由长度 $2^N$ 的 01 串构造 FBI 树：根的类型与整串相同；若串长大于 1，从中间分成等长两半，分别递归构造左右子树。输出这棵树的后序遍历。

输入格式

第一行一个整数 $N$；第二行一个长度为 $2^N$ 的 01 串。

输出格式

一个字符串，为后序遍历序列。

样例输入

1 2	`3 10001011`

样例输出

1	`IBFBBBFIBFIIIFF`

数据范围

$0 \le N \le 10$

FBI 树 AC 代码

解题思路

递归处理区间 $[l, r]$：先递归左半、再递归右半、最后统计本段输出类型（后序 = 左右根），递归到单字符直接判型输出。

AC代码

#include <bits/stdc++.h>
using namespace std;

string s;

// 递归处理 [l, r]，输出后序：先左子树、再右子树、最后根
void solve(int l, int r) {
    if (l > r) return;
    if (l == r) {                               // 单字符：直接判型输出
        cout << (s[l] == '0' ? 'B' : 'I');
        return;
    }
    int mid = (l + r) / 2;
    solve(l, mid);                              // 左子树
    solve(mid + 1, r);                          // 右子树
    bool has0 = false, has1 = false;
    for (int i = l; i <= r; i++) {
        if (s[i] == '0') has0 = true;
        else has1 = true;
    }
    cout << (has0 && has1 ? 'F' : (has0 ? 'B' : 'I'));
}

int main() {
    int n;
    cin >> n >> s;
    solve(0, (int)s.size() - 1);
    return 0;
}

美国血统²⁷¶

美国血统

题目描述

给出一棵二叉树（$\le 26$ 个结点）的中序遍历与前序遍历，求后序遍历。

输入格式

共两行：第一行中序遍历，第二行前序遍历。

输出格式

一行，后序遍历。

样例输入

1 2	`ABEDFCHG CBADEFGH`

样例输出

1	`AEFDBHGC`

数据范围

结点数 $\le 26$

美国血统 AC 代码

解题思路

前序的首位是根；在中序中定位根分成左右两段递归，根最后输出（后序 = 左右根）。

AC代码

#include <bits/stdc++.h>
using namespace std;

string in, pre;

// 前序首位是根；在中序中定位根，左右分治，最后输出根（后序顺序）
void build(int il, int ir, int pl, int pr) {
    if (il > ir) return;
    char root = pre[pl];
    int mid = in.find(root, il);
    int leftSize = mid - il;
    build(il, mid - 1, pl + 1, pl + leftSize);
    build(mid + 1, ir, pl + leftSize + 1, pr);
    cout << root;
}

int main() {
    cin >> in >> pre;
    build(0, (int)in.size() - 1, 0, (int)pre.size() - 1);
    return 0;
}

求先序排列²⁸¶

求先序排列

题目描述

给出一棵二叉树（结点为不同的大写字母，结点数 $\le 8$）的中序遍历与后序遍历，求先序遍历。

输入格式

共两行，分别为中序排列与后序排列。

输出格式

一行，先序排列。

样例输入

1 2	`ABEDFCHG AEFDBHGC`

样例输出

1	`CBADEFGH`

数据范围

结点数 $\le 8$

求先序排列 AC 代码

解题思路

后序的末位是根；在中序中定位根，左边是左子树、右边是右子树；先输出根，再对两段递归（前序顺序 = 根左右）。

AC代码

#include <bits/stdc++.h>
using namespace std;

string in, post;

// 后序末位是根；在中序中定位根，左右分治，先输出根（前序顺序）
void build(int il, int ir, int pl, int pr) {
    if (il > ir) return;
    char root = post[pr];                       // 后序最后一个 = 根
    cout << root;
    int mid = in.find(root, il);                // 根在中序中的位置
    int leftSize = mid - il;
    build(il, mid - 1, pl, pl + leftSize - 1);
    build(mid + 1, ir, pl + leftSize, pr - 1);
}

int main() {
    cin >> in >> post;
    build(0, (int)in.size() - 1, 0, (int)post.size() - 1);
    return 0;
}

递推计数¶

走方格²⁹¶

走方格

题目描述

有一个 $m \times n$ 的网格，从左上角出发，每一步只能向右或向下走，走到右下角。共有多少种不同的走法？

输入格式

一行两个正整数 $m, n$。

输出格式

一个整数，为走法总数。

样例输入

2 3

样例输出

数据范围

$1 \le m, n \le 20$

⬇ 点击下载数据包

走方格 AC 代码

解题思路

二维递推：$f_{i,j} = f_{i-1,j} + f_{i,j-1}$（从上方或左方走来），边界第一行、第一列均为 1——这也是 L28 网格 DP 的前奏。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<long long>> f(m + 1, vector<long long>(n + 1, 0));
    for (int i = 1; i <= m; i++) f[i][1] = 1;        // 第一列只有一种走法
    for (int j = 1; j <= n; j++) f[1][j] = 1;        // 第一行只有一种走法
    for (int i = 2; i <= m; i++)
        for (int j = 2; j <= n; j++)
            f[i][j] = f[i - 1][j] + f[i][j - 1];     // 从上方或左方走来
    cout << f[m][n] << "\n";
    return 0;
}

母牛问题³⁰¶

母牛问题

题目描述

农场第 1 年有一头小母牛；小母牛从出生起第 4 年开始，每年年初生一头小母牛；所有母牛都不会死。求第 $n$ 年农场有多少头母牛。

输入格式

一个正整数 $n$。

输出格式

一个整数，为第 $n$ 年的母牛数。

样例输入

样例输出

数据范围

$1 \le n \le 50$

⬇ 点击下载数据包

母牛问题 AC 代码

解题思路

递推：$f_i = f_{i-1} + f_{i-3}$——第 $i$ 年的牛 = 去年的牛 + 今年新出生的牛（新出生数 = 满三年的牛数，即 $f_{i-3}$），边界 $f_1=1, f_2=2, f_3=3$。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    // f[i] = f[i-1] + f[i-3]：第 i 年的牛 = 去年的牛 + 满三年的牛各生一头
    vector<long long> f(n + 1);
    f[1] = 1;
    if (n >= 2) f[2] = 2;
    if (n >= 3) f[3] = 3;
    for (int i = 4; i <= n; i++) f[i] = f[i - 1] + f[i - 3];
    cout << f[n] << "\n";
    return 0;
}

圈圈传球³¹¶

圈圈传球

题目描述

$n$ 个小朋友围成一圈，按顺时针编号 $1 \sim n$（这样每个人都有恰好两个邻居：左邻和右邻）。传球规则：球在谁手中，就传给他左邻或右邻中的任意一人。球从 1 号手中出发，恰好传 $m$ 次后要求回到 1 号手中。两条传球路线只要过程中某一步传给了不同的人，就算不同的路线。求共有多少条传球路线。

输入格式

一行两个整数 $n, m$。

输出格式

一个整数，为传球路线总数。

样例输入

3 2

样例输出

（两条路线：1→2→1 和 1→3→1。）

数据范围

$3 \le n \le 30$，$1 \le m \le 30$

⬇ 点击下载数据包

圈圈传球 AC 代码

解题思路

二维环上递推：设 $f_{t,j}$ 为传 $t$ 次后球在 $j$ 号手中的路线数，球只能从左右两个邻居传来，故 $f_{t,j} = f_{t-1,j-1} + f_{t-1,j+1}$（下标越界按环绕回），边界 $f_{0,1} = 1$，答案 $f_{m,1}$。$n \ge 3$ 时传 1 次不可能回到 1 号（输出 0），是天然的边界检查点。

AC代码

#include <bits/stdc++.h>
using namespace std;

long long f[35][35];   // f[t][j]：传了 t 次后球在 j 号手中的路线数

int main() {
    int n, m;
    cin >> n >> m;
    f[0][1] = 1;
    for (int t = 1; t <= m; t++) {
        for (int j = 1; j <= n; j++) {
            int L = (j == 1) ? n : j - 1;   // 左邻
            int R = (j == n) ? 1 : j + 1;   // 右邻
            f[t][j] = f[t - 1][L] + f[t - 1][R];
        }
    }
    cout << f[m][1] << endl;
    return 0;
}

栈³²¶

栈

题目描述

操作数序列 $1, 2, \ldots, n$ 依次经过一个栈：每个数可以从序列头 push 进栈，也可以从栈顶 pop 到输出序列。问共能得到多少种不同的输出序列。

输入格式

一个整数 $n$。

输出格式

一个整数，为可能的输出序列总数。

样例输入

样例输出

数据范围

$1 \le n \le 18$

栈 AC 代码

解题思路

经典计数：方案数是卡特兰数。设第一个出栈的是第 $i$ 个数，它把序列分成两段独立计数，递推 $C_r = \sum_{i=0}^{r-1} C_i \cdot C_{r-1-i}$，边界 $C_0 = 1$。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    // 卡特兰数递推：C[0]=1, C[i] = Σ C[j]*C[i-1-j]
    vector<long long> c(n + 1, 0);
    c[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            c[i] += c[j] * c[i - 1 - j];
    cout << c[n] << "\n";
    return 0;
}

排队买票³³¶

排队买票

题目描述

演唱会门票每张 1 元，售票处一开始没有任何零钱。$2n$ 个人排队购票，其中 $n$ 人手持一张 1 元纸币，$n$ 人手持一张 2 元纸币；每人只买一张票，持 2 元纸币的人购票时售票员需要找零 1 元。只看队伍中每个人持哪种纸币（持同种纸币的人互换位置不算新方案），问有多少种排队顺序，使得售票全程的任意时刻都不会出现找不出零钱的情况。

输入格式

一个整数 $n$。

输出格式

一个整数，为合法排队顺序数。

样例输入

样例输出

（两种合法顺序：1元 1元 2元 2元；1元 2元 1元 2元。）

数据范围

$1 \le n \le 30$（答案超出 int 范围，请用 long long）

⬇ 点击下载数据包

排队买票 AC 代码

解题思路

合法队列的任意前缀中，持 1 元的人数都不能少于持 2 元的人数（否则找不开零钱）。设 $f_{i,j}$ 为已安排 $i$ 个持 1 元、$j$ 个持 2 元的人的方案数（只在 $i \ge j$ 的状态合法）：队尾来一个持 1 元的有 $f_{i-1,j}$ 种；来一个持 2 元的有 $f_{i,j-1}$ 种。答案 $f_{n,n}$ 恰为卡特兰数——与「栈」的出栈序列计数同一条数列，两题互为镜像。

AC代码

#include <bits/stdc++.h>
using namespace std;

long long f[35][35];   // f[i][j]：已安排 i 个持 1 元、j 个持 2 元的人的合法方案数

int main() {
    int n;
    cin >> n;
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i][0] = 1;                       // 只来持 1 元的，随便排
        for (int j = 1; j <= i; j++) {     // 合法状态必须 i ≥ j（找得开零钱）
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    cout << f[n][n] << endl;
    return 0;
}

信封问题³⁴¶

信封问题

题目描述

$n$ 封信装进 $n$ 个信封，若所有信都装错了信封，共有多少种不同的装法。

输入格式

一个整数 $n$。

输出格式

一个整数，为装错的方式数。

样例输入

样例输出

数据范围

$1 \le n \le 20$

信封问题 AC 代码

解题思路

错排递推：$D_1 = 0$、$D_2 = 1$，$D_i = (i-1)(D_{i-1} + D_{i-2})$——第 $i$ 封信选装进 $i-1$ 个错误信封之一，设装进第 $j$ 个：若 $j$ 号信恰好装进 $i$ 号信封则剩 $D_{i-2}$，否则剩 $D_{i-1}$。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    // 错排递推：D[1]=0, D[2]=1, D[i]=(i-1)(D[i-1]+D[i-2])
    long long d1 = 0, d2 = 1;
    if (n == 1) { cout << 0 << "\n"; return 0; }
    for (int i = 3; i <= n; i++) {
        long long d = (i - 1) * (d2 + d1);
        d1 = d2;
        d2 = d;
    }
    cout << d2 << "\n";
    return 0;
}

本节需要 J-L30 高精度

下面 6 题都是递推的经典好题，但数据范围决定答案必须用高精度表示（高精度在 J-L30 才学）。已学完 L30 的同学可直接练习；尚未学到的可先跳过，学完回填。

数楼梯³⁵¶

数楼梯

题目描述

楼梯有 $N$ 阶，上楼可以一步上一阶，也可以一步上二阶。编一个程序，计算共有多少种不同的走法。

输入格式

一个数字 $N$。

输出格式

输出走的方式总数。

样例输入

样例输出

数据范围

$1 \le N \le 5000$（答案需要高精度）

数楼梯 AC 代码

解题思路

与爬楼梯同一条递推 $f_i = f_{i-1} + f_{i-2}$，但 $N \le 5000$ 时答案是上千位的大数——用高精度加法（十进制数组）实现递推。

AC代码

#include <bits/stdc++.h>
using namespace std;

using Big = vector<int>;                     // 十进制，低位在前

Big add(const Big& a, const Big& b) {
    Big r;
    int carry = 0;
    for (size_t i = 0; i < max(a.size(), b.size()) || carry; i++) {
        int s = carry;
        if (i < a.size()) s += a[i];
        if (i < b.size()) s += b[i];
        r.push_back(s % 10);
        carry = s / 10;
    }
    return r;
}

void print(const Big& a) {
    for (int i = a.size() - 1; i >= 0; i--) cout << a[i];
    cout << "\n";
}

int main() {
    int n;
    cin >> n;
    Big f1 = {1}, f2 = {2};                  // f[1]=1, f[2]=2
    if (n == 1) { print(f1); return 0; }
    for (int i = 3; i <= n; i++) {
        Big f = add(f1, f2);                 // f[i] = f[i-1] + f[i-2]，n 可达 5000
        f1 = f2;
        f2 = f;
    }
    print(f2);
    return 0;
}

蜜蜂路线³⁶¶

蜜蜂路线

题目描述

蜜蜂在数字蜂房上只能从标号小的蜂房爬到标号大的相邻蜂房。求蜜蜂从蜂房 $m$ 爬到蜂房 $n$（$m < n$）有多少种路线。

输入格式

一行两个整数 $m, n$。

输出格式

一个整数，为路线数。

样例输入

1 14

样例输出

数据范围

$1 \le m < n \le 1000$（答案需要高精度）

蜜蜂路线 AC 代码

解题思路

从 $m$ 走到 $n$ 要跨 $n-m$ 段，每步 1 或 2 段——路线数就是斐波那契数 $fib(n-m+1)$，高精度实现（题面 1 14 → fib(14) = 377）。

AC代码

#include <bits/stdc++.h>
using namespace std;

using Big = vector<int>;                     // 十进制，低位在前

Big add(const Big& a, const Big& b) {
    Big r;
    int carry = 0;
    for (size_t i = 0; i < max(a.size(), b.size()) || carry; i++) {
        int s = carry;
        if (i < a.size()) s += a[i];
        if (i < b.size()) s += b[i];
        r.push_back(s % 10);
        carry = s / 10;
    }
    return r;
}

void print(const Big& a) {
    for (int i = a.size() - 1; i >= 0; i--) cout << a[i];
    cout << "\n";
}

int main() {
    int m, n;
    cin >> m >> n;
    int steps = n - m;                       // 走 n-m 段，路线数 = fib(steps+1)
    Big f1 = {1}, f2 = {1};                  // fib(1)=1, fib(2)=1
    for (int i = 3; i <= steps + 1; i++) {
        Big f = add(f1, f2);
        f1 = f2;
        f2 = f;
    }
    print(f2);
    return 0;
}

Hanoi 双塔问题³⁷¶

Hanoi 双塔问题

题目描述

A 柱上放有 $2n$ 个圆盘，共 $n$ 种尺寸、每种两个（不加区分）。把它们移到 C 柱：每次移动一个盘、始终保持上小下大、可借助 B 柱。设最少移动次数为 $A_n$，输出 $A_n$。提示：建立 $A_n$ 与 $A_{n-1}$ 的递推关系。

输入格式

一个正整数 $n$。

输出格式

一个正整数，为 $A_n$。

样例输入

样例输出

数据范围

$1 \le n \le 200$（答案需要高精度）

Hanoi 双塔问题 AC 代码

解题思路

递推：同尺寸双盘使 $A_n = 3A_{n-1} + 2$（先把上面 $2(n-1)$ 个盘挪到 B——两倍的单塔代价，移最大两盘 2 步，再整体盖回来），即 $A_n = 3^n - 1$，高精度实现。

AC代码

#include <bits/stdc++.h>
using namespace std;

using Big = vector<int>;                     // 十进制，低位在前

Big mulSmall(const Big& a, int m) {
    Big r;
    int carry = 0;
    for (size_t i = 0; i < a.size() || carry; i++) {
        long long s = carry;
        if (i < a.size()) s += (long long)a[i] * m;
        r.push_back(s % 10);
        carry = s / 10;
    }
    return r;
}

Big add(const Big& a, const Big& b) {
    Big r;
    int carry = 0;
    for (size_t i = 0; i < max(a.size(), b.size()) || carry; i++) {
        int s = carry;
        if (i < a.size()) s += a[i];
        if (i < b.size()) s += b[i];
        r.push_back(s % 10);
        carry = s / 10;
    }
    return r;
}

void print(const Big& a) {
    for (int i = a.size() - 1; i >= 0; i--) cout << a[i];
    cout << "\n";
}

int main() {
    int n;
    cin >> n;
    // 双塔递推：A_n = 3*A_{n-1} + 2（同尺寸双盘不加区分）
    Big a = {2};                             // A_1 = 2
    for (int i = 2; i <= n; i++) {
        a = mulSmall(a, 3);
        a = add(a, Big({2}));
    }
    print(a);
    return 0;
}

通天之汉诺塔³⁸¶

通天之汉诺塔

题目描述

三根柱子和一根柱上的 $n$ 个圆盘构成汉诺塔。输出把全部圆盘移到另一根柱所需的最少步数 $2^n - 1$。

输入格式

一个数 $n$。

输出格式

一个数 $s$，表示需要 $s$ 步。

样例输入

样例输出

数据范围

$1 \le n \le 15000$（答案需要高精度）

通天之汉诺塔 AC 代码

解题思路

直接输出 $2^n - 1$：十进制数组从 1 开始翻倍 $n$ 次再减 1（最低位必为偶数，减 1 不借位），$n = 15000$ 也能瞬间完成。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    // 2^n - 1 的十进制：用一个「位」数组模拟二进制左移，再整体减 1
    vector<int> bits(n + 1, 0);
    bits[n] = 1;                             // 二进制的 1 后跟 n 个 0 = 2^n
    // 十进制打印 2^n 再减 1：直接在十进制数组上做
    vector<int> d = {1};                     // 十进制低位在前
    for (int i = 0; i < n; i++) {            // 翻倍 n 次
        int carry = 0;
        for (auto& x : d) {
            x = x * 2 + carry;
            carry = x / 10;
            x %= 10;
        }
        while (carry) { d.push_back(carry % 10); carry /= 10; }
    }
    d[0] -= 1;                               // 减 1：最低位必为偶数，不会借位
    for (int i = d.size() - 1; i >= 0; i--) cout << d[i];
    cout << "\n";
    return 0;
}

阶乘之和³⁹¶

阶乘之和

题目描述

用高精度计算出 $S = 1! + 2! + 3! + \cdots + n!$（$n \le 50$）。

输入格式

一个正整数 $n$。

输出格式

一个正整数 $S$，为计算结果。

样例输入

样例输出

（1! + 2! + 3! = 1 + 2 + 6 = 9。）

数据范围

$1 \le n \le 50$（$50! \approx 3 \times 10^{64}$，需要高精度）

阶乘之和 AC 代码

解题思路

两条高精度递推并行：$fact_i = fact_{i-1} \times i$（高精乘小数）与 $sum_i = sum_{i-1} + fact_i$（高精加），最后输出 $sum$。

AC代码

#include <bits/stdc++.h>
using namespace std;

using Big = vector<int>;                     // 十进制，低位在前

Big mulSmall(const Big& a, int m) {
    Big r;
    int carry = 0;
    for (size_t i = 0; i < a.size() || carry; i++) {
        long long s = carry;
        if (i < a.size()) s += (long long)a[i] * m;
        r.push_back(s % 10);
        carry = s / 10;
    }
    return r;
}

Big add(const Big& a, const Big& b) {
    Big r;
    int carry = 0;
    for (size_t i = 0; i < max(a.size(), b.size()) || carry; i++) {
        int s = carry;
        if (i < a.size()) s += a[i];
        if (i < b.size()) s += b[i];
        r.push_back(s % 10);
        carry = s / 10;
    }
    return r;
}

void print(const Big& a) {
    for (int i = a.size() - 1; i >= 0; i--) cout << a[i];
    cout << "\n";
}

int main() {
    int n;
    cin >> n;
    Big fact = {1}, sum = {0};               // fact: i!，sum: 累加和
    for (int i = 1; i <= n; i++) {
        fact = mulSmall(fact, i);            // i! = (i-1)! × i（递推）
        sum = add(sum, fact);
    }
    print(sum);
    return 0;
}

阶乘数码⁴⁰¶

阶乘数码

题目描述

$T$ 组询问：给定 $n$ 和数码 $d$，求 $n!$ 的十进制表示中数码 $d$ 出现的次数。

输入格式

第一行一个整数 $T$；接下来 $T$ 行，每行两个整数 $n, d$。

输出格式

对每组询问输出一行，为数码 $d$ 在 $n!$ 中出现的次数。

样例输入

1
2

1
5 1

样例输出

（5! = 120，含一个数码 1。）

数据范围

$1 \le n \le 1000$，$0 \le d \le 9$（答案需要高精度）

阶乘数码 AC 代码

解题思路

高精度递推阶乘（$fact_i = fact_{i-1} \times i$）到 $n$ 后直接统计十进制数组中等于 $d$ 的位数；多组询问各自独立计算即可。

AC代码

#include <bits/stdc++.h>
using namespace std;

using Big = vector<int>;                     // 十进制，低位在前

Big mulSmall(const Big& a, int m) {
    Big r;
    int carry = 0;
    for (size_t i = 0; i < a.size() || carry; i++) {
        long long s = carry;
        if (i < a.size()) s += (long long)a[i] * m;
        r.push_back(s % 10);
        carry = s / 10;
    }
    return r;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, d;
        cin >> n >> d;
        Big fact = {1};
        for (int i = 2; i <= n; i++) fact = mulSmall(fact, i);
        int cnt = 0;
        for (int x : fact)
            if (x == d) cnt++;
        cout << cnt << "\n";
    }
    return 0;
}

递归入门经典题。 ↩
数组求和 · 经典入门题。 ↩
递归函数 · 洛谷 P5739。 ↩
数位分解 · 经典入门题。 ↩
递推经典题（朴素递归超时对照）。 ↩
递归分治经典题。 ↩
递归分治 · 洛谷 P5461。 ↩
递归入门经典题。 ↩
字符串递归 · 经典入门题。 ↩
递归分解入门题。 ↩
递归分治入门题。 ↩
递归分解 · 洛谷 P1010 · NOIP1998。 ↩
递归解码 · 洛谷 P1928。 ↩
递归分形 · 洛谷 P1498。 ↩
记忆化递归 · 洛谷 P1464。 ↩
线性递推（斐波那契型）。 ↩
递推建模 · 经典模板题。 ↩
二维递推 · 洛谷 P5732。 ↩
反向递推 · 洛谷 P5743。 ↩
递推解方程 · 洛谷 P1011 · NOIP1998。 ↩
队列模拟 / 递推 · 洛谷 P1996。 ↩
递归 → 递推 · 洛谷 P1028 · NOIP2001。 ↩
递归求深度 · 洛谷 P4913。 ↩
递归统计经典题。 ↩
建树 + 先序 · 洛谷 P1305。 ↩
递归建树 · 洛谷 P1087 · NOIP2004。 ↩
递归遍历还原 · 洛谷 P1827 · USACO。 ↩
递归遍历还原 · 洛谷 P1030 · NOIP2001。 ↩
网格递推入门题。 ↩
线性递推经典题。 ↩
环上递推 · 经典模型题。 ↩
卡特兰数递推 · 洛谷 P1044 · NOIP2003。 ↩
卡特兰计数 · 经典模型题。 ↩
错排递推 · 洛谷 P1595。 ↩
递推 + 高精度 · 洛谷 P1255。 ↩
递推 + 高精度 · 洛谷 P2437。 ↩
递推 + 高精度 · 洛谷 P1096 · NOIP2007。 ↩
2^n − 1 高精度 · 洛谷 P1760。 ↩
阶乘和 + 高精度 · 洛谷 P1009 · NOIP1998。 ↩
阶乘数码 + 高精度 · 洛谷 P1591。 ↩

J-L24 递归与递推¶

递归入门¶

递归求和1¶

递归数组求和2¶

计算阶乘3¶

数位之和4¶

斐波那契数列5¶

汉诺塔6¶

赦免战俘7¶

递归分解与构造¶

字符串逆序8¶

递归判断回文9¶

输出二进制10¶

递归求最大值11¶

幂次方12¶

外星密码13¶

南蛮图腾14¶

Function15¶

线性递推¶

爬楼梯16¶

铺地砖17¶

杨辉三角18¶

猴子吃桃19¶

车站20¶

约瑟夫问题21¶

数的计算22¶

递归与二叉树¶

二叉树深度23¶

二叉树叶子数24¶

新二叉树25¶

FBI 树26¶

美国血统27¶

求先序排列28¶

递推计数¶

走方格29¶

母牛问题30¶

圈圈传球31¶

栈32¶

排队买票33¶

信封问题34¶

数楼梯35¶

蜜蜂路线36¶

Hanoi 双塔问题37¶

通天之汉诺塔38¶

阶乘之和39¶

阶乘数码40¶

递归求和¹¶

递归数组求和²¶

计算阶乘³¶

数位之和⁴¶

斐波那契数列⁵¶

汉诺塔⁶¶

赦免战俘⁷¶

字符串逆序⁸¶

递归判断回文⁹¶

输出二进制¹⁰¶

递归求最大值¹¹¶

幂次方¹²¶

外星密码¹³¶

南蛮图腾¹⁴¶

Function¹⁵¶

爬楼梯¹⁶¶

铺地砖¹⁷¶

杨辉三角¹⁸¶

猴子吃桃¹⁹¶

车站²⁰¶

约瑟夫问题²¹¶

数的计算²²¶

二叉树深度²³¶

二叉树叶子数²⁴¶

新二叉树²⁵¶

FBI 树²⁶¶

美国血统²⁷¶

求先序排列²⁸¶

走方格²⁹¶

母牛问题³⁰¶

圈圈传球³¹¶

栈³²¶

排队买票³³¶

信封问题³⁴¶

数楼梯³⁵¶

蜜蜂路线³⁶¶

Hanoi 双塔问题³⁷¶

通天之汉诺塔³⁸¶

阶乘之和³⁹¶

阶乘数码⁴⁰¶