luogu P2602 [ZJOI2010]数字计数

P2602 [ZJOI2010]数字计数

一眼：数位dp

等等，先来个暴力再说

枚举l~r的数字

对于每个数字求出它每位位值

时间复杂度 O(k(r-l)) k为数字位数（常数，最大12）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll l,r;
ll a[11];
void add(ll u){
    while(u>0){
        a[u%10]++;
        u/=10;
    }
}
int main(){
    cin >> l >> r;
    for(ll i=l;i<=r;i++){
        add(i);
    } 
    for(int i=0;i<10;i++) printf("%d ",a[i]);
    printf("\n");
    return 0;
}
           

30分

浙江省选，30分，很不错了！

我们怎么能不思进取？

考虑数位dp

然后如果您想用数位dp做，请移步其他博客。

我只会小奥

枚举数字

l~r的sum=sum[r]-sum[l-1]

至于如何算sum(当然，我们不会用数组，因为开不下)，可以分位算

0要特判

std:(丑陋)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll l,r;
ll work(int x,ll u){
    if(u==0&&x==0) return 1;
    ll ans=0;
    int lll=0;
    int a[15];
    ll v=u;
    while(u>0){
        a[++lll]=u%10;
        u/=10;
    }
    if(x==0){
        ll ans=0;
        for(int i=1;i<lll;i++){
            ll sum=0;
            ll mul=1;
            ll mmm=1;
            ll rs=0;
    for(int j=1;j<i;j++){
              rs+=9*mmm;
              mmm*=10;
    }
            if(x<a[i]){
                for(int j=1;j<=lll;j++){
                    if(i==j) continue;
                    else if(j<i) sum+=9*mul; 
                    else sum+=(ll)a[j]*mul;
                    mul*=10;
                }
            }
            else{
                for(int j=1;j<=lll;j++){
                    if(i==j) continue;
                    sum+=(ll)a[j]*mul;
                    mul*=10;
                }
            } 
            ans+=sum-rs;
        }
        return ans+1;
    }
    for(int i=1;i<=lll;i++){//确定位数
        if(i==lll&&a[lll]<x) break; 
        ll sum=0;
        ll mul=1;
        if(x>a[i]){
            for(int j=1;j<i;j++){
                sum+=9*mul; 
                mul*=10;
            }
            sum+=(ll)(a[i+1]-1)*mul;
            mul*=10;
            for(int j=i+2;j<=lll;j++){
                sum+=(ll)a[j]*mul;
                mul*=10;
            }
        } 
        else if(x<a[i]){
            for(int j=1;j<i;j++){
                sum+=9*mul; 
                mul*=10;
            }
            for(int j=i+1;j<=lll;j++){
                sum+=(ll)a[j]*mul;
                mul*=10;
            }
        }
        else{
            for(int j=1;j<=lll;j++){
                if(i==j) continue;
                sum+=(ll)a[j]*mul;
                mul*=10;
            }
        } 
        sum++;
        ans+=sum;
    }
    return ans;
}
int main(){
 //freopen("a.in","r",stdin);
 //freopen("a.out","w",stdout);
    cin >> l >> r;
    for(int i=0;i<10;i++){
        cout << work(i,r)-work(i,l-1) << " ";
        
    } 
    cout << endl;
    return 0;
}
           

至此完结

才怪

这题还要注意：

开longlong!

真·完结