当前位置: 代码迷 >> 综合 >> 原 [BZOJ 1833][ZJOI 2010]count数字计数( 前导0数位DP 模板)
  详细解决方案

原 [BZOJ 1833][ZJOI 2010]count数字计数( 前导0数位DP 模板)

热度:32   发布时间:2024-01-15 07:35:02.0

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;
}

 

  相关解决方案