题目简述：给两个数字a和b，求a和b之间的所有数中k出现的次数总和。比如1和11之间，1出现的次数为4（1,10,11共4个1）。
输入：若干组数据，每行三个整数，a，b，k。以0 0结尾。（0<a,b<100 000 000,0<=k<=9)
输出：输出k出现的次数总和。
解题思路：分治策略。可以分别考虑从0到a和b的这些数中，k出现的次数和，再做减法。 以197和k=1为例，先考虑190~197这8个数，个位1出现一次；其他数位上百位有1个1,8个数一共1*8个1。0~189这些数中，个位1出现19次。再之后，就不需要考虑个位上的1了，value可以安心*10了。如果是0的话，要特殊处理。（因为十位为0的000和个位为0的000是一种情况，而十位为1的010和个位为1的001是两种情况。）value*10后，就开始考虑十位上的1了。这个时候，考虑的数是100~189。一直下去......
代码：
1
#include <iostream>
2
#include <fstream>
3
#include <cstdio>
4
using
namespace
std;
5
6
#define
ll long long
7
8
ll value,ans;
9
int
k;
10
11
inline
void
Swap(
int
&a,
int
&
b);
12
void
Deal(
int
n);
13
14
int
main(){
15
//
freopen("D:\\input.in","r",stdin);
16
int
a,b;
17
while
(scanf(
"
%d %d %d
"
,&a,&b,&
k),a){
18
if
(a==
b){
19
ans=
0
;
20
while
(a){
21
value=a%
10
;
22
if
(value==k) ans++
;
23
a/=
10
;
24
}
25
}
else
{
26
if
(a<
b) Swap(a,b);
27
ans=
0
;
28
value=
1
;
29
Deal(a);
30
value=-
1
;
//
Deal(a)-Deal(b)
31
Deal(b-
1
);
32
}
33
printf(
"
%lld\n
"
,ans);
34
}
35
return
0
;
36
}
37
inline
void
Swap(
int
&a,
int
&
b){
38
int
t=
a;
39
a=
b;
40
b=
t;
41
}
42
void
Deal(
int
n){
43
if
(n<=
0
)
return
;
44
int
one,ten,tmp;
45
one=n%
10
;
46
n/=
10
;
47
ten=
n;
48
if
(one>=k) ans+=value;
//
先看个位
49
while
(ten){
//
十位以上的每个数对应one+1个个位数变化
50
tmp=ten%
10
;
51
if
(tmp==k) ans+=value*(one+
1
);
52
ten/=
10
;
53
}
54
ans+=value*n;
//
比如197，考虑十位以上0~18.
55
if
(k==
0
) ans-=value;
//
将第一位是0的情况排除
56
value*=
10
;
//
变权
57
Deal(n-
1
);
58
}
