4401: 优美数-白红宇

4401: 优美数

阅读量：5132 次

发布时间：2019-06-13

本文共 1385 字，大约阅读时间需要 4 分钟。

链接

[]

题意

Description

如果一个数中只有少于三个数字是非零的，那么我们称这个数为优美数，我们定义这个优美数的优美程度为这个数所有数字相加的和。例如优美数有4，200000，10203，其中4的优美度是4，200000的优美度是2，10203的优美度是6. 数字4231，102306，7277420000，就不是啰。

现在问在【L，R】中，有多少个优美度为x的优美数。

Input

T组数据，T<=5e4. 第一行为组数T。接下来T行，每组输入L，R，x。1<=L <= R <= 3e18;

Output

每行输出一个对应的答案

Sample Input

1 1000 1

1024 1024 7

65536 65536 15

1 1000000000 20

Sample Output

3024

分析

数位DP

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define ll long longusing namespace std;int a[30];ll dp[20][30][4][30];int k;ll dfs(int pos,int now,int num,bool limit){//pos当前位数，now现在位数之和，num非零位的个数，limit判断是否到达上限     if(num > 3) return 0;    if(pos==-1) return now == k;    if(!limit && dp[pos][now][num][k]!=-1) return dp[pos][now][num][k];    int up=limit?a[pos]:9;    ll ans=0;    for(int i=0;i<=up&&now+i<=k;++i){       ans+=dfs(pos-1,now+i,num+(i!=0),limit&&i==a[pos]);    }    if(!limit) dp[pos][now][num][k]=ans;    return ans;}ll solve(ll x){    int pos=0;    if(x==0)return 0;    while(x){        a[pos++]=x%10;        x/=10;    }    return dfs(pos-1,0,0,1);}int main(){    int T;    //freopen("in.txt","r",stdin);     cin>>T;    memset(dp,-1,sizeof(dp));    while(T--){        ll l,r;        cin>>l>>r>>k;        if(k>27) cout<<0<

转载于:https://www.cnblogs.com/mch5201314/p/9922255.html

你可能感兴趣的文章