Poj 3286 How many 0's? + Bzoj 1833 count 数字计数（数位统计）

╰半夏微凉° 2023-01-04 15:56 95阅读 0赞

差不多的两道题，放在一起总结下。

第一题的分析可以参考：http://www.cnblogs.com/zhj5chengfeng/archive/2013/03/24/2977984.html

#include <cstdio>
    
    __int64 radix[15],n,m;
    
    __int64 Cal (__int64 x)
    {
    	if (x<0) return 0;
    	__int64 sum=1;   //第一个无符号整数是0
    	for (int i=1;radix[i]<=x;i++)
    	{
    		__int64 quo=x/radix[i];   //提取当前位左侧的值
    		__int64 rem=x%radix[i-1]; //提取当前位右侧的值
    		__int64 now=(x%radix[i]-x%radix[i-1])/radix[i-1]; //提取当前位
    		if (now==0)
    			sum+=(quo-1)*radix[i-1]+rem+1;
    		else
    			sum+=quo*radix[i-1];
    	}
    	return sum;
    }
    
    int main ()
    {
    	radix[0]=1;
    	for (int i=1;i<15;i++)
    		radix[i]=radix[i-1]*10;
    	while (scanf("%I64d%I64d",&m,&n), n!=-1 || m!=-1)
    		printf("%I64d\n", Cal(n)-Cal(m-1));
    	return 0;
    }

Bzoj 1833 count 数字计数

题目连接：http://61.187.179.132/JudgeOnline/problem.php?id=1833

比上一道稍微复杂一些

枚举0~9，从低到高枚举该数字在每一位上出现的次数，  
累加左边所有数的种数\*右边该位为该数字的种数。然后将多加的减掉  
比如562078  
某次j=1000,则对于千位,0可以出现56\*1000次,9可以出现57\*1000-1000次,2可以出现57\*1000-921次  
某次j=100,则对于百位,0可以出现562\*100-21次  
0与其他数的区别是左侧的数不能全部为0

#include <cstdio>
    #define __int64 long long
    
    __int64 ans[10];
    
    void Cal (__int64 x,int p)
    {
    	__int64 j;
    	for (j=1;j<=x;j*=10)
    	{
    		ans[0]+=x/(j*10)*j*p;
    		if (x%(j*10)/j==0)    //该位为0
    			ans[0]-=(j-x%j-1)*p;
    	}
    	for (int i=1;i<10;i++)
    		for (j=1;j<=x;j*=10)
    		{
    			ans[i]+=(x/(j*10)+1)*j*p;
    			int c=x%(j*10)/j;  //提取该位
    			if (c<i)
    				ans[i]-=j*p;
    			else  if (c == i)
    				ans[i]-=(j-x%j-1)*p;
    		}
    }
    
    int main ()
    {
    	__int64 a,b;
    	scanf("%lld%lld",&a,&b);
    	Cal(b,1);
    	if (a)
    		Cal(a-1,-1);
    	else
    		ans[0]++;
    	for (int i=0;i<10;i++)
    		printf(i==9?"%lld\n":"%lld ",ans[i]);
        return 0;
    }