12.[NOIP2008 提高组] 火柴棒等式 难度：普及+/提高 来源：-- AC代码（C++）： 没有注释，自行学习。 by：ACGO 你的点赞和关注就是我更新题解的最大动力！ ------------------------------点个赞吧 ↓ ！----------------------------

#include <bits/stdc++.h> using namespace std; int a[2001] = {6}; int c[10] = {6,2,5,5,4,5,6,3,7,6}; int get_num,num1,num2; int main(void) { cin >> get_num; for (int i = 1;i <= 2000;i++) { num2 = i; while (num2 >= 1) { a[i] = a[i] + c[num2 % 10]; num2 /= 10; } } num1 = 0; for (int i = 0;i <= 1000;i++) { for (int j = 0;j <= 1000;j++) { if (get_num == a[i] + a[j] + a[i + j] + 4) { num1++; } } } cout << num1; return 0; }

**你的点赞和关注就是我更新题解的最大动力！ ------------------------------点个赞吧 ↓ ！----------------------------

题解： 因为nnn<=242424，我们马上看出来，这个等式能模拟出的最大的数字绝对不会大于100010001000，所以我们考虑表示出111-100010001000的所有数字，基于这个开始枚举，最后得出答案。 是的，有些事情就是这么巧妙，什么打表啊，枚举啊，模拟啊，都是智慧的结晶，请大家不要嗤之以鼻。 所以我们开始模拟。 先处理出的a[]a[]a[]数组保存的是当数组下标为iii的时候，需要几根火柴模拟出来。为什么aaa数组要开200020002000呢？因为后来判断的时候要a[i+j]a[i+j]a[i+j]，而iii和jjj都是100010001000规模的，不开200020002000会RE。 然后我们打表处理出mmm数组，表示拼出数字，注意是数字iii的时候需要几根火柴，然后就可以按位表示了。应该很简单。 最后判断，不用多说了。 注意要加444。 所以就AC了: 欢迎加入团队

题意分析 用 nnn 根火柴棒拼等式 A+B=CA+B=CA+B=C，求有多少种拼法。 解题思路 首先看到数据范围，第一个想到的就是打表枚举，那枚举什么呢？肯定是 ABCABCABC 了。能确定的是需要 444 根火柴棒拼符号，因此我们有至多 202020 根火柴棒来拼 ABCABCABC。一看好像很多，最少花费的数字是1，最高能到 101010 位数！事实并非如此，以下是上界推导，也是本题难点： 设 A=1A=1A=1（最小火柴 222 根），s(N)s(N)s(N) 为拼 NNN 所需要的火柴数 推出 a+b+c≤20a+b+c ≤ 20a+b+c≤20，B=C−1B=C-1B=C−1，所以 s(C)+s(C−1)≤18s(C)+s(C-1) ≤ 18s(C)+s(C−1)≤18 假设一个枚举上界 C≤2000C≤2000C≤2000，对 C≥2000C≥2000C≥2000 上述等式不成立，所以可以证明上界 C≤2000C≤2000C≤2000 可用 当 AAA 不是 111 时，所需火柴更多，不等式更严 所以在 n≤24n≤24n≤24 时，CCC 最大不超过 200020002000 当然，也可以根据数据范围猜测数较小 接下来是就是实现，既然已经知道了数据范围，就可以根据范围来枚举。若枚举 ABCABCABC 并在枚举时计算火柴棒花费则可能会超时，可以先把所有 ABCABCABC 的可能值，也就是 200020002000 以下的所有数字需要的火柴棒数量计算出来，可以节省大量时间。枚举 aaa 和 bbb 各自最多约 150015001500 种可能，大概 2e62e62e6 的计算量，不会超时 AC代码

看数据范围，很小，手算或者程序打表就可以过。 代码：

| | |---|---| | | |

#include <bits/stdc++.h> using namespace std; int a[2001] = {6}; int c[10] = {6,2,5,5,4,5,6,3,7,6}; int get_num,num1,num2; int main(void) { cin >> get_num; for (int i = 1;i <= 2000;i++) { num2 = i; while (num2 >= 1) { a[i] = a[i] + c[num2 % 10]; num2 /= 10; } } num1 = 0; for (int i = 0;i <= 1000;i++) { for (int j = 0;j <= 1000;j++) { if (get_num == a[i] + a[j] + a[i + j] + 4) { num1++; } } } cout << num1; return 0; }

话不多说，请看题解~

#include <bits/stdc++.h> using namespace std; int a[2001] = {6}; int c[10] = {6,2,5,5,4,5,6,3,7,6}; int get_num,num1,num2; int main(void) { cin >> get_num; for (int i = 1;i <= 2000;i++) { num2 = i; while (num2 >= 1) { a[i] = a[i] + c[num2 % 10]; num2 /= 10; } } num1 = 0; for (int i = 0;i <= 1000;i++) { for (int j = 0;j <= 1000;j++) { if (get_num == a[i] + a[j] + a[i + j] + 4) { num1++; } } } cout << num1; return 0; }

#include <iostream> using namespace std; int need[]={6,2,5,5,4,5,6,3,7,6}; int cnt(int cur){ int ans=0,ret; if(cur==0)return 6; while(cur>0){ ret=cur%10; ans+= need[ret]; cur/=10; } return ans; } int main(){ int ansk=0; int n; cin>>n; for(int i=0;i<720;i++){ for(int j=0;j<720;j++){ int a=cnt(i); int b=cnt(j); int d=cnt(i+j); int c=n-4-a-b; if(d=c){ ansk++; } } } cout<<ansk; return 0; }

#include <bits/stdc++.h> using namespace std; int a[2001] = {6}; int c[10] = {6,2,5,5,4,5,6,3,7,6}; int get_num,num1,num2; int main(void) { cin >> get_num; for (int i = 1;i <= 2000;i++) { num2 = i; while (num2 >= 1) { a[i] = a[i] + c[num2 % 10]; num2 /= 10; } } num1 = 0; for (int i = 0;i <= 1000;i++) { for (int j = 0;j <= 1000;j++) { if (get_num == a[i] + a[j] + a[i + j] + 4) { num1++; } } } cout << num1; return 0; }

#include<bits/stdc++.h> using namespace std; int a[] = {1, 2, 8, 9, 6, 9, 29, 39, 38, 65, 88, 128}; int main(){ int n; cin >> n; if(n <= 12) cout << 0; else cout << a[n - 13]; return 0; }

#include<cstdio> using namespace std; int a[]={1,2,8,9,6,9,29,39,38,65,88,128}; int main(){ int n; scanf("%d",&n); if(n <= 12) printf("0"); else printf("%d",a[n - 13]); return 0; }