[蓝桥杯 2023 省 A] 填空问题

形式化题目

本题的输入只有一个字符 A 或 B，要求分别回答两个互相独立的小问。

A. 幸运数：称一个正整数是幸运数，若它的十进制位数 $2h$ 为偶数，且把它的十进制表示从中点切开后，前 $h$ 位的数位和等于后 $h$ 位的数位和。求区间 $[1, 10^8]$ 内幸运数的个数。

B. 有奖问答：一次答题共 $30$ 道题，每道题只有答对、答错两种结果。规则是：

答对得 $10$ 分，答错则分数清零；
小蓝可以在任意时刻结束答题并领取当前分数对应的奖项；
分数到达 $100$ 分时他必然立刻停止（也就是连续答对 $10$ 道题后就结束了）；
他最终实际领取的是 $70$ 分对应的奖项。

求满足上述条件的答题情况数。

暴力解法

思路

两道小题的数据规模都不大，先把“按定义直接数”的做法写出来，作为理解题意和校验正解的基线。

A 题：枚举 $1 \sim 10^8$ 的每个整数，把它的十进制位拆到数组里。若位数为奇数，直接跳过；否则把后一半与前一半分别求和，相等就计入答案。整个过程没有任何数学化简，纯粹照定义翻译。

B 题：把答题过程看成一棵二叉树，每个节点是状态「已经答了 $t$ 题、当前分数为 $score$ 」，向下有两种选择：

这一题答错：转移到 $(t+1, 0)$ ，分数归零；
这一题答对：转移到 $(t+1, score+10)$ ，但如果 $score+10 = 100$ ，说明他必须在这里停止，不能再继续向下扩展。

每当走到一个 $score = 70$ 的状态，对应“已答完这些题、此刻正好 $70$ 分”的一种情况，可以让小蓝在这里结束答题，因此累加 $1$ ；之后再继续枚举他“不在这里停、继续答”的所有分支。同一个状态 $(t, score)$ 会被大量重复访问，用记忆化数组保证每个状态只展开一次。

这两个暴力解都写在 brute.cpp 里，只用来做小规模理解和互相对拍，不是正解。

代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105/**
 * 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-02 15:07
 * update_at: 2026-10-03 11:23
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// A 题：直接枚举 1 ~ 100000000 的每个数，数位求和后比较前后两半，不做任何数学优化。
// B 题：把答题过程看成一次搜索，状态是（已答题数, 当前分数），
//       每层在这一题上做“答对 / 答错”的选择，遇到 70 分就把“此刻停止答题”计入答案。
// 它与 main.cpp 的状态定义完全不同（main 用的是“末尾连续答对数”），
// 因此是一份独立的校验实现；规模只够用来对拍和理解，不适合当作正解。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int ALL_Q = 30;            // B 题总题数
const int MAX_SCORE = 90;        // 分数只能是 10 的倍数，且 100 分时立即停止
const int WANT_SCORE = 70;       // 最终实际获得的 70 分
const int A_LIMIT = 100000000;   // A 题题面上界

int digit[16];                   // digit[1..len]：当前枚举到的数的各位数字

// A 题暴力：把 x 拆位，位数必须是偶数，且前后两半的数位和相等。
bool is_lucky(int x) {
    int len = 0;
    int y = x;
    while (y > 0) {
        len++;
        digit[len] = y % 10;
        y /= 10;
    }
    if (len % 2 != 0) {
        return false;
    }
    int half = len / 2;
    int front = 0;
    int back = 0;
    for (int i = len; i > half; i--) { // digit[len]..digit[half+1] 是高位那一半
        front += digit[i];
    }
    for (int i = half; i >= 1; i--) {  // digit[half]..digit[1] 是低位那一半
        back += digit[i];
    }
    return front == back;
}

ll solve_a_brute() {
    ll cnt = 0;
    for (int x = 1; x <= A_LIMIT; x++) {
        if (is_lucky(x)) {
            cnt++;
        }
    }
    return cnt;
}

ll memo[ALL_Q + 1][MAX_SCORE + 1];  // 记忆化：同一个（已答题数, 当前分数）只算一次
bool visited[ALL_Q + 1][MAX_SCORE + 1];

// 当前已经答了 t 题、手上分数是 score，返回还能产生多少种“以 70 分结束”的答题情况。
// 到达某个状态时分数一定小于 100，否则早就在 100 分处停止、不会继续答题。
ll dfs_answer(int t, int score) {
    if (visited[t][score]) {
        return memo[t][score];
    }
    visited[t][score] = true;

    ll res = 0;
    if (score == WANT_SCORE) {
        res += 1;                       // 此刻正好 70 分，小蓝可以选择在这里结束答题
    }
    if (t < ALL_Q) {
        res += dfs_answer(t + 1, 0);    // 这一题答错：分数直接归零
        if (score + 10 <= MAX_SCORE) {  // 这一题答对：拿到 100 分就必须停止，不能再往后展开
            res += dfs_answer(t + 1, score + 10);
        }
    }
    memo[t][score] = res;
    return res;
}

ll solve_b_brute() {
    memset(visited, 0, sizeof(visited));
    memset(memo, 0, sizeof(memo));
    return dfs_answer(0, 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    char pid;
    if (!(cin >> pid)) {
        return 0;
    }
    if (pid == 'A') {
        cout << solve_a_brute() << "\n";
    } else {
        cout << solve_b_brute() << "\n";
    }
    return 0;
}

复杂度

A 题枚举 $10^8$ 个数、每个数拆 $8$ 位，约 $8 \times 10^8$ 次基本操作，本机实测约 $1$ 秒，已经贴着可接受上限；B 题状态数是 $31 \times 10$ ，每个状态只扩展两个分支，是常数时间。

瓶颈

A 题的瓶颈是 $10^8$ 次枚举本身：它对每个数都要做一次拆位和两次求和，重复计算了大量结构相同的前缀。B 题的瓶颈则是“状态”选得不好：以具体分数为状态时无法直接看到“什么时候是 $70$ 分、什么时候会到 $100$ 分”这件事与末尾连续答对题数的对应关系，转移分支和停止条件混在一起，难以进一步压缩。

正解

思路

A 题：把“枚举数”换成“枚举数位和”。

幸运数由两部分拼成：前 $h$ 位和后 $h$ 位。设后半部分的数位和为 $s$ ，那么前半部分的数位和也必须是 $s$ ，而两个半部分的取值互不影响，因此可以直接相乘求和：

\text{ans}_A = \sum_{h=1}^{4} \sum_{s} f(h, s) \cdot g(h, s)

其中：

$f(h, s)$ 表示长度恰为 $h$ 、首位不为 $0$ 的数字中数位和为 $s$ 的个数；
$g(h, s)$ 表示长度恰为 $h$ 、允许首位为 $0$ 的 $0$ 填充串中数位和为 $s$ 的个数。

$h$ 只取 $1\sim 4$ ，因为 $10^8$ 以内的偶数位数最多 $8$ 位。两个量都可以用一次简单的“数位和背包”求出：设 $W(h, s)$ 表示 $h$ 位（允许前导 $0$ ）数位和为 $s$ 的个数，则

W(0, 0) = 1,\qquad W(h, s) = \sum_{d=0}^{9} W(h-1, s-d)

于是 $g(h, s) = W(h, s)$ ；而 $f(h, s)$ 就是 $W(h, s)$ 中首位非 $0$ 的那部分，即

f(h, s) = W(h, s) - W(h-1, s)

减掉的正是“首位取 $0$ 、剩下 $h-1$ 位任意”的方案数。这样 A 题只需 $4 \times 37 \times 10$ 级别的运算，和 $10^8$ 无关。

B 题：把“分数”换成“末尾连续答对了几题”。

关键观察是：分数完全由「末尾连续答对题数」 $r$ 决定， $score = 10r$ 。所以 $70$ 分等价于 $r = 7$ ， $100$ 分等价于 $r = 10$ ，而“答错”就是把 $r$ 清零。于是所有信息都被压缩进 $r \in [0, 9]$ 。

定义 $dp_t[r]$ ：已经答完了 $t$ 道题、末尾恰好连续答对 $r$ 道题、且中途从未达到 $100$ 分（即从未出现 $r = 10$ ）的情况数。初始 $dp_0[0] = 1$ 。

转移就是“第 $t+1$ 题答对还是答错”：

dp_{t+1}[0] = \sum_{r=0}^{9} dp_t[r], \qquad dp_{t+1}[r+1] \mathrel{+}= dp_t[r] \quad (0 \leqslant r \leqslant 8)

答错时无论原来连续对了多少题都会清零，所以所有状态都汇总到 $r=0$ ；答对时连续数加一， $r \leqslant 8$ 才能转移，因为 $r = 9$ 再答对就变成 $100$ 分、小蓝必须停止，不能再计入“答完 $t+1$ 题”。

每一层的 $dp_t[7]$ 都表示“答完 $t$ 题后正好停在 $70$ 分”的情况数，它们都要计入答案（小蓝可以在第 $t$ 题结束时选择结束答题），所以

\text{ans}_B = \sum_{t=1}^{30} dp_t[7]

以长度 $t$ 较小的情况为例， $dp$ 的形态如下（每行是这一层的 $dp_t[0..9]$ ，只列出非零项）：

$t$	$dp_t[0]$	$dp_t[1]$	$dp_t[2]$	$dp_t[3]$	$dp_t[7]$	本层贡献
0	1	0	0	0	0	0
1	1	1	0	0	0	0
2	2	1	1	0	0	0
3	4	2	1	1	0	0
4	8	4	2	1	0	0
7	64	32	16	8	1	1

可以看到：连续答对数 $r$ 每增加一层最多加一，所以 $r = 7$ 的第一层一定是 $t = 7$ （也就是“七题全对”），此后随着答错清零、重新积累， $dp_t[7]$ 不断变大，把 $t = 7 \sim 30$ 的贡献加起来就得到 B 题答案。

代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99/**
 * 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-02 15:07
 * update_at: 2026-10-03 11:23
 */
// main.cpp：P9230 [蓝桥杯 2023 省 A] 填空问题 的正式提交程序。
// A 题：位数最多 8 位，统计前后半部分数位和相等的数 —— 按“半长 + 数位和”计数相乘。
// B 题：一共 30 题，统计最终得 70 分（连续答对 7 题）的答题情况数 —— 按“末尾连续答对数”分层递推。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int HALF = 4;          // 1e8 以内偶数位数最多 8 位，所以前/后半部分最多 4 位
const int MAX_SUM = 36;      // 4 位数字的最大数位和是 9*4 = 36
const int MAX_Q = 30;        // 答题总数为 30
const int BRUTE_RUN = 10;    // 连续答对 10 题就是 100 分，到达时立刻停止
const int WANT_RUN = 7;      // 70 分对应的连续答对数

// ways[h][s]：h 位数字（允许前导 0）中数位和为 s 的个数
ll ways[HALF + 1][MAX_SUM + 1];

// 预处理每一位自由取 0~9 的数位和方案数，相当于做 h 次“数位和”背包。
void build_digit_ways() {
    ways[0][0] = 1;
    for (int h = 1; h <= HALF; h++) {
        for (int s = 0; s <= 9 * HALF; s++) {
            ll total = 0;
            for (int d = 0; d <= 9; d++) {
                if (s - d >= 0) {
                    total += ways[h - 1][s - d];
                }
            }
            ways[h][s] = total;
        }
    }
}

// A 题答案：长度为 2h 的数，前 h 位的数位和 == 后 h 位的数位和。
// 后半部分允许前导 0（就是普通的 h 位串），前半部分首位不能是 0。
ll solve_a() {
    build_digit_ways();
    ll ans = 0;
    for (int h = 1; h <= HALF; h++) {
        for (int s = 0; s <= 9 * h; s++) {
            // 前半部分首位不能是 0：先随便填 h 位，再减掉首位为 0 的 h-1 位方案
            ll front = ways[h][s] - ways[h - 1][s];
            ans += front * ways[h][s];
        }
    }
    return ans;
}

// dp[r]：在当前枚举到的长度下，以“末尾恰好连续答对 r 题”结尾、
// 并且中途从未到达 100 分（即从未连续答对 10 题）的答题序列数。
ll dp[BRUTE_RUN + 1];

// B 题答案：对每个长度 t，恰好结束在 70 分（末尾连续答对 7 题）的序列都要计入。
ll solve_b() {
    ll ans = 0;
    dp[0] = 1;
    for (int t = 1; t <= MAX_Q; t++) {
        ll ndp[BRUTE_RUN + 1];
        for (int r = 0; r <= BRUTE_RUN; r++) {
            ndp[r] = 0;
        }
        ll all = 0;                       // 所有长度 t-1 的合法序列，下一题答错后都落到 r = 0
        for (int r = 0; r <= BRUTE_RUN; r++) {
            all += dp[r];
        }
        ndp[0] = all;
        for (int r = 0; r + 1 < BRUTE_RUN; r++) {
            ndp[r + 1] += dp[r];          // 下一题答对，连续答对数加一；到 10 就已经是 100 分，不再延伸
        }
        for (int r = 0; r <= BRUTE_RUN; r++) {
            dp[r] = ndp[r];
        }
        ans += dp[WANT_RUN];
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    char pid;
    if (!(cin >> pid)) {
        return 0;
    }
    if (pid == 'A') {
        cout << solve_a() << "\n";
    } else {
        cout << solve_b() << "\n";
    }
    return 0;
}

复杂度

设 A 题最大位数 $H = 4$ 。预处理 $W$ 的复杂度为 $O(H \cdot 9H \cdot 10) = O(H^2)$ 级别常数；统计答案为 $O(H \cdot 9H)$ 。B 题每层只枚举 $10$ 个状态，共 $30$ 层，复杂度 $O(30 \times 10)$ 。两者都是 $O(1)$ 规模的常数级计算，与 $10^8$ 枚举相比可以忽略，占用内存是几个几十大小的数组。

总结

这道题的两问看起来毫不相干，但拆开后是同一个思路的两个实例：先找出真正决定答案的那一个量，再把枚举对象换成它。

A 题的答案是「前 $h$ 位数位和 = 后 $h$ 位数位和」的方案数。前一半与后一半互不干扰，于是可以先各自统计“数位和为 $s$ 的 $h$ 位数有多少个”（一次数位和背包），再对同一个 $s$ 做乘法合并。核心是意识到 $h \leqslant 4$ ，数位和最多 $36$ ，状态空间只有几百个，枚举数位和自然远快于枚举数。注意两个半部分边界不同：前半部分首位不能为 $0$ （用 $W(h,s) - W(h-1,s)$ 扣掉首位为 $0$ 的情况），后半部分允许有前导 $0$ 。
B 题的答案是「结束时正好 $70$ 分」的方案数。分数完全由末尾连续答对题数决定，所以状态不需要记录具体分数，只需记录 $r \in [0, 9]$ ；答错即 $r \to 0$ ，答对即 $r \to r+1$ ，且 $r$ 永远不能到 $10$ （那是 $100$ 分、必须停止）。这样一条 $O(31 \times 10)$ 的线性递推就能求出所有长度上停在 $70$ 分的方案数。

本题的输入只有一个字符，答案固定为 $4430091$ 和 $8335366$ ，但把两问当作真正的计数问题去推导，才是这道填空题的训练价值。brute.cpp 中保留了两份独立实现（枚举 $1 \sim 10^8$ 与以分数为状态的记忆化搜索），可以与 main.cpp 对拍验证。