[TIOJ] 1361. 零的法則
題目連結:http://tioj.infor.org/problems/1361
卡了超久....寫了支暴搜對答案也看不出個所以然,最後才發現原來沒保證a≤b,所以要判一下...
回到正題,觀察一下後會發現對於[1,x]中出現的0的個數,考慮個位時就是看⌊x101⌋,但考慮十位時則是⌊x102⌋×10,稍微想一下就可以推出考慮第i位時就是看⌊x10i⌋×10i−1,不過要稍微注意一下邊界,若是不足10i−1時要修正回來。
所以對於[l,r]做法就是用算[0,r]−[0,l−1]
留言
張貼留言