2008年NOIP提高组火柴棒（洛谷P1149）：暴力枚举优化

一、问题分析

2008年NOIP提高组的火柴棒等式问题要求计算使用给定数量火柴棒能组成多少个形如A+B=C的等式。这道题考察了选手对数字表示、枚举算法和简单数学建模的理解能力。

二、完整代码实现（含详细注释）

#include <iostream>
using namespace std;

// 每个数字0-9所需的火柴棒数量
const int match_count[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

// 计算一个数字需要的火柴棒总数
int get_match_num(int num) {
    if (num == 0) return match_count[0];
    int total = 0;
    while (num > 0) {
        total += match_count[num % 10];
        num /= 10;
    }
    return total;
}

int main() {
    int n;
    cin >> n;
    int count = 0;
    
    // 遍历所有可能的A和B组合
    for (int a = 0; a <= 1111; ++a) {
        for (int b = 0; b <= 1111; ++b) {
            int c = a + b;
            // 计算总火柴棒数：A + B + C + '+' + '='
            int total = get_match_num(a) + get_match_num(b) + get_match_num(c) + 4;
            if (total == n) {
                count++;
            }
        }
    }
    
    cout << count << endl;
    return 0;
}

三、关键知识点详解

1. 火柴棒数字表示：

• 使用数组预先存储每个数字(0-9)所需的火柴棒数量

• 数字1需要2根，7需要3根，8需要7根（最多）

2. 数字分解计算：

• 通过取模(%)和整除(/)操作分解多位数的每一位

• 对每位数字查询预存数组并累加

3. 枚举优化：

• 设置合理的枚举上限(1111)，避免无效计算

• 提前计算'+'和'='共需4根火柴棒

四、常见问题解答

Q: 为什么上限设为1111？ A: 这是经验值，因为24根火柴最多能表示4个1(2×4+2=10)，实际测试1111足够覆盖

Q: 如何计算运算符的火柴数？ A: '+'需要2根，'='需要2根，共4根

Q: 如何处理前导零？ A: 题目默认不考虑前导零情况，按正常数字处理