BZOJ1833 ZJOI2010 count 数字计数 【数位DP】

xiaoxiao2021-02-28  5

BZOJ1833 ZJOI2010 count 数字计数


Description

给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次。

Input

输入文件中仅包含一行两个整数a、b,含义如上所述。

Output

输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次。

Sample Input

1 99

Sample Output

9 20 20 20 20 20 20 20 20 20

HINT

30%的数据中,a<=b<=10^6; 100%的数据中,a<=b<=10^12。


数位DP嘛,虽然是模板题但还是满满的毒瘤感觉,如果不考虑上界的问题,很显然相同位数每一个字符出现次数是一样的,这样我们就只用 dp[x] d p [ x ] 表示第i位的时候所有数的出现次数,然后在搜索的时候我们就考虑一下上界问题,就好了

唔 还有一些恶心的细节问题。。我们不是从高位开始搜的嘛,然后注意一下如果当前为i==目标数字且处在pos位,我们要将答案加上 10pos1 10 p o s − 1 ,然后处理一下上界特殊判断一下


恶心


#include<bits/stdc++.h> using namespace std; #define LL long long LL dp[20],p[20],cnt[20],w[20],c[20]; LL dfs(int dig,int pos,bool front,bool up){ if(!pos)return 0; if(!front&&!up&&dp[pos])return dp[pos]; int tmp=up?p[pos]:9; LL ans=0; for(int i=0;i<=tmp;i++){ if(!i&&front)ans+=dfs(dig,pos-1,1,up&&i==tmp); else if(i==dig){ if(i==tmp&&up)ans+=c[pos-1]+1+dfs(dig,pos-1,0,1); else ans+=w[pos-1]+dfs(dig,pos-1,0,0); }else ans+=dfs(dig,pos-1,0,up&&i==tmp); } if(!front&&!up)dp[pos]=ans; return ans; } void solve(LL t,LL typ){ memset(dp,0,sizeof(dp)); LL len=0; while(t){ p[++len]=t; t/=10; c[len]=c[len-1]+w[len-1]*p[len]; } for(int i=0;i<=9;i++)cnt[i]+=dfs(i,len,1,1)*typ; } int main(){ w[0]=1;for(int i=1;i<=15;i++)w[i]=w[i-1]*10; LL a,b;scanf("%lld%lld",&a,&b); solve(b,1);solve(a-1,-1); for(LL i=0;i<=9;i++)printf("%lld ",cnt[i]); return 0; }
转载请注明原文地址: https://www.6miu.com/read-2150124.html

最新回复(0)