POJ 2282 – The Counting Problem 3252 round numbers

两个都是麻烦的计数问题,只不过一个是二进制,另一个似乎更贴近十进制的现实世界.不过计算机里,还是二进制感觉能跑得更快一些,移位总比乘十来得更快一些. 计数从0-n的每一位的数字个数,先计数位数小于n的位数的数字个数,再从高位到低位依次循环累加计数和n位数相同且小于n的数的各位数字.考虑的情形很多,有一点考虑不到就很难得到正确答案.

/*Source Code

Problem: 2282  User: y09shendazhi 

Memory: 220K  Time: 16MS 

Language: C++  Result: Accepted 

Source Code */

#include <iostream>

using namespace std;

int ans[15];//answer

int pow(int a,int b)

{

    int an=1;

    for(int i=0;i<b;i++)

        an*=a;

    return an;

}

void solve(int n)

{

    int i,j,k;

    memset(ans,0,sizeof(ans));

    if(n<10)

    {

        for(i=1;i<=n;i++)

            ans[i]=1;

        return ;

    }

    int digit[20]={0};

    int dec=0;//decimal of n

    int temp=0;

    temp=n;

    while(temp)

    {

        digit[dec++]=temp%10;

        temp/=10;

    }

    temp=pow(10,dec-1);

    for(i=1;i<10;i++)//位数小于n的

        ans[i]+=(dec-1)*temp/10;

    ans[0]+=(dec-1)*temp/10-(temp-1)/9;

    for(i=1;i<digit[dec-1];i++)//最高位是  1~最高位

    {

        ans[i]+=temp;

        for(k=0;k<10;k++)

            ans[k]+=(dec-1)*temp/10;

    }

    temp/=10;

    for(i=dec-2;i>=0;i--)

    {

        for(j=0;j<digit[i];j++)

        {

            for(k=dec-1;k>i;k--)

                ans[digit[k]]+=temp;

            ans[j]+=temp;

            for(k=0;k<10;k++)

                ans[k]+=i*temp/10;

        }

        temp/=10;

    }

    for(i=0;i<dec;i++)

        ans[digit[i]]++;

}

int main(int argc, char *argv[])

{

    int n,m;

    int ans1[15]={0};

    int temp=0;

    while(cin>>n>>m)

    {

        if(n==0 && m==0)

            break;

        if(n>m)

        {

            temp=n;

            n=m;

            m=temp;

        }

        solve(n-1);

        memcpy(ans1,ans,sizeof(ans));

        solve(m);

        for(int i=0;i<9;i++)

            cout<<ans[i]-ans1[i]<<' ';

        cout<<ans[9]-ans1[9]<<endl;

    }

    return 0;

}