P2602 [ZJOI2010]数字计数（递推+数位dp写法）

P2602 [ZJOI2010]数字计数

递推写法：

主要观察到对于所有小于1000的数每一个数字1，2，3,...都是平均出现的（不考虑前导零）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
#define debug(x) cout<<#x<<':'<<x<<endl;
int bits[maxn];
ll dp_up[maxn],dp_down[maxn],zahn[maxn],a,b;
void solve(long long x,long long *dp)
{
    int len=-1;ll tempnum=x;
    for(ll i=x;i;i/=10) bits[++len]=i%10;
    for(int i=len;i>=0;i--){
        for(int j=0;j<=9;j++)   dp[j]+=i*(zahn[i]/10)*bits[i];//后面的位数是平均的
        for(int j=0;j<bits[i];j++)  dp[j]+=zahn[i];//当前首位的贡献
        dp[bits[i]]+=(tempnum-=zahn[i]*bits[i])+1;
        dp[0]-=zahn[i];//按位处理前导零
    } 
}
int main()
{
    scanf("%lld %lld",&a,&b);
    zahn[0]=1;
    for(int i=1;i<=15;i++)zahn[i]=10*zahn[i-1];
    solve(a-1,dp_down);
    solve(b,dp_up);
    for(int i=0;i<=9;i++)
    printf("%lld ",dp_up[i]-dp_down[i]);
    system("pause");
}

数位dp写法：

1.要考虑前导零

2.要记得dp每次赋值为-1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<#x<<':'<<x<<endl;
const int maxn=25;
ll dp[maxn][2][2][10][maxn],bitsa[maxn],bitsb[maxn],a,b;
ll dfs(int pos,int lim,int lead,int dig,ll sum ,ll *bits){//lead为0表示有前导零
    if(pos==0) return sum;//处理边界
    ll &ans=dp[pos][lim][lead][dig][sum];//数位dp本质记忆化搜索
    if(ans!=-1) return ans;
    else ans=0;
    int up=lim?bits[pos]:9;
    for(int i=0;i<=up;i++){
        ans+=dfs(pos-1,(i==up)&&lim,lead||i,dig,sum+((i||lead)&&(i==dig)),bits);
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&a,&b);
    int lena=0;a--;
    for(ll i=a;i;i/=10) bitsa[++lena]=i%10;
    int lenb =0;
    for(ll i=b;i;i/=10)bitsb[++lenb]=i%10;
    for(int i=0;i<=9;i++){memset(dp,-1,sizeof(dp));
        ll ans=dfs(lenb,1,0,i,0,bitsb);memset(dp,-1,sizeof(dp));
        ans-=dfs(lena,1,0,i,0,bitsa);
        printf("%lld ",ans);
    }
    //system("pause");
}