题目描述

给你 n 根火柴棍，你可以拼出多少个形如 A+B=C 的等式？等式中的 A、B、C 是用火柴棍拼出的整数（若该数非零，则最高位不能是 0）。用火柴棍拼数字 0∼9 的拼法如图所示：

注意：

1. 加号与等号各自需要两根火柴棍；
2. 如果 A=B，则 A+B=C 与 B+A=C 视为不同的等式（A,B,C≥0）；
3. n 根火柴棍必须全部用上。

输入格式

一个整数 n(1≤n≤24)。

输出格式

一个整数，能拼成的不同等式的数目。

输入输出样例

输入 #1复制

14

输出 #1复制

2

输入 #2复制

18

输出 #2复制

9

说明/提示

【输入输出样例 1 解释】

2 个等式为 0+1=1 和 1+0=1。

【输入输出样例 2 解释】

9 个等式为

0+4=4、0+11=11、1+10=11、2+2=4、2+7=9、4+0=4、7+2=9、10+1=11、11+0=11。

noip2008 提高第二题

代码

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1e4+10;
int a[N];
int q[10]={6,2,5,5,4,5,6,3,7,6}; 
int res=0;
int col(int x)
{
	if(x==0)
	{
		return q[0];
	}
	else
	{
		int sumfire=0; 
		while(x>0)
		{
			sumfire+=q[x%10];
			x/=10;
		}
		return sumfire;
	}
}
void dfs(int u,int sum)
{
	if(sum>n)
	return ;
	if(u>3)
	{
		if(a[1]+a[2]==a[3]&&sum==n)
		res++;
		return ;
	}
	 
	 
	 
	 for(int i=0;i<=1111;i++)
	 {
	 	a[u]=i;
	 	dfs(u+1,sum+col(i));
		a[u]=0; 
	 }
	 
}
int main()
{
	cin>>n;
	n-=4;
	dfs(1,0);
	cout<<res<<endl;
	return 0;

	
}

含有注释的代码

#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 1e4 + 10;
int a[N];
// 存储0 - 9每个数字所需的火柴棒数量
int q[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; 
int res = 0;

// 计算数字x所需的火柴棒数量
int col(int x) {
    if (x == 0) {
        return q[0];
    }
    int sumfire = 0;
    while (x > 0) {
        sumfire += q[x % 10];
        x /= 10;
    }
    return sumfire;
}

// 深度优先搜索函数
void dfs(int u, int sum) {
    if (sum > n) return;

    if (u > 3) {
        if (a[1] + a[2] == a[3] && sum == n) {
            res++;
        }
        return;
    }

    // 缩小数字范围，减少不必要的计算
    for (int i = 0; i <= 1111; i++) {
        a[u] = i;
        dfs(u + 1, sum + col(i));
        a[u] = 0;
    }
}

int main() {
    cin >> n;
    // 减去“+”和“=”所需的4根火柴棒
    n -= 4;
    dfs(1, 0);
    cout << res << endl;
    return 0;
}

优化代码 （时间更短）

#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 1e4 + 10;
int a[N];
int q[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; 
int stickCount[N]; // 用于存储每个数字所需的火柴棒数量
int res = 0;

// 预处理所有可能用到的数字所需的火柴棒数量
void preprocess() {
    for (int i = 0; i < N; i++) {
        int x = i;
        int sumfire = 0;
        if (x == 0) {
            sumfire = q[0];
        } else {
            while (x > 0) {
                sumfire += q[x % 10];
                x /= 10;
            }
        }
        stickCount[i] = sumfire;
    }
}

void dfs(int u, int sum) {
    if (sum > n)
        return;
    if (u > 3) {
        if (a[1] + a[2] == a[3] && sum == n)
            res++;
        return;
    }

    for (int i = 0; i <= 1111; i++) {
        a[u] = i;
        dfs(u + 1, sum + stickCount[i]);
        a[u] = 0; 
    }
}

int main() {
    preprocess();
    cin >> n;
    n -= 4;
    dfs(1, 0);
    cout << res << endl;
    return 0;
}

1、这里取得火柴的数量为1~24，其中的加号和等号总共需要4根火柴，我们首先进行搜索数存入一个数组中u>3时，就进行判断

2、然后就剩20根火柴去组成3个数

3、就是写一个判断数需要火柴的函数col

这里给大家推荐Bilibili一个博主的视频https://www.bilibili.com/video/BV1N24y1W7q4/?spm_id_from=333.1391.0.0