題目簡(jiǎn)述：給兩個(gè)數(shù)字a和b，求a和b之間的所有數(shù)中k出現(xiàn)的次數(shù)總和。比如1和11之間，1出現(xiàn)的次數(shù)為4（1,10,11共4個(gè)1）。
?
輸入：若干組數(shù)據(jù)，每行三個(gè)整數(shù)，a，b，k。以0 0結(jié)尾。（0<a,b<100 000 000,0<=k<=9)
輸出：輸出k出現(xiàn)的次數(shù)總和。
?
解題思路：分治策略。可以分別考慮從0到a和b的這些數(shù)中，k出現(xiàn)的次數(shù)和，再做減法。 以197和k=1為例，先考慮190~197這8個(gè)數(shù)，個(gè)位1出現(xiàn)一次；其他數(shù)位上百位有1個(gè)1,8個(gè)數(shù)一共1*8個(gè)1。0~189這些數(shù)中，個(gè)位1出現(xiàn)19次。再之后，就不需要考慮個(gè)位上的1了，value可以安心*10了。如果是0的話，要特殊處理。（因?yàn)槭粸?的000和個(gè)位為0的000是一種情況，而十位為1的010和個(gè)位為1的001是兩種情況。）value*10后，就開(kāi)始考慮十位上的1了。這個(gè)時(shí)候，考慮的數(shù)是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;
//
先看個(gè)位
49
while
(ten){
//
十位以上的每個(gè)數(shù)對(duì)應(yīng)one+1個(gè)個(gè)位數(shù)變化
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
;
//
變權(quán)
57
Deal(n-
1
);
58
}
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
