P1149 火柴棒等式
补上之前落下的递归题orz
基本思路就是个二重循环，枚举a，再枚举b，直接a+b得出c
然后在枚举的范围懵了orz，其实最大是24根火柴，减去加号等于号是20根，再减去0后除以2剩余八根，就是最大值为1111
题目描述
给你n根火柴棍，你可以拼出多少个形如“ A+B=C ”的等式？等式中的 A 、 B 、 C 是用火柴棍拼出的整数（若该数非零，则最高位不能是 00 ）。用火柴棍拼数字 0-90−9 的拼法如图所示：
注意：
加号与等号各自需要两根火柴棍
如果 A≠B ，则 A+B=C与 B+A=C 视为不同的等式( A,B,C>=0 )
nn 根火柴棍必须全部用上
一个整数 n(n<=24)n(n<=24) 。
输出格式：一个整数，能拼成的不同等式的数目。
输入输出样例输入样例#1： 14
输出样例#1： 2
输入样例#2： 18
输出样例#2： 9
说明
【输入输出样例1解释】
2 个等式为
0+1=1
0+1=1 。
【输入输出样例2解释】
99 个等式为：
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
ac代码：
#include <iostream>
#include <cmath>
#include <map>
#define ll long long
using namespace std;
int s=0;
int n;
void dfs(int x,int l,int t){
int i;
map <int,int> mp;
mp[0]=6,mp[1]=2,mp[3]=5,mp[4]=4,mp[5]=5,mp[6]=6,mp[7]=3,mp[8]=7,mp[9]=6,mp[2]=5;
int r=l;
for(i=0;i<=t;i++){
l=r;
int y=i;
do{
int k=y%10;
l+=mp[k];
y=y/10;
}while(y);
int h=i+x;
if(l>=n) continue;
int e=h;
do{
int k=h%10;
l+=mp[k];
h=h/10;
}while(h);
if(l==n){
s++;
}
}
}
int main()
{
cin>>n;
map <int,int> mp;
mp[0]=6,mp[1]=2,mp[2]=5,mp[3]=5,mp[4]=4,mp[5]=5,mp[6]=6,mp[7]=3,mp[8]=7,mp[9]=6;
n-=4;//等号和加号
int sum=0,i;//方法总数
ll t=0;
int g=(n-6)/4;
while(g>0){
t=t*10+1;
g--;
}
t=1200;
for(i=0;i<=t;i++){
g=0;//已用火柴
int h=i;
do{
int k=h%10;
g+=mp[k];
h=h/10;
}while(h);
if(g>=n) continue;
dfs(i,g,t);
}
cout<<s<<endl;
return 0;
}
评论