【洛谷P2602】数字计数

题目大意：求 [a,b] 中 0-9 分别出现了多少次。

题解：看数据范围应该是一个数位dp。

在 dfs 框架中维护当前的位置和到当前位置一共出现了多少个 \(x,x\in [0,9]\)。因此，用一个 dp[][] 数组记录一下状态即可，dp 的含义大概是前 i 位中出现了 j 个 x 的总 x 的个数是多少。

代码如下

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;LL dp[15][15];
int digit[15],tot,now;LL dfs(int cur,int sum,bool lead,bool limit){
if(cur==0)return sum;
if(!lead&&!limit&&dp[cur][sum]!=-1)return dp[cur][sum];
LL ret=0;
int bit=limit?digit[cur]:9;
for(int i=0;i<=bit;i++){
if(!i&&lead)ret+=dfs(cur-1,sum,1,limit&&i==bit);
else if(i==now)ret+=dfs(cur-1,sum+1,0,limit&&i==bit);
else ret+=dfs(cur-1,sum,0,limit&&i==bit);
}
if(!lead&&!limit)dp[cur][sum]=ret;
return ret;
}
LL part(LL x){
tot=0;
memset(digit,0,sizeof(digit));
do{
digit[++tot]=x%10;
x/=10;
}while(x);
memset(dp,-1,sizeof(dp));
return dfs(tot,0,1,1);
}
int main(){
LL a,b;
cin>>a>>b;
for(int i=0;i<9;i++)now=i,printf("%lld ",part(b)-part(a-1));
now=9,printf("%lld\n",part(b)-part(a-1));
return 0;
}