Description
给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次。
Input
输入文件中仅包含一行两个整数a、b,含义如上所述。
Output
输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次。
Sample Input
1 99
- 1
Sample Output
9 20 20 20 20 20 20 20 20 20
- 1
HINT
30%的数据中,a<=b<=10^6;
100%的数据中,a<=b<=10^12。
Source
Day1
简单的数位DP,但我浪费了好多时间,一开始的一直答案错误,改了好几遍前导0,结果竟然是tmp忘加longlong了啊啊啊啊
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[30];
ll dp[30][30][30];
ll dfs(int pos,int sta,int lead,int limit,int y){if(pos==-1){return sta;};if(!limit&&!lead&&dp[pos][y][sta]!=-1) return dp[pos][y][sta];int up=limit?a[pos]:9;ll tmp=0;for(int i=0;i<=up;i++){if(lead==1&&i==0){tmp+=dfs(pos-1,sta,lead,limit&&i==up,y);}else tmp+=dfs(pos-1,sta+(y==i),lead && i==0,limit&&i==up,y);}if(!limit&&!lead) dp[pos][y][sta]=tmp;return tmp;
}ll solve(ll x,int i)
{int pos=0;while(x){a[pos++]=x%10;x/=10;}return dfs(pos-1,0,true,true,i);
}
int main()
{ll n,m;scanf("%lld%lld",&n,&m);memset(dp,-1,sizeof(dp));for(int i=0;i<10;i++) {if(i!=9)printf("%lld ",solve(m,i)-solve(n-1,i));elseprintf("%lld\n",solve(m,i)-solve(n-1,i));} return 0;
}