P1149 [NOIP 2008 提高组] 火柴棒等式——题解

解题思路

先写函数计算一个非负整数所需的火柴数，其中 0 需要单独处理。因为火柴总数很小，等式中的数不会很大，枚举 $A,B$，令 $C=A+B$，检查三个数的火柴数再加上加号、等号的 4 根是否恰好等于 $n$。

复杂度分析

枚举范围固定到 0 到 1000，时间复杂度约 $O(10^6)$，空间复杂度 $O(1)$。

易错点

整数 0 需要 6 根火柴；加号和等号总共固定消耗 4 根。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int c[10]={6,2,5,5,4,5,6,3,7,6};
int cost(int x){
    if(x==0) return c[0];
    int s=0;
    while(x){s+=c[x%10];x/=10;}
    return s;
}
int main(){
    int n; cin>>n; int ans=0;
    for(int a=0;a<=1000;a++)
        for(int b=0;b<=1000;b++){
            int z=a+b;
            if(cost(a)+cost(b)+cost(z)+4==n) ans++;
        }
    cout<<ans<<'\n';
    return 0;
}

#include <bits/stdc++.h> using namespace std; int c[10]={6,2,5,5,4,5,6,3,7,6}; int cost(int x){ if(x0) return c[0]; int s=0; while(x){s+=c[x%10];x/=10;} return s; } int main(){ int n; cin>>n; int ans=0; for(int a=0;a<=1000;a++) for(int b=0;b<=1000;b++){ int z=a+b; if(cost(a)+cost(b)+cost(z)+4n) ans++; } cout<<ans<<'\n'; return 0; }