[折腾笔记] 洛谷P1149-火柴棒等式 AC记

原题链接： https://www.luogu.org/problem/P1149

题面简述：

给你n根火柴棍，你可以拼出多少个形如“A+B=C”“A+B=C”“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根火柴棍必须全部用上

思路：

等式可能的情况：

x+y=zx + y = zx+y=z

xx+yy=zzxx+yy=zzxx+yy=zz

xxx+yyy=zzzxxx+yyy=zzzxxx+yyy=zzz

xxxx+yyyy=zzzzxxxx+yyyy=zzzzxxxx+yyyy=zzzz

为啥这么说呢？因为计算在极端条件n=24n = 24n=24,的情况下，最高位数是:

24÷2=1224\div 2=1224÷2=12 (如果全部摆111的话，可以摆121212个111) 12÷3=412\div 3=412÷3=4 一共有333个数，于是最多444位。

---

于是，我们大可枚举，因为枚举的话再加上优化，不会超时所以，就可以写出如下代码：

#include <bits/stdc++.h>

using namespace std;

int s[] = {6,2,5,5,4,5,6,3,7,6};

int t = 4;

int ans = 0;

bool judge(int a,int b,int c,int n) {

    int p = 0;

    string d = to_string(a),e = to_string(b),f = to_string(c);

    for(int i = 0;i<d.length();++i) p+=s[d[i]-'0'];

    for(int i = 0;i<e.length();++i) p+=s[e[i]-'0'];

    for(int i = 0;i<f.length();++i) p+=s[f[i]-'0'];

    if(p==n) {

        return 1;

    }

    return 0;

}

int main() {

	int n;

	cin>>n;

	n-=4;

	for(int i = 0;i<=9999;++i) {

        for(int j = 0;j<=9999;++j) {

            int k = i+j;

            if(i+j==k&&judge(i,j,k,n)) {

                ans++;

            }

        }

    }

	cout<<ans<<endl;

}

另外之前还犯了个错误:

#include <bits/stdc++.h>

using namespace std;

int s[] = {6,2,5,5,4,5,6,3,7,6};

int t = 4;

int ans = 0;

bool judge(int a,int b,int c,int n) {

    int p = 0;

    string d = to_string(a),e = to_string(b),f = to_string(c);

    for(int i = 0;i<d.length();++i) p+=s[d[i]-'0'];

    for(int i = 0;i<e.length();++i) p+=s[e[i]-'0'];

    for(int i = 0;i<f.length();++i) p+=s[f[i]-'0'];

    if(p==n) {

        return 1;

    }

    return 0;

}

int main() {

	int n;

	cin>>n;

	n-=4;

	for(int i = 0;i<=n;++i) {

        for(int j = 0;j<=n;++j) {

            int k = i+j;

            if(i+j==k&&judge(i,j,k,n)) {

                ans++;

            }

        }

    }

	cout<<ans<<endl;

}

这里只枚举到n不够。