BZOJ1833 ZJOI2010 count 数字计数
Description
给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。
输入文件中仅包含一行两个整数a、b，含义如上所述。
Output
输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。
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位，我们要将答案加上
10pos−1
10
p
o
s
−
1
，然后处理一下上界特殊判断一下
恶心
using namespace std;
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;
}
