火柴棒等式（洛谷
1149 && NOIp2008
提高组
T2
）
题目描述
给你 n 根火柴棍， 你可以拼出多少个形如 “A+B=C” 的等式？ 等式中的 A 、 B 、 C
是用火柴棍拼出的整数（ 若该数非零， 则最高位不能是 0 ） 。
注意：
加号与等号各自需要两根火柴棍
如果 A≠B ， 则 A+B=C 与 B+A=C 视为不同的等式（ A 、 B 、 C>=0 ）
n 根火柴棍必须全部用上
输入输出格式
输入格式：
输入文件 matches.in 共一行， 又一个整数 n （ n<=24 ） 。
输出格式：
输出文件 matches.out 共一行， 表示能拼成的不同等式的数目。
输入输出样例
输入样例 #1 ：
样例输入 1 ：
14
样例输入 2 ：
18
分析：
直接暴力枚举每个数， 就是正解。 （ 注意处理火柴的数量） 火柴棒等式 .cpp 代
码很简单：
——————————————
基于 dfs 框架的枚举
既然也是枚举， 那么大体思路也是一样的。 对于某些问题， 有 n 个需要确定
的内容。 通常， 我们就可以用 n 层循环语句进行逐一枚举， 再判断每种情况能否
符合条件， 最后得出答案。 但是， 这里不同的是， 你不能确定到底有多少层循环，
或者， 循环的层数是由输入来决定的， 或者循环的层数太多了， 代码写不下。
这时我们可以使用 dfs （ 深度优先搜索） 的框架来解决问题。
给出伪代码
void dfs ( int x, int step ) {
if ( step == n ) return ; // 如果已经有 n 层
for ( i = 1; i <= 当前层所有可能的情况 ; i ++ ） {
Do_what_you_want_here() ; // 决定当前
dfs ( u, step+1 ) ; // 层数 +1
Back() ; // 回溯
}
}
题目描述
给你 n 根火柴棍， 你可以拼出多少个形如 “A+B=C” 的等式？ 等式中的 A 、 B 、 C
是用火柴棍拼出的整数（ 若该数非零， 则最高位不能是 0 ） 。
注意：
加号与等号各自需要两根火柴棍
如果 A≠B ， 则 A+B=C 与 B+A=C 视为不同的等式（ A 、 B 、 C>=0 ）
n 根火柴棍必须全部用上
输入输出格式
输入格式：
输入文件 matches.in 共一行， 又一个整数 n （ n<=24 ） 。
输出格式：
输出文件 matches.out 共一行， 表示能拼成的不同等式的数目。
输入输出样例
输入样例 #1 ：
样例输入 1 ：
14
样例输入 2 ：
18
分析：
直接暴力枚举每个数， 就是正解。 （ 注意处理火柴的数量） 火柴棒等式 .cpp 代
码很简单：
——————————————
基于 dfs 框架的枚举
既然也是枚举， 那么大体思路也是一样的。 对于某些问题， 有 n 个需要确定
的内容。 通常， 我们就可以用 n 层循环语句进行逐一枚举， 再判断每种情况能否
符合条件， 最后得出答案。 但是， 这里不同的是， 你不能确定到底有多少层循环，
或者， 循环的层数是由输入来决定的， 或者循环的层数太多了， 代码写不下。
这时我们可以使用 dfs （ 深度优先搜索） 的框架来解决问题。
给出伪代码
void dfs ( int x, int step ) {
if ( step == n ) return ; // 如果已经有 n 层
for ( i = 1; i <= 当前层所有可能的情况 ; i ++ ） {
Do_what_you_want_here() ; // 决定当前
dfs ( u, step+1 ) ; // 层数 +1
Back() ; // 回溯
}
}
附AC码：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
int a[10]={6,2,5,5,4,5,6,3,7,6};
int gs(int x){int ans=0;if(x==0)return 6;while(x>0){ans+=a[x%10];x/=10;}return ans;
}
int main(){int i,j,k,n,hehe=0;scanf("%d",&n);n-=4; for(i=0;i<=999;i++)for(j=0;j<=999;j++)if(gs(i)+gs(j)+gs(i+j)==n)hehe++;printf("%d\n",hehe);return 0;
}