Time Limit: 1 second
Memory Limit: 50 MB
【问题描述】
给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：
注意：
1. 加号与等号各自需要两根火柴棍
2. 如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）
3. n根火柴棍必须全部用上
【输入】
共一行，有一个整数n（n<=24）
【输出】
共一行，表示能拼成的不同等式的数目。
【输入样例1】
14
【输出样例1】
2
【输入输出样例1解释】
2个等式为0+1=1和1+0=1。
【输入样例2】
18
【输出样例2】
9
【输入输出样例2解释】
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
【题解】
因为要减去一个等号一个加号；
所以最多n=20来组成所有的数字;
而数字消耗火柴棒最少的数字是1->消耗2根火柴棒；
则可以最多出现10个1；
然后分配到3个数字上；
则让C=4个1；A和B分别分配3个1;
如果C有5个1,则A也必须有5个1;
因为A+B=C这个式子C的位数最大是A和B的位数中最大的位+1;
然而A的位数为4的话,都是1，剩下1个数字,也没办法进位;
而A是5个1的话,B是0的话得增加6个棒。。
显然C位数最大不能超过4..
(以上是针对全是1的情况，显然这种情况的C是最大的,则其他情况也适用了);
而N=1000的话
O(N^2)是可以承受的;
枚举C然后再枚举B，再通过相减得到A就可以了；
用个函数计算某个数字要多少个棒棒.
【完整代码】
#pragma comment(linker,"/STACK:10240000000,10240000000")
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <string>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
void rel(LL &r)
{
r = 0;
char t = getchar();
while (!isdigit(t) && t!='-') t = getchar();
LL sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
}
void rei(int &r)
{
r = 0;
char t = getchar();
while (!isdigit(t)&&t!='-') t = getchar();
int sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
}
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int num[10] = {6,2,5,5,4,5,6,3,7,6};
int n;
int ans = 0;
int f(int x)
{
if (x==0) return num[x];
int t = x;
int tot = 0;
while (t>0)
{
tot+=num[t%10];
t/=10;
}
return tot;
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
cin >> n;
n-=4;
rep1(i,0,1111)
rep1(j,0,i)
{
int k = i-j;
if (f(k)+f(j)+f(i)==n)
ans++;
}
printf("%d
",ans);
return 0;
}