思路

$90 pts$ 做法：直接模拟，枚举 $i \in [l,r]$，看一下 $i$ 满不满足情况。

$100 pts$ 做法：类似前缀和方法预处理，用 $pre_i$ 表示区间 $[1,i]$ 中有 $0$ 个 $1$ 数字的个数。

询问的答案跟用前缀和求区间和的方法一样，$[l,r]$ 中满足条件的数有 $pre_{r}-pre_{l-1}$ 个。

时间复杂度 $O(kn)$。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
const int N = 1e7 + 10;
int pre[N];

bool check(int k) {
	while (k) {
		if (k % 10 == 1) {
			return false;
		}
		k /= 10;
	}
	return true;
}

int main() {
	int T;
	scanf("%d", &T);
	for (int i = 0; i <= 1e7 + 10; i++) {
		if (check(i)) {
			pre[i]++;
		}
		pre[i] += pre[i - 1];
	}
	while (T--) {
		int l, r;
		scanf("%d%d", &l, &r);
		if (!l) {
			printf("%d\n", pre[r]);
		} else {
			printf("%d\n", pre[r] - pre[l - 1]);			
		}
	}
	return 0;
}