題目簡述：給兩個數字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
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
