HDU1663The Counting Problem

最新推荐文章于 2020-01-27 14:36:02 发布

Y幽谷客

最新推荐文章于 2020-01-27 14:36:02 发布

阅读量502

点赞数

本文链接：https://blog.csdn.net/daima66699/article/details/73770703

版权

本文介绍了一种高效的算法来计算两个整数之间每个数字0到9出现的频率。通过分解数字并统计不同位上数字的出现次数，该算法能够快速解决此类问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Given two integers a and b, we write the numbers between a and b, inclusive, in a list. Your task is to calculate the number of occurrences of each digit. For example, if a = 1024 and b = 1032, the list will be

1024 1025 1026 1027 1028 1029 1030 1031 1032

there are ten 0’s in the list, ten 1’s, seven 2’s, three 3’s, and etc.

Input
The input consists of up to 500 lines. Each line contains two numbers a and b where 0 < a, b < 100000000. The input is terminated by a line `0 0’, which is not considered as part of the input.

Output
For each pair of input, output a line containing ten numbers separated by single spaces. The first number is the number of occurrences of the digit 0, the second is the number of occurrences of the digit 1, etc.

Sample Input

1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0

Sample Output

1 2 1 1 1 1 1 1 1 1
85 185 185 185 190 96 96 96 95 93
40 40 40 93 136 82 40 40 40 40
115 666 215 215 214 205 205 154 105 106
16 113 19 20 114 20 20 19 19 16
107 105 100 101 101 197 200 200 200 200
413 1133 503 503 503 502 502 417 402 412
196 512 186 104 87 93 97 97 142 196
398 1375 398 398 405 499 499 495 488 471
294 1256 296 296 296 296 287 286 286 247

纯数学：
求给定区间的数字（0-9）出现的次数也可以这样求解。

///首先的思路是求出[1,n]中0~9出现的次数，这样用solve[1,b]-solve[1,a-1]就是solve[a,b]，下面先以4321为例计算[1,4321]中2出现的次数
///个位为0 左边的可能值为1~432，右边没有数字，所以是432*1
///十位为0 左边的可能值为1~43时，右边可能值为0~9所以是43*10
///百位为0 左边可能值1~4，右边可能值为0~99，所以是4*100


///个位为1 左边的可能值为0~432，右边没有数字，所以是433*1
///十位为1 左边的可能值为0~43时，右边可能值为0~9所以是44*10
///百位为1 左边可能值为0~4，右边可能值为0~99，所以是5*100
///千位为1 左边没有数字，右边可能值为0~999，所以是1*1000

///个位为2 左边的可能值为0~431，右边没有数字，所以是432*1
///十位为2 左边的可能值为0~42时，右边可能值为0~9，左边为43时，右边可能值为0~1，所以是43*10+1*2
///百位为2 左边可能值为0~4，右边可能值为0~99，所以是5*100
///千位为2 左边没有数字，右边可能值为0~999，所以是1*1000


///个位为3 左边的可能值为0~431，右边没有数字，所以是432*1
///十位为3 左边的可能值为0~42时，右边可能值为0~9，所以是43*10
///百位为3 左边可能值为0~3，右边可能值为0~99，所以是4*100+1*22
///千位为3 左边没有数字，右边可能值为0~999，所以是1*1000

///个位为4 左边的可能值为0~431，右边没有数字，所以是432*1
///十位为4 左边的可能值为0~42时，右边可能值为0~9，所以是43*10
///百位为4 左边可能值为0~3，右边可能值为0~99，所以是4*100
///千位为4 左边没有数字，右边可能值为0~321，所以是1*322
///以此类推，1~9的计算情况与2相同，而0的数量因为存在前置0的情况，所以每次把当前位左边的可能值减一即可
/*
/第一种方法
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll ans[10];
void count_num(ll number)
{
    ll ren=1,dang=0;///dang表示当前位右边的数值,ren表示当当前位右边可以任意取时的情况数
    while(number>0)
    {
        ll temp=number%10;///从最低位往最高位累计
        number/=10;
        for(int i=0;i<10;i++)
        {
            if(temp>i)///如果当前位的值大于要计算的数字
            {
                ans[i]+=number*ren;
                if(i) ans[i]+=ren;
            }
            else if(temp==i)///如果当前位的值等于要计算的数字
            {
                if(number&&i==0)
                    ans[i]+=(number-1)*ren+dang+1;
                else if(i>0)
                    ans[i]+=number*ren+dang+1;
            }
            else if(temp<i)///如果当前位的值小于要计算的数字
                ans[i]+=number*ren;
        }
        dang+=temp*ren;
        ren*=10;
    }
}

/第2种方法
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
ll  b[9] = { 1, 10, 100, 1000, 10000, 100000, 1000000,10000000, 100000000 };
ll count_num ( ll n, ll id )
{
    ll ans, m, sum = 0;
    for ( int i = 1; i < 9; i++ )
    {
        ans = n / b[i] - (id==0);///判断尾数是否为0 若为0 就需要减1 上面规律课以发现
        sum += ans * b[i-1];
        m = (n % b[i] - n % b[i-1]) / b[i-1]; ///求出每一位
        if ( m > id ) sum += b[i-1];
        else if ( m == id ) sum += n % b[i-1] + 1;
        if ( n < b[i] ) break;
    }
    return sum;
}
int main()
{
    ll n,m,f;
    ll a[10];
    int i;
    while(cin>>n>>m,n,m)
    {
        if(n>m) swap(n,m);
        for(i=0; i<=9; i++)
        {
            a[i]=count_num(m,i)-count_num(n-1,i);
        }
        for(i=0; i<9; i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<a[9]<<endl;
    }
}
int main()
{
    ll a,b;
    while(cin>>a>>b,a,b)
    {
        if(a>b) swap(a,b);
        memset(ans,0,sizeof(ans));
        count_num(a-1);
        for(int i=0;i<10;i++)
            ans[i]=-ans[i];
            count_num(b);
        for(int i=0;i<10;i++)
            printf("%lld%c",ans[i],i==9? '\n':' ');
    }
    return 0;

}
*/