信息学奥赛一本通 1852：【08NOIP提高组】火柴棒等式 | 洛谷 P1149 [NOIP2008 提高组] 火柴棒等式

【题目链接】

ybt 1852：【08NOIP提高组】火柴棒等式
洛谷 P1149 [NOIP2008 提高组] 火柴棒等式

【题目考点】

1. 枚举

2. 数字拆分

3. 打表

【解题思路】

先设数组st，st[i]表示数字i由几个火柴棍组成，其中i为0~9的数字。

数字1用的火柴棍最少，考虑公式1111+1=1112，该公式已经用了25根火柴棍，而题目询问的n最大为24。在此基础上，两个加数如果继续增大，整个公式使用的火柴棍数量只会增加。因此可以认为两个加数都是小于等于1111的。

解法1：枚举 设函数求数字使用的火柴棍数量

设函数matchCt，matchCt(n)求数字n由多少火柴棍组成，用数字拆分的方法得到n的每位数字，将组成每位数字的火柴棍数量加和返回。
枚举两个可能的加数，枚举范围为0~1111，对于每次枚举出的两个加数，求出这两个数字相加的等式所用的火柴棍数量是否等于n，如果是，则计数。最后输出计数数量。

解法2：枚举 先求出每个数字使用的火柴棍数量

设数组st，st[i]表示数字i使用的火柴棍数量（数字i可以很大）。调用matchCt函数求出st数组。
而后枚举每对可以相加的数字组成等式，直接在st数组中取值来获取数字使用火柴棍的数量，复杂度会比解法1降低一些。

解法3：枚举 记忆化递归求每个数字使用火柴棍的数量

• 递归状态：st[i]：数字i使用的火柴棍的数量
• 递归关系：数字i使用的火柴棍数量，为数字i/10使用的火柴棍数量，加上数字i%10使用的火柴棍数量，即st[i] = st[i/10] + st[i%10]
• 递归出口：st[i]，i为0~9时，使用的火柴棍数量已知。

解法4：枚举 打表

由于输入的n最大为24，只有24种结果，因此可以打表。
打表程序：枚举两个加数为0~1111的每种情况，只要加和火柴数加和小于等于24，则做计数，将所有的计数带逗号输出。
将打表程序的输出拷贝到题解程序，输入n，做询问即可。

【题解代码】

解法1：枚举 设函数求数字使用的火柴棍数量

#include 
using namespace std;
int st[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};//st[i]:数字i的火柴棍数 
int matchCt(int x)//求数字x由多少个火柴棍组成 
{
	int s = 0, a = x;
	do
	{
		s += st[a%10];
		a /= 10;
	}while(a > 0);
	return s;
}
int main()
{
	int n, ct = 0;//ct:加和为n的个数 
	cin >> n;
	for(int i = 0; i <= 1111; ++i)//考虑到1111+1=1112，已经用了21个火柴了，数字再大只能使用更多火柴 
		for(int j = 0; j <= 1111; ++j)
			if(matchCt(i) + matchCt(j) + matchCt(i+j) + 4 == n)//公式i加j等于i+j的总火柴棍数量 
				ct++;
	cout << ct;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

解法2：枚举 先求出每个数字使用的火柴棍数量

#include 
using namespace std;
int st[2500] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};//st[i]:数字i的火柴棍数 
int matchCt(int x)//求数字x由多少个火柴棍组成 
{
	int s = 0, a = x;
	do
	{
		s += st[a%10];
		a /= 10;
	}while(a > 0);
	return s;
}
int main()
{
	int n, ct = 0;//ct:加和为n的个数 
	cin >> n;
	for(int i = 10; i <= 2222; ++i)//先初始化st数组 
		st[i] = matchCt(i);
	for(int i = 0; i <= 1111; ++i)//考虑到1111+1=1112，已经用了21个火柴了，数字再大只能使用更多火柴 
		for(int j = 0; j <= 1111; ++j)
			if(st[i] + st[j] + st[i+j] + 4 == n)//公式i加j等于i+j的总火柴棍数量 
				ct++;
	cout << ct;
	return 0;
}
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

解法3：枚举 记忆化递归求每个数字使用火柴棍的数量

#include 
using namespace std;
int st[2500] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};//st[i]:数字i的火柴棍数  
int matchCt(int x)//求数字x由多少个火柴棍组成 
{
	if(st[x] > 0)
		return st[x];
	return st[x] = matchCt(x/10) + st[x%10];
}
int main()
{
	int n, ct = 0;//ct:加和为n的个数 
	cin >> n;
	for(int i = 0; i <= 1111; ++i)//考虑到1111+1=1112，已经用了21个火柴了，数字再大只能使用更多火柴 
		for(int j = 0; j <= 1111; ++j)
			if(matchCt(i) + matchCt(j) + matchCt(i+j) + 4 == n)//公式i加j等于i+j的总火柴棍数量 
				ct++;
	cout << ct;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

解法4：枚举 打表

• 打表程序

#include 
using namespace std;
int st[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};//st[i]:数字i的火柴棍数 
int ct[25];//ct[i]:总火柴数目为i的情况数 
int matchCt(int n)//求数字n由多少个火柴棍组成 
{
	int s = 0, a = n;
	do
	{
		s += st[a%10];
		a /= 10;
	}while(a > 0);
	return s;
}
int main()
{
	for(int i = 0; i <= 1111; ++i)//考虑到1111+1=1112，已经用了21个火柴了，数字再大只能使用更多火柴 
		for(int j = 0; j <= 1111; ++j)
		{
			int mc = matchCt(i) + matchCt(j) + matchCt(i+j) + 4;//公式i加j等于i+j的总火柴棍数量 
			if(mc <= 24)
				ct[mc]++;
		}
	cout << ct[0];
	for(int i = 1; i <= 24; ++i)
		cout << ',' << ct[i];
	return 0;
}
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

• 题解程序

#include 
using namespace std;
int main()
{
	int n, ct[25] = {0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,8,9,6,9,29,39,38,65,88,128};
	cin >> n;
	cout << ct[n];
	return 0;
}
1
2
3
4
5
6
7
8
9