BFS+lower_bound
既然大家都用dfs, 那咱就写个BFS的版本吧!
爆int调试了半天[恼]
#include <stdio.h>
#define N 100001
#define M 300000001
int all[N], cnt;
int queue[N], front, rear;
int n, l, r;
int push(int x) {
queue[front++] = x;
}
void pop() {
rear++;
}
int top() {
return queue[rear];
}
void bfs() {
for(int i = 1; i <= 9; ++i)
push(i);
long long x, a, b, m, ma, mb;
while(rear != front) {
x = top(); pop();
m = x % 10;
ma = m - 1, mb = m + 1, a = x * 10 + ma, b = x * 10 + mb; // 这里 a和b可能会爆int
if(ma >= 0 && ma <= 9 && a < M){
push(a);
all[cnt++] = a;
}
if(mb >= 0 && mb <= 9 && b < M) {
push(b);
all[cnt++] = b;
}
}
}
int lower_bound(int x) {
int l = 0, r = cnt - 1, mid;
while(l <= r) {
mid = l + r >> 1;
if(all[mid] > x) r = mid - 1;
else l = mid + 1;
}
return l;
}
int main() {
bfs();
// printf("%d\n", cnt);
// for(int i = 0; i < cnt; ++i)
// printf("%d ", all[i]);
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d%d", &l, &r);
printf("%d\n", lower_bound(r) - lower_bound(l-1));
// for(int i = lower_bound(l); i < lower_bound(r); ++i)
// printf("%d ", all[i]);
// putchar(10);
}
return 0;
}