網頁

2014年1月29日 星期三

UVa 11038 How many 0's?

題目連結
想法:
  將問題簡化為求1~m 0的總數,以及1~n 0的總數,然後最後再相減。
  求1~n 0的總數,要將n分別算每個位數0的個數,舉例如30324:
  • 先從右邊第一位'4'開始,其左邊為3032,表示1~30320在"第一位"總共有3032*1=3032個0
  • 換第二位數'2',其左邊為303,表示總共有303*10(右邊有1位)=3030個0
  • 再換第三位數也是一樣,30*100=3000個0,
  • 注意第四位數為'0',因此原本應該是3*1000,但第3個1000其實只到324而以,所以為2*1000+324+1=2325個0 (+1是因為別忘了0~324是325個)
  • 最後一位'3',它是最高位數,因此不會有0
  • 所以總共為3032+3030+3000+2325=11387
因此,此演算法從最低位(i==1)開始到最高位(i==k)結束,如果第i位不為0,直接左邊數字x10^(i-1),如果第i位為0,那麼(左邊數字-1)x10^(i-1)+右邊數字+1,最後把每位數的0總數加起來即可。