初看题目以为是数位dp,一看数据范围,好吧我放弃了
这么大的数据范围,显然先找数再判断是否满足条件是不合适的
一个直接的思路就是看能不能直接把所有满足条件的数找出来
考虑满足条件的数的个数,为了方便从第一位开始顺序向后枚举,以后每位比前一位多1或者少1
如此便能不重不漏枚举到所有情况,第一位1~9,以后每位两种选择即2^8,一共才2000多个数
所以直接把满足条件的数找出来并统计在范围内的个数就行,为了写起来方便就用dfs写了
时间复杂度$O(T(2000+c))$?我也不清楚,反正不大就是了
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ri register int
#define endl '\n'
#define rep(i, x, y) for(ri i = x; i <= y; ++ i)
#define pre(i, x, y) for(ri i = x; i >= y; -- i)
#define x first
#define y second
#define lowbit(x) (x&(-x))
#define maxe max_element
#define mine min_element
#define all(v) v.begin(), v.end()
#define pb push_back
#define qb pop_back
#define pf push_front
#define qf pop_front
using namespace std;
using i64 = int64_t;
const int N = 30;
int T, n, m;
int res, ans;
void dfs(i64 u, ri v, ri w)
{
if(v < 10) return;
if(u > v) return;
if(w > 1) ++ res;
ri k = u % 10;
if(k > 0) dfs(u * 10 + k - 1, v, w + 1);
if(k < 9) dfs(u * 10 + k + 1, v, w + 1);
}
int main()
{
IOS;
cin >> T;
while(T --)
{
cin >> n >> m;
res = 0;
rep(i, 1, 9) dfs(i, n - 1, 1);
ans = res, res = 0;
rep(i, 1, 9) dfs(i, m, 1);
cout << res - ans << endl;
}
return 0;
}