P6356 CUDAK-题解

wangyutian111 · 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;//完美结束
}