洛谷题单指南-暴力枚举-P1149 [NOIP2008 提高组] 火柴棒等式

原题链接：https://www.luogu.com.cn/problem/P1149

题意解读：计算符合A+B=C时，火柴棍数量正好等于n，可以采用枚举A、B，然后计算出C，根据A、B、C计算出所有火柴棍数量，再加上4根加号、等号的，如果与n相等，即为一种合法等式。

解题思路：

题目的关键在于枚举A、B时，最大值的设定，不能超时。

分析思路如下：

由于n最大是24，除开加号、等号，可用于拼数字的火柴棍有20根，且要分配到A、B、C三个数；

一个基本常识：用的火柴棍越少，可拼的数字就越长，也就越大；

再看每个数字所用的火柴棍数，1只需要2根，是最少的，假设B数用最少的火柴棍即2根，那么A、C分剩余18根；

根据A+B=C，那么C的数字长度要么等于A的数字长度，要么比A的数字长度多1；

18根火柴棍可以组成9个1，因此A最大为1111，不能再大了。

同样的分析，B最大也为1111，O(n²)不会超时。

100分代码：

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

int h[10] = {6, 2, 5, 5, 4 ,5, 6, 3, 7, 6}; //每个数字对应的火柴棍数
int n, ans;

//数字x由多少根火柴棍组成
int count(int x)
{
    if(x == 0) return h[0];

    int cnt = 0;
    while(x)
    {
        cnt += h[x % 10];
        x /= 10;
    }
    return cnt;
}

int main()
{
    cin >> n;

    for(int a = 0; a <= 1111; a++)
    {
        for(int b = 0; b <= 1111; b++)
        {
            int c = a + b;
            int all = count(a) + count(b) + count(c) + 4;
            if(all == n) ans++;
        }
    }

    cout << ans;
}