题目描述

给你n根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示:

洛谷P1149.火柴棒等式(暴力搜索)-LMLPHP

注意:

  • 加号与等号各自需要两根火柴棍
  • 如果A≠B,则A+B=C与B+A=C视为不同的等式(A,B,C>=0)
  • n根火柴棍必须全部用上

输入格式

一个整数n(n<=24)。

输出格式

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

输入输出样例

输入 #1

14

输出 #1

2

输入 #2

18

输出 #2

9


我的分析

刚开始做这道题的时候,因为题目标签“搜索”蛊惑,我就真的一根脑经琢磨着用DFS做,后来证明这个做法并不是明智之举。

当时我先定义了一个数组,表示各个数与对应火柴数目的映射关系。因为不确定各个数具体范围是多少,为了保险起见,我的数组大小定义为1001,0-1000下标对应的元素即组成这些数的火柴数目。然后采取DFS的手段枚举所有情况,找出符合条件的所有三个数的组合。

--然而悲催的是,最后Time Limit Exceed!!/(ㄒoㄒ)/~~

洛谷P1149.火柴棒等式(暴力搜索)-LMLPHP

我痛定思痛,冷静分析了一波,应该是堆栈调用过多(3层),每次调用又经历一个1000的for循环,电脑遭不住了。(当时想的是3个数嘛,搜索3次嘛,后来才知道这个想法多么愚蠢,因为确定了前两个数,第三个数就是他们的和,自然确定了啊,根本不需要再搜索了,只需要调用两次即可/(ㄒoㄒ)/~~)

正当我心灰意冷,准备放弃时,我耳边突然想起了OI界的神之诫言:“骗分过样例,暴力出奇迹”

于是,我删掉之前的代码,准备用暴力法卷头重来!!(好吧,这应该是贬义词)

洛谷P1149.火柴棒等式(暴力搜索)-LMLPHP

我在对之前的不堪入目的算法作出了如下改进,首先我没有再申请了1001大小的数组,而是用一个函数即时计算每一个数对应的火柴数,而这仅仅需要大小为10的数组(用于表示出0-9对应的火柴数),其余数对应的火柴数皆可用函数在此基础上计算出。我把DFS的递归也也换成了双重for循环的暴力迭代,最终代码如下:

#include<iostream>
using namespace std;
//对应0-9的火柴数
int map[10]={6,2,5,5,4,5,6,3,7,6};
//计算某个数对应的火柴数
int match(int n){
//0单独处理
if(n==0) return 6;
int count=0;
//分离该数各位数分别计算火柴数
//然后将火柴数累加
while(n){
count +=map[n%10];
n/=10;
}
return count;
}
int main(){
int n;
cin>>n;
int count=0;
for(int i=0;i<=1000;++i){
for(int j=0;j<=1000;++j){
//因为+,=共占4根火柴,故-4
if(match(i)+match(j)+match(i+j)==n-4)
count++;
}
}
cout<<count<<endl;
return 0;
}

最后,如愿以偿的AC啦!

洛谷P1149.火柴棒等式(暴力搜索)-LMLPHP

05-17 01:34