InTheBloodHorse

每日一题(12) BZOJ1833

字数统计: 385阅读时长: 2 min
2018/09/23 Share

题目地址
题意:
给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次。
思路:
数位dp模版题,用dp[pos][sum][num]来表示在第pos位,目标是num,个数是sum时的值,但是有几个注意点
1:0 的时候要注意,因为 0000 没有意义,和之前二进制数位dp题一样
2:爆int了,这个有点不应该
3:传入0的时候,要特殊判断,只有0位,计算0的位数才有意义。(说不明白)
AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
int a[20];
long long dp[20][20][20];
long long dfs(int pos,int num,int sum,int sta,bool lim){
if(pos<0) return sum;
if(sta && !lim && dp[pos][num][sum]!=-1) return dp[pos][num][sum];
int up = lim ? a[pos]:9;
long long ans=0;
for(int i=0;i<=up;i++){
if(i==0){
if(sta || pos==0) ans+= dfs(pos-1,num,sum+ (num==i),sta || i,lim && i==a[pos]);
else ans+= dfs(pos-1,num,sum,0,lim && i==a[pos]);
}
else ans+= dfs(pos-1,num,sum+(num==i),1,lim && i==a[pos]);
}
if(!lim && sta) dp[pos][num][sum]=ans;
return ans;
}
long long solve(long long x,int num){
if(x<0) return 0;
if(x==0) return num==0?1:0;
int pos=0;
while(x){
a[pos++]=x%10;
x/=10;
}
return dfs(pos-1,num,0,0,true);
}
int main()
{
long long x,y;
scanf("%lld %lld",&x,&y);
memset(dp,-1,sizeof(dp));
for(int i=0;i<=8;i++){
printf("%lld ",solve(y,i)-solve(x-1,i));
}
printf("%lld\n",solve(y,9)-solve(x-1,9));
}

原文作者:InTheBloodHorse

原文链接:http://pyking.cn/2018/09/23/每日一题-12-BZOJ1833/

发表日期:September 23rd 2018, 8:24:19 pm

更新日期:September 23rd 2018, 8:33:22 pm

版权声明:Have a fun

CATALOG