[NOIP 2008 提高组] 火柴棒等式

题意

给定 n 根火柴，要求拼出形如：

text

1A + B = C

的等式。加号和等号一共固定消耗 4 根火柴，数字 0..9 的消耗已知。要求所有火柴恰好用完，统计不同等式数量。

思路

先扣掉加号和等号的 4 根火柴，剩下的火柴全部用于 A、B、C 三个数。

由于 n <= 24，数字部分最多只剩 20 根火柴，合法数字不会很大。枚举：

text

1
2
30 <= A < 1000
0 <= B < 1000
C = A + B

然后检查：

text

1cost(A) + cost(B) + cost(C) == n - 4

为了让 Python 跑得更稳，先预处理 0..1999 每个数的火柴消耗。

Python 知识

str(number) 可以把整数转成十进制字符串，再逐位统计。
列表 MATCH_COUNT[digit] 保存每个数字需要的火柴数。
预处理 costs = [...] 可以避免双重循环里反复计算字符串。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20MATCH_COUNT = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]


def match_count(number):
    return sum(MATCH_COUNT[int(digit)] for digit in str(number))


n = int(input())
target = n - 4
costs = [match_count(number) for number in range(2000)]

answer = 0
for a in range(1000):
    cost_a = costs[a]
    for b in range(1000):
        c = a + b
        if cost_a + costs[b] + costs[c] == target:
            answer += 1

print(answer)

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/**
 * 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-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

int cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int calc(int x) {
    if (x == 0) return cost[0];
    int sum = 0;
    while (x) { sum += cost[x % 10]; x /= 10; }
    return sum;
}

int n, ans;
int cost_pre[2005]; // 预处理 0..2000 的火柴消耗

int main() {
    cin >> n;
    int target = n - 4;
    for (int i = 0; i <= 2000; i++) cost_pre[i] = calc(i);
    for (int a = 0; a <= 1000; a++) {
        int ca = cost_pre[a];
        for (int b = 0; b <= 1000; b++) {
            int c = a + b;
            if (c > 2000) continue; // 不超过范围
            if (ca + cost_pre[b] + cost_pre[c] == target) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

复杂度

枚举 A,B 共 $1000^2$ 组，预处理是常数规模。时间复杂度为 $O(10^6)$ ，空间复杂度为 $O(1)$ 。

总结

这题的关键是把符号消耗先扣掉，再把等式变成双重枚举 A,B 和一次代价检查。

[NOIP 2008 提高组] 火柴棒等式

目录

题意

思路

Python 知识

代码

复杂度

总结