题目链接：点击打开链接
题意：
给定一个数n
找一个最大的数u使得u
枚举前面有多少位是一样的。然后分类讨论。啪啦啪啦
#include
#include
#include
#include
#include
using namespace std; typedef long long ll; const int N = 22; int pie[N], piesize; ll ans, x; int z[N], a[N], asize; ll mx[N]; bool ok(ll v) { int x, dep = 0; while (v > 0) { x = v % 10; if (dep == 0 || x != z[dep - 1]) z[dep++] = x; v /= 10; } int l = 0, r = dep - 1; while (l < r) { if (z[l] == z[r]) ++ l, -- r; else return false; } return true; } void up(ll g) { if (g > ans) { ans = g; for (int i = 0; ;++i) { g /= 10; mx[i] = g; if (g == 0) return ; } } } void dfs(int dep, ll g, int idy, int f) { if (dep == -1) { if (g <= x && ok(g)) { up(g); } } else { if (mx[dep] > g) return ; if (f) { dfs(dep - 1, g * 10 + a[idy], idy, 1); if (idy - 1 >= 0) dfs(dep - 1, g * 10 + a[idy - 1], idy - 1, 1); } else { if (a[idy] < pie[dep]) { dfs(dep - 1, g * 10 + a[idy], idy, 1); } else if (a[idy] == pie[dep]) { dfs(dep - 1, g * 10 + a[idy], idy, 0); } if (idy - 1 >= 0) { if (a[idy - 1] < pie[dep]) dfs(dep - 1, g * 10 + a[idy - 1], idy - 1, 1); else if (a[idy - 1] == pie[dep]) dfs(dep - 1, g * 10 + a[idy - 1], idy - 1, 0); } } } } /* void dfs(int dep, ll g, int idy, int f) { if (dep == -1) { if (g <= x && ok(g)) ans = max(ans, g); } else { dfs(dep - 1, g * 10 + a[idy], idy); if (idy - 1 >= 0) dfs(dep - 1, g * 10 + a[idy - 1], idy - 1); } } */ void work() { ll y; int n, v; //x = 999915494587545487; scanf("%lld", &x); -- x; if (ok(x)) { printf("%lld\n", x); return ; } if (ok(x - 1)) { printf("%lld\n", x - 1); return ; } // y = x; piesize = 0; while (y > 0) { pie[piesize ++] = y % 10; y /= 10; } n = piesize; ans = 0; memset(mx, 0, sizeof mx); ll g, cnt; for (int i = n - 1; i >= 0; --i) { if (pie[i] == 0) continue; asize = 0; for (int j = n - 1; j > i; -- j) { if (asize == 0 || a[asize - 1] != pie[j]) a[asize ++] = pie[j]; } if (asize == 0 || a[asize - 1] != pie[i] - 1) a[asize ++] = pie[i] - 1; g = 0; for (int j = n - 1; j > i; --j) g = g * 10 + pie[j]; g = g * 10 + pie[i] - 1; dfs(i - 1, g, asize - 1, 1); cnt = i - asize; ll gg = g; for (int j = 0; j <= cnt; ++j) g = g * 10 + 9; for (int j = asize - 2; j >= 0; --j) g = g * 10 + a[j]; if (ok(g) && g <= x) up(g); for (int j = 0; j < cnt; ++j) gg = gg * 10 + 9; for (int j = asize - 1; j >= 0; --j) gg = gg * 10 + a[j]; if (gg <= x && ok(gg)) up(gg); } for (int i = n - 1; i >= 0; --i) { asize = 0; g = 0; for (int j = n - 1; j >= i; --j) { g = g * 10 + pie[j]; if (asize == 0 || a[asize - 1] != pie[j]) a[asize ++] = pie[j]; } dfs(i - 1, g, asize - 1, 0); } printf("%lld\n", ans); } int main() { int cas; scanf("%d", &cas); while (cas -- > 0) work(); return 0; }