P1708 [入门赛 #21] 星云 hard ver. 题解

思路

看到此题，第一想到可以直接枚举，求一个数的数位之和，然后判断，可以就让方案数加一，代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    int n,k,cnt=0,ans;
    while(t--){
        cin>>n>>k;
        cnt=0;
        for(int i=1;i<pow(10,n);i++){
            ans=0;
            int temp=i;
            while(temp>0){
                ans+=(temp%10);
                temp/=10;
            }
            if(ans<=k) cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

可一测，啊，超时了？仔细一看，发现 \(T\) \(\le\) \(10^5\)。做的时候没想出来，后面看了别人的题解才发现可以打表，用一个二维数组，然后我就试了一下。温馨提示，不要用在线编译器，不然绝对超时，建议使用DEVC++。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[7][100]={1,2,3,4,5,6,7,8,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,2,5,9,14,20,27,35,44,54,63,71,78,84,89,93,96,98,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,3,9,19,34,55,83,119,164,219,282,351,424,499,574,647,716,779,834,879,915,943,964,979,989,995,998,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,4,14,34,69,125,209,329,494,714,996,1344,1759,2239,2779,3371,4004,4664,5334,5994,6627,7219,7759,8239,8654,9002,9284,9504,9669,9789,9873,9929,9964,9984,9994,9998,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,5,20,55,125,251,461,791,1286,2001,2997,4337,6082,8287,10997,14243,18038,22373,27213,32493,38124,43999,49999,55999,61874,67505,72785,77625,81960,85755,89001,91711,93916,95661,97001,97997,98712,99207,99537,99747,99873,99943,99978,99993,99998,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,99999,6,27,83,209,461,923,1715,3002,5004,8001,12333,18395,26627,37499,51491,69068,90650,116577,147069,182196,221858,265775,313487,364364,417626,472373,527625,582372,635634,686511,734223,778140,817802,852929,883421,909348,930930,948507,962499,973371,981603,987665,991997,994994,996996,998283,999075,999537,999789,999915,999971,999992,999998,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,7,35,119,329,791,1715,3431,6434,11439,19440,31767,50135,76679,113969,164999,233144,322079,435654,577719,751914,961439,1208819,1495679,1822544,2188679,2591984,3028959,3494754,3983319,4487634,4999999,5512364,6016679,6505244,6971039,7408014,7811319,8177454,8504319,8791179,9038559,9248084,9422279,9564344,9677919,9766854,9834999,9886029,9923319,9949863,9968231,9980558,9988559,9993564,9996567,9998283,9999207,9999669,9999879,9999963,9999991,9999998,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999,9999999};
	int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        cout<<a[n-1][k-1]<<endl;
    }
    return 0;
}