题面
solution
n³dp：fl[x][r]表示当前显示的数字为 x ，还要处理的区间为[x+1,r]时的最小步数，普通区间dp，枚举中间点转移即可，fr类似
查询的时候也枚举中间点然后左右取max值
太慢了，把状态定义改为区间进行加速，最后的答案不会很大(45)，更改状态为：
range_l[c,x] = min{l:fr[l][x] <= c}
range_r[c,x] = max{r:fl[x][r] <= c}
以range_r为例介绍计算方法：
要求满足上述条件的最大值，类似n³的枚举一个中点dp方法，可得若range_r[c,x] >= r,则存在一个点mid（中间点）,满足range_l[c-dist(x,m)-1][m] <= x + 1 且 range_r[c-dist(x,m)-1][m] >= y，其中dist(x,m)表示从 x 变化到 m 需要的步数，再 -1 是因为询问的代价
先强制让第一个条件满足，具体做法为从 1 到 max 枚举 x , 每次用 range_l[c-dist(x,m)-1][m] = x + 1 的 m 更新答案，这里是 = 而不是 <= 是因为 x 是从小到大枚举的，之前的已经算过
对于每一个 m，枚举可以由 m 更新的 x，但复杂度过高，进行折半处理，先把 m 中的 d 为变为 ？，然后对 x 也枚举若干位变成 ? 后的序列更新，复杂度优秀
对于包含 ? 和数字的序列可以通过 11 进制的方法映射到整型
code
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rg register
void read (int &x) {
char ch = getchar(); x = 0;
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}
const int N = 1e5, M = 2e5;
int rg_l[50][N], rg_r[50][N], dr[M], dl[M];
struct qwq {
int id, val;
bool operator < (const qwq &x) const {
return val < x.val;
}
} q[6][N + 10];
int change (int x) { //把原数字转到带 ？ 的映射
int tmp = 0, t = 1;
for (int i = 1; i <= 5; ++i)
tmp += x % 10 * t, x /= 10, t *= 11;
return tmp;
}
int modify (int x, int w) { //把 x 的第 w 位改为 ？ 后映射的数
int t = 1; for (int i = 1; i < w; ++i) t *= 11;
return x % t + (x / t - (x / t) % 11 + 10) * t;
}
#define Max(a, b) (a = a > b ? a : b)
#define Min(a, b) (a = a > b ? b : a)
void dfsr (int c, int x, int now, int w, int s) {
if (5 - w + 1 < s) return;
if (w == 6) {
Max (dr[now], rg_r[c][x]); return;
} dfsr (c, x, now, w + 1, s);
if (s) dfsr (c, x, modify (now, w), w + 1, s - 1);
}
void dfsl (int c, int x, int now, int w, int s) {
if (5 - w + 1 < s) return;
if (w == 6) {
Min (dl[now], rg_l[c][x]); return;
} dfsl (c, x, now, w + 1, s);
if (s) dfsl (c, x, modify (now, w), w + 1, s - 1);
}
void workr (int c, int x, int now, int w) {
if (w == 6) {
Max (rg_r[c][x], dr[now]); return;
} workr (c, x, now, w + 1);
workr (c, x, modify (now, w), w + 1);
}
void workl (int c, int x, int now, int w) {
if (w == 6) {
Min (rg_l[c][x], dl[now]); return;
} workl (c, x, now, w + 1);
workl (c, x, modify (now, w), w + 1);
}
void Pre_work() {
memset (rg_l, 0x3f, sizeof (rg_l));
for (int i = 0; i < N; ++i) {
rg_l[0][i] = rg_l[1][i] = max (0, i - 1);
rg_r[0][i] = rg_r[1][i] = min (i + 1, N - 1);
}
for (int i = 2; i <= 45; ++i) {
memset (dr, 0, sizeof (dr));
memset (dl, 0x3f, sizeof (dl));
for (int p = 1; p <= 5 && p < i; ++p) {
for (int x = 0; x < N; ++x)
q[p][x] = (qwq) {x, rg_l[i - p - 1][x]};
sort (q[p], q[p] + N);
} int y[6];
y[1] = y[2] = y[3] = y[4] = y[5] = 0;
for (int x = 0; x < N; ++x) {
for (int p = 1; p <= 5 && p < i; ++p) {
while (y[p] < N && q[p][y[p]].val < x + 1) ++y[p];
while (y[p] < N && q[p][y[p]].val == x + 1) {
dfsr (i - p - 1, q[p][y[p]].id, change (q[p][y[p]].id), 1, p), ++y[p];
}
}
workr (i, x, change (x), 1);
}
//////////////////////////////////////////////////////////
for (int p = 1; p <= 5 && p < i; ++p) {
for (int x = 0; x < N; ++x)
q[p][x] = (qwq) {x, rg_r[i - p - 1][x]};
sort (q[p], q[p] + N);
}
y[1] = y[2] = y[3] = y[4] = y[5] = N - 1;
for (int x = N - 1; x >= 0; --x) {
for (int p = 1; p <= 5 && p < i; ++p) {
while (y[p] >= 0 && q[p][y[p]].val > x - 1) --y[p];
while (y[p] >= 0 && q[p][y[p]].val == x - 1) {
dfsl (i - p - 1, q[p][y[p]].id, change (q[p][y[p]].id), 1, p), --y[p];
}
}
workl (i, x, change (x), 1);
}
}
}
int get_dis (int x, int y) {
int tmp = 0;
for (int i = 1; i <= 5; ++i)
tmp += (x % 10 != y % 10), x /= 10, y /= 10;
return tmp;
}
void solve (int l, int r) {
int res = 1e9;
for (int mid = l; mid <= r; ++mid) {
int co = get_dis (0, mid) + 1;
int cl = 0, cr = 0;
while (rg_l[cl][mid] > l) ++cl;
while (rg_r[cr][mid] < r) ++cr;
Min (res, co + max (cl, cr));
} printf ("%d
", res);
}
signed main() {
freopen ("button.in", "r", stdin);
freopen ("button.out", "w", stdout);
Pre_work(); int m, l, r; read (m);
while (m--) read (l), read (r), solve (l, r);
return 0;
}