[TIOJ] 1361. 零的法則
題目連結:http://tioj.infor.org/problems/1361
卡了超久....寫了支暴搜對答案也看不出個所以然,最後才發現原來沒保證$a \leq b$,所以要判一下...
回到正題,觀察一下後會發現對於$[1, x]$中出現的0的個數,考慮個位時就是看$\lfloor \frac{x}{10^1} \rfloor$,但考慮十位時則是$\lfloor \frac{x}{10^2} \rfloor \times 10$,稍微想一下就可以推出考慮第$i$位時就是看$\lfloor \frac{x}{10^i} \rfloor \times 10^{i-1}$,不過要稍微注意一下邊界,若是不足$10^{i-1}$時要修正回來。
所以對於$[l, r]$做法就是用算$[0, r]-[0, l-1]$
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
inline int getSum(int);
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int l, r;
while(cin>>l>>r){
if(l>r) swap(l, r);
cout<<getSum(r)-getSum(l-1)<<'\n';
}
return 0;
}
inline int getSum(int x){
if(x<0) return 0;
int r=1;
for(lld i=10;i<=x;i*=10){
r += (x/i) * (i/10);
if((x%i)<(i/10)) r -= (i/10)-(x%i)-1;
}
return r;
}
留言
張貼留言