AcWing 1082. 数字游戏
原题链接
中等
作者:
最后五分钟
,
2025-04-03 00:09:02
· 江西
,
所有人可见
,
阅读 3
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=45;
int f[N][10];
int dp(int t)
{
vector<int> num;
do{
num.push_back(t%10),t/=10;
}while(t);
int ls=0;
int res=0;
for(int i=num.size()-1;~i;i--)
{
int x=num[i];
if(x<ls)break;
for(int j=ls;j<x;j++)
{
res+=f[i+1][j];
}
ls=x;
if(!i)res++;
}
return res;
}
void init()
{
for(int i=0;i<=9;i++)f[1][i]=1;
for(int i=2;i<N;i++)
for(int j=0;j<=9;j++)
for(int k=9;k>=j;k--)
f[i][j]+=f[i-1][k];
}
signed sol(int l,int r)
{
cout<<dp(r)-dp(l-1)<<endl;
}
signed main()
{
int l,r;
init();
while(cin>>l>>r)
{
sol(l,r);
}
return 0;
}