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

· · 题解

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

PS:暴力枚举会TLE+WA 
#include <bits/stdc++.h>
using namespace std;
const int num[] = {6,2,5,5,4,5,6,3,7,6};//下标数对应的火柴棒个数
int search(int x){
    if(x == 0) return num[0];
    int ans = 0;
    while(x){//从最后位开始 
        int t = x % 10;
        ans += num[t];
        x /= 10;
    }
    return ans;
}
int main(){
    int n,cnt = 0; cin >> n;
    for(int i = 0;i <= 1000;i++)//因为 最多为四位数 
        for(int j = 0;j <= 1000;j++)
            if(search(i) + search(j) + search(i+j) + 4 == n) ++cnt;//符合条件 
    cout << cnt;//加4是因为有一个加号一个等于号 search(i与j的和) 
    return 0;
}