題目簡述:給兩個數字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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
