题解

估计不是最优解(其实是练习时写的，本人是蒟蒻)

首先，题目中说 + 和 = 分别需要两根火柴，那么直接在输入后执行

n -= 2

然后我们可以建立一个结构体数组 num ，代码如下：

struct number{
    int need;  //need表示这个数字所需的火柴数量
    int num;  //num表示这个数字
};
number num[10] = {{6, 0}, {2, 1}, {5, 2}, {5, 3}, {4, 4}, {5, 5}, {6, 6}, {3, 7}, {7, 8}, {6, 9}};

然后按所需的火柴数量排序一下 num 数组

bool cmp(number a, number b){
    if (a.need != b.need) return a.need < b.need;
    return a.num > b.num;
}
sort(num, num + 9, cmp);

接下来用两个DFS函数算 a 和 b 就好了
最后计算两个数之和 c
然后算一下所需火柴数量是否符合条件即可
再搭配一点剪枝

完整代码：

#include <bits/stdc++.h>
using namespace std;
struct number{
    int need;
    int num;
};
number num[10] = {{6, 0}, {2, 1}, {5, 2}, {5, 3}, {4, 4}, {5, 5}, {6, 6}, {3, 7}, {7, 8}, {6, 9}};
int num_need[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int n;
long long ans = 0;
bool cmp(number a, number b){
    if (a.need != b.need) return a.need < b.need;
    return a.num > b.num;
}
void check_c(long long a, long long b, int n2){
	long long c = a + b;
	//cout << a << " + " << b << " = " << c << ' ';
    long long use = 0;
    if (c == 0) use = 6;
    while (c) {
        use += num_need[c % 10];
        c /= 10;
    }
    //cout << "use:" << (n - n2) + use << endl;
    if (n2 - use != 0) return;
    //cout << a << " + " << b << " = " << a+b << " ";
    //cout << "use:" << (n - n2) + use << endl;
    ans++;
    return;
}
void DFS_b(long long a, long long b, int n2){
	if (n2 <= 0) return;
    for (int i = 0 ; i <= 9 ; i++) {
        if (num[i].need > n2) break;
        int use = 0;
        long long new_num = 0;
        if (b == 0 && num[i].num == 0) {
            //new_num = 0;
            //use = num[i].need;
            check_c(a, 0, n2 - num[i].need);
            continue;
        }
        else {
            new_num = b * 10 + num[i].num;
            use = num[i].need;
        }
        DFS_b(a, new_num, n2 - use);
        check_c(a, new_num, n2 - use);
    }
}
void DFS_a(long long a, long long b, int n2) {
	if (n2 <= 0) return;
    for (int i = 0 ; i < 10 ; i++) {
        if (num[i].need > n2) break;
        int use = 0;
        long long new_num = 0;
        if (a == 0 && num[i].num == 0) {
            //new_num = 0;
            //use = num[i].need;
            DFS_b(0, b, n2 - num[i].need);
            continue;
        }
        else {
            new_num = (a * 10) + num[i].num;
            use = num[i].need;
        }
        DFS_a(new_num, b, n2 - use);
        DFS_b(new_num, b, n2 - use);
    }
}
void solve() {
    sort(num, num + 9, cmp);
    DFS_a(0, 0, n);
    cout << ans;
}
int main() {
    cin >> n;
    n -= 4;
    solve();
    return 0;
}