Codeforces 205D - Little Elephant and Interval 题解

2020-02-21 数学组合学题解

题解 #

这种题常见套路就是写一个求 1 到 x 答案的函数 $F(x)$ 然后最终答案就是 $F(r)-F(l-1)$ 。

一种很妙的方法是我们可以通过在任意数字之后加一个第一位的数字从而得到题目要求的数字。所以如果 x 小于 10 那么答案就是 x，否则答案就是去掉最后一位的 x+9。如果最后一位小于第一位我们还要把答案减 1。

Code #

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
ll cal(ll x){
	if(x<10) return x;
	string st=to_string(x);
	ll ans=9;
	if(st[0]>st.back()) ans--;
	ans+=x/10;
	return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	ll l,r;
	cin>>l>>r;
	cout<<cal(r)-cal(l-1);
    return 0;
}