自动搬运

查看原文

来自洛谷，原作者为

	IGA_Indigo 想，都是问题；做，才是答案。

搬运于2025-08-24 21:28:10，当前版本为作者最后更新于2024-03-11 14:22:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

就是给你 $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!