Problem - C - Codeforces
让我们称某个正整数为“优美的”，如果它的十进制表示中不超过3个数字不为零。例如，数字4、200000、10203是优美的，而数字4231、102306、7277420000则不是。
给定一个区间[L;R]，请计算在此区间内有多少个优美的整数x，满足L≤x≤R。
每个测试用例包含若干个区间，对于每个区间，您需要单独解决问题。
输入：
第一行包含一个整数T（1≤T≤104）——测试用例的数量。
Example
Input
Copy
4 1 1000 1024 1024 65536 65536 999999 1000001
Output
Copy
1000 1 0 2
题解:
题中说最多三个位置不为0,
情况大概为有三种
1.一个地方不为0,18个位置中选一个位置为1~9,其余均为0
2.两个位置不为0同上
3.三个位置不为0同上
根据组合数学,我们发现可以构造出的数完全可以用数组存下,我们对数组进行排序,二分找首尾,
即可算出答案
别忘了把1e18也加上
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
typedef unsigned long long ULL;
const int N = 3e5 + 10;
int mod = 1e9 + 7;
int a[1000050],idx;
void dfs(int now,int cnt,int len)
{
a[++idx] = now;
// cout << now <<"\n";
if(len == 18)
return ;
dfs(now*10,cnt,len + 1);
if(cnt < 3)
{
for(int i = 1;i <= 9;i++)
{
dfs(now*10 + i,cnt + 1,len + 1);
}
}
}
void solve()
{
int l,r;
cin >> l >> r;
int x = lower_bound(a + 1,a + 1 + idx,l) - a;
int y = upper_bound(a + 1,a + 1 + idx,r) - a;
cout << y - x<<"\n";
}
signed main()
{
// ios::sync_with_stdio(0 );
// cin.tie(0);cout.tie(0);
int t = 1;
for(int i = 1;i <= 9;i++)
dfs(i,1,1);
a[++idx] = 1e18;
sort(a + 1,a + 1 + idx);
cin >> t;
while(t--)
{
solve();
}
}
