「枚举」的入门题目

题目地址

题目描述

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

img

注意：

1. 加号与等号各自需要两根火柴棍
2. 如果 ，则 与 视为不同的等式( )
3. 根火柴棍必须全部用上

输入输出格式

输入格式：

一个整数 () 。

输出格式：

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

输入样例#1：

1

14

输出样例#1：

1

2

输入样例#2：

1

18

输出样例#2：

1

9

说明

【输入输出样例1解释】

个等式为 和 。

【输入输出样例2解释】

个等式为：

1
2
3
4
5
6
7
8
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

解题思路

枚举思路

我们可以枚举和

上界？

手算啊

，去掉符号用的4根火柴棒，相当于是「」

再（这里只考虑有和两个数字），可得

对于某一个数字，可调用的火柴棒共有10个

由于使用火柴棒数量最少的要使用2根，所以我们假设两个数字都为，但是显然这样是不成立的，因为就已经达到了，没有火柴棒再放第三个数字，那么由此可粗略得出

对于某一个数字，它最高有5位

于是我们可以选择枚举到，洛谷的评测机上也不会TLE

当然CCF的老爷机就不一定了（

于是我们可以选择再精确一点

// 未完待续

枚举之后相加，取出所用的火柴棒数，进行判断就好了

预处理思路

火柴棒数怎么求？

新建一个数组 f[10000 * 2 + 10] ，表示i这个数字需要用f[i]根火柴

题目已经给出了f[09]，如何处理出f[10(10000*2)]？

1
2
3
4
5
6

f[i] = f[i/10] + f[i%10]; // (i >= 10)
/*
这里的i/10可以取它除了个位上其他位的数，在前面已经处理过，
所以可以直接使用；这里的i%10可以取它个位上的数，也处理过，
可以直接使用。两个火柴棒数目一相加，就能获得火柴棒的总数。
*/

循环一遍就好了

代码实现

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 <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int sticks[10001 * 2];

int main(int argc, char *const argv[]) {
	sticks[0] = sticks[6] = sticks[9] = 6;
	sticks[1] = 2;
	sticks[2] = sticks[3] = sticks[5] = 5;
	sticks[4] = 4;
	sticks[7] = 3;
	sticks[8] = 7;
	int n;
	cin >> n;
	int sum = 0;
	for (int i = 10; i <= 20000; ++i) {
		sticks[i] = sticks[i/10] + sticks[i%10];
	}
	for (int i = 0; i <= 9999; ++i) {
		for (int j = 0; j <= 9999; ++j) {
			if (sticks[i] + 2 + sticks[j] + 2 + sticks[i+j] == n) ++sum;
		}
	} 
	cout << sum << endl;
	return 0;
}