自动搬运

查看原文

来自洛谷，原作者为

	wangyutian111 LIFE IS LIKE RIDING A BICYCLE. TO KEEP YOUR BALANCE , YOU MUST KEEP MOVING.

搬运于2025-08-24 22:20:00，当前版本为作者最后更新于2023-08-26 08:34:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

想法一：暴力

很明显，这道题第一反应就是暴力，枚举区间 $\left [ A,B \right ]$，逐位拆分，判断和是否等于 $S$，可以得到 $30$ 分。

代码：

#include<bits/stdc++.h>
#define int long long//开 long long
using namespace std;
signed main(){
	int a,b,s,minn,sum=0;
	scanf("%lld%lld%lld",&a,&b,&s);
	for(int i=a;i<=b;i++){//枚举 A 到 B
		int x=i,ans=0;
		while(x){
			ans+=x%10;
			x/=10;
		}
		if(ans==s){
			if(sum==0) minn=i;
			sum++;
		}
	}
	printf("%lld\n%lld",sum,minn);
	return 0;
}

想法二：正解

我们看一下数据范围：对于 $100\%$ 的数据，保证 $1\le A,B\le 10^{15}$，$1\le S\le 135$。

显然，枚举区间 $\left [ A,B \right ]$，时间复杂度过高。

前置信息：数位dp。

简单介绍一下数位 dp：

用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：

• 要求统计满足一定条件的数的数量（即，最终目的为计数）。

• 这些条件经过转化后可以使用「数位」的思想去理解和判断。

• 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制。

• 上界很大（比如 $10^{18}$），暴力枚举验证会超时。

——引用于 OI-WIKI

所以显然易见，这是一道数位 dp 模板题。

设 $f_{i,j}$ 表示前 $i$ 位数位和为 $j$ 的方案总数，随后跑模板即可。

第二问可以采用二分，如果 $l$ 到 $mid$ 之间有满足条件的数，就让 $r \gets mid-1$，否则让 $l \gets mid+1$。

AC 代码：

#include<bits/stdc++.h>
#define int long long//开 long long
using namespace std;
const int maxn=20,maxs=150;
int f[maxn][maxs]/*这里第二维要开maxs ，否则第三组样例过不去*/,digit[maxn];
int a,b,s;
int dfs(int pos,int pre,int limit,int lead){
	if(pos==0&&pre==s) return 1;
	if(pre+pos*9<s) return 0;	
	if(!lead&&!limit&&f[pos][pre]!=-1) return f[pos][pre];
	int sum=0,up;
	if(limit) up=digit[pos];
	else up=9;
	for(int i=0;i<=up;i++){
		if(pre+i>s) break;
		sum+=dfs(pos-1,pre+i,(limit&&i==up),lead&&(i==0));
	}
	if(!limit&&!lead) f[pos][pre]=sum;
	return sum; 
}
int solve(int x){
	memset(f,-1,sizeof(f));//清空
	memset(digit,0,sizeof(digit));
	int cnt=0;
	while(x){
		digit[++cnt]=x%10;
		x/=10;
	}
	return dfs(cnt,0,1,1);
}
signed main(){
	scanf("%lld%lld%lld",&a,&b,&s);
	int x=solve(a-1);
	printf("%lld\n",solve(b)-x);
	int l=a,r=b,ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(solve(mid)-x>0){//如果区间内还有满足条件的数字
			r=mid-1;//右指针左移
			ans=mid;//保存答案
		}
		else l=mid+1;//否则左指针右移
	}
	printf("%lld",ans);//输出答案
	return 0;//完美结束
}