【链接】 我是链接,点我呀:)
【题意】
让你求出只由3个非0数字组成的数字在[li,ri]这个区间里面有多少个.
【题解】
只由3个非0数字组成的数字在1~10^18中只有60W个
dfs处理出来之后排序做个二分查找一下区间里有多少个就好。
【代码】
import java.io.*;
import java.util.*;
public class Main {
static InputReader in;
static PrintWriter out;
public static void main(String[] args) throws IOException{
//InputStream ins = new FileInputStream("E:\\rush.txt");
InputStream ins = System.in;
in = new InputReader(ins);
out = new PrintWriter(System.out);
//code start from here
new Task().solve(in, out);
out.close();
}
static int N = 700000;
static class Task{
TreeSet<Long> myset = new TreeSet<Long>();
long a[] = new long[N+10];
int T,n;
long l,r;
void dfs(long cur,int num,int dep) {
if (dep==18) {
if (cur>0) myset.add(cur);
return;
}
if (num<3) {
for (int j = 1;j <= 9;j++)
dfs(cur*10+j,num+1,dep+1);
}
dfs(cur*10,num,dep+1);
}
int get_least_gore(long x) {
int l = 1,r = n,temp = 1;
while (l<=r) {
int mid = (l+r)/2;
if (a[mid]>=x) {
temp = mid;
r = mid - 1;
}else l = mid + 1;
}
return temp;
}
int get_last_lore(long x) {
int l = 1,r = n,temp = 1;
while (l<=r) {
int mid = (l+r)/2;
if (a[mid]<=x) {
temp = mid;
l = mid + 1;
}else r = mid - 1;
}
return temp;
}
public void solve(InputReader in,PrintWriter out) {
myset.add((long)1e18);
dfs(0,0,0);
n = myset.size();
Iterator<Long> it = myset.iterator();
int j = 1;
while (it.hasNext()) {
a[j] = it.next();
j++;
}
T = in.nextInt();
for (int ii = 1;ii <= T;ii++) {
l = in.nextLong();r = in.nextLong();
int idx1 = get_least_gore(l);
int idx2 = get_last_lore(r);
out.println(idx2-idx1+1);
}
}
}
static class InputReader{
public BufferedReader br;
public StringTokenizer tokenizer;
public InputReader(InputStream ins) {
br = new BufferedReader(new InputStreamReader(ins));
tokenizer = null;
}
public String next(){
while (tokenizer==null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(br.readLine());
}catch(IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
}
}