计数小于等于N的整数中数字0的出现次数-CSDN博客

本文链接：https://blog.csdn.net/acm_fighting/article/details/51798587

4148. number 0

Time Limit: 1.0 Seconds Memory Limit: 65536K

Given an integer N, count the total number of digit 0 appearing in all positive integers less than or equal to N.

Input

The input consists of multiple test cases. The first line contains an integer T , indicating the number of test cases.(1<=T<=1000)

Each case contains only one integer N(1<=N<=1e8)

Output

For each case output only one number.

Sample Input

Sample Output

0
1
453979

思路一:

先预处理出1000000中不含前导0的数目和形成的六位数<=i且包含前导0的个数

那么如果这个数是7位数,我们只需要枚举它的第一位,如果是8位数,我们只需要枚举它的前两位,如果是9位数,先转化为8位数

思路二:

对每一位进行讨论,分析这一位i为0,前i-1位和后面的位数合起来的总共的方案数为多少

思路一代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1001000;
int dp[maxn],dp1[maxn];//dp1表示小于等于i后面6位
int P[10];
char s[10];

int main(){
    dp1[0]=6,dp1[1]=11;
    for(int i=2;i<1000000;i++){
        int num=i,Count=0;
        dp[i]=dp[i-1];
        dp1[i]+=dp1[i-1];
        while(num){
            if(num%10==0)
                dp[i]++,dp1[i]++;
            num/=10;
            Count++;
        }
        dp1[i]+=(6-Count);
    }
    int _,n;
    scanf("%d",&_);
    while(_--){
        scanf("%s",&s);
        n=atoi(s);
        if(n<1000000){
            printf("%d\n",dp[n]);
            continue;
        }
        int ans=0;
        if(n==100000000){
            for(int i=0;i<=7;i++)
                s[i]='9';
            ans+=8;
        }
        ans+=dp[999999];
        if(n<=9999999){
            for(int i=1;i<=9;i++){
                if(s[0]-'0'<i)
                    break;
                if(s[0]-'0'==i){
                    int num=0;
                    for(int j=1;j<=6;j++)
                        num=num*10+s[j]-'0';
                    ans+=dp1[num];
                }
                else
                    ans+=dp1[999999];
            }
        }
        else{
            for(int i=0;i<=9;i++){
                if(s[0]-'0'<i)
                    break;
                if(s[0]-'0'==i){
                    int j=(i==0 ? 1:0);
                    for(;j<=9;j++){
                        if(s[1]-'0'<j)
                            break;
                        if(s[1]-'0'==j){
                            int num=0;
                            for(int k=2;k<=7;k++)
                                num=num*10+s[k]-'0';
                            ans+=dp1[num];
                            if(j==0)
                                ans+=num+1;
                        }
                        else{
                            ans+=dp1[999999];
                            if(j==0)
                                ans+=999999+1;
                        }
                    }

                }
                else{
                    int j=(i==0 ? 1:0);
                    for(;j<=9;j++){
                        ans+=dp1[999999];
                        if(j==0)
                            ans+=999999+1;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

思路二代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=10;
int suf[maxn],pre[maxn],P[maxn];
char s[10];

int main(){
    int _,n,len,ans;
    P[0]=1,P[1]=10;
    for(int i=2;i<=9;i++)
        P[i]=P[i-1]*10;
    scanf("%d",&_);
    while(_--){
        scanf("%s",s+1);
        len=strlen(s+1),n=0,suf[0]=0;
        for(int i=1;i<=len;i++)
            pre[i]=pre[i-1]*10+s[i]-'0';
        n=pre[len],ans=0;
        suf[len+1]=0;
        for(int i=len;i>=1;i--)
            suf[i]=suf[i+1]+(s[i]-'0')*P[len-i];
        for(int i=2;i<=len;i++){
            ans+=(pre[i-1]-1)*P[len-i]; //前面i-1位即小于原来的值且不为0
            if(s[i]=='0')   //s[i]原来为0,后面的位数不能随便取
                ans+=suf[i+1]+1;
            else            //s[i]原来不为0,后面的位数不能随便取
                ans+=P[len-i];
        }
        printf("%d\n",ans);
    }
    return 0;
}

toj 4148