[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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology