计数问题

计数问题

TimeLimit: 1 Second   MemoryLimit: 32 Megabyte

Totalsubmit: 1712   Accepted: 193  

Description

给你两个数a和b,你的任务是计算出1在a和b之间出现的次数,比如说，如果a=1024,b=1032，那么a和b之间的数就是：

1024 1025 1026 1027 1028 1029 1030 1031 1032

则有10个1出现在这些数中。

Input

输入不会超过500行。每一行有两个数a和b，a和b的范围是0 < a, b < 100000000。输入两个0时程序结束，两个0不作为输入样例。

Output

对于每一对输入的a和b，输出一个数，代表1出现的个数。

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

2
185
40
666
113
105
1133
512
1375
1256

 解题思路

　　本题可以先求1在0~a之间出现的次数，再求出1在0~b-1之间出现的次数，相减即可。

将0~197的数列出来后可以看出规律：
　　①可以求出1在190~197之间出现的次数，然后对于0~180.190~197中1在个位数上出现了1次。

　　②个位考虑完以后，直接考虑197/10-1（即18）中1出现的次数，同时考虑数字减小了，每一位的权值会增加，也就是说一个数字出现的次数会增加10倍。

/*本算法算出了0~9在a和b之间分别出现的次数，取答案时直接取d[1]即可*/
#include <iostream>
using namespace std;
/*****************************************************************/
const int N = 11;
int d[N];         //d[N]存储0~9分别出现的次数
int value;        //记录相应权值的变化
void deal(int n);
/****************************************************************/

void deal(int n)
{
    if ( n <= 0 )
    {
        return ;
    }
    int one, ten;
    one = n % 10;  //one，tenden别代表个位和十位
    n /= 10;
    ten = n;
    for ( int i = 0; i <= one; i++ )//将个位上出现的数统计下来
    {
        d[i] += value;
    }
    while ( ten )//十位上的数在one的前提下出现的次数
    {
        d[ten % 10] += (one + 1) * value;
        ten /= 10;
    }
    for ( i = 0; i < 10; i++ )//根据权值统计0~9出现的次数
    {
        d[i] += value * n;
    }
    d[0] -= value;//将第一位是0的情况排除
    value *= 10;//权值变化10倍
    deal (n-1);
}

int main()
{
    int a, b;
    while ( cin >> a >> b)
    {
        if ( a == 0 && b== 0)
        {
            break;
        }            
        if ( a < b)
        {
            int tmp = b;
            b = a;
            a = tmp;
        }
        for (int i = 0; i < 10; i++)
        {
            d[i] = 0;
        }
        value  =1;
        deal(a);
        value = -1;//此处value=-1是为了求出最后的答案deal(a)-deal(b)
        deal(b - 1);
        cout << d[1]<< endl;
    }
    system ("pause");
    return 0;
}