[TIOJ] 1361. 零的法則

題目連結:http://tioj.infor.org/problems/1361

卡了超久....寫了支暴搜對答案也看不出個所以然,最後才發現原來沒保證ab,所以要判一下...

回到正題,觀察一下後會發現對於[1,x]中出現的0的個數,考慮個位時就是看x101,但考慮十位時則是x102×10,稍微想一下就可以推出考慮第i位時就是看x10i×10i1,不過要稍微注意一下邊界,若是不足10i1時要修正回來。

所以對於[l,r]做法就是用算[0,r][0,l1]

#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;
}
C++

留言

這個網誌中的熱門文章

[TIOJ] 1094. C.幼稚國王的獎賞

[IOJ] 19. 啦啦啦

[IOJ] 14. 費氏數列問題