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

· · 题解

题目分析

就是给你 t 次询问，每次询问给你一个 n 和一个 k ，问你位数小于 n、位数之和小于 k 的正整数一共有多少个。

大体思路

虽然这道题的 n\le7 且 k\le100，但是他的查询次数 t\le10^5，暴力做法一定会超时，但是聪明的你一定一眼就看出来每一个 n 和 k 的组合方案数一定是一样的，所以我们就想到了用朴素算法打出一个 7\times100 的表的做法。

解题方法

这道题的朴素其实很好写，只需要枚举所有位数小于 n 的数字，挨个求出各位数和，与 k 作比较，如果 \le k，方案数就 +1。

朴素代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    int sum=1;
    int ans=0;
    for(int i=1;i<=n;i++){
        sum*=10;
    }//先求出n的位数，用来求出最大的限制 
    for(int i=1;i<=sum;i++){//枚举出来每一个可能的数字 
        int diao=0;
        int gg=i;
        while(gg){
            diao+=gg%10;
            gg/=10;//求出每一位的和 
        }
        if(diao<=k){
            ans++;
        }//如果小于k就代表可以，方案数++ 
    }
    cout<<ans-1;
    return 0;
}

这就是这道题的朴素代码且只能求 t=1 的情况，想让它成为大表哥，就必须对他进行一些改变：

#include<bits/stdc++.h>
using namespace std;
int main(){
    freopen("biao.out","w",stdout);
    for(int n=1;n<=7;n++){
        for(int k=1;k<=100;k++){
            int sum=1;
            int ans=0;
            for(int i=1;i<=n;i++){
                sum*=10;
            }
            for(int i=1;i<=sum;i++){
                int diao=0;
                int gg=i;
                while(gg){
                    diao+=gg%10;
                    gg/=10;
                }
                if(diao<=k){
                    ans++;
                }
            }
            cout<<ans-1<<",";
        }
    }
    return 0;
}

得到初始表之后我们把它折到一个数组中，就做出了表哥。

Code

#include<bits/stdc++.h>
using namespace std;
int b[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 main(){
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        int n,m;
        cin>>n>>m;
        cout<<b[n-1][m-1]<<endl;
    }
    return 0;
}

THE END!