ZOJ 3816 Generalized Palindromic Number dfs+暴力枚舉
題目鏈接:點擊打開鏈接
題意:
給定一個數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;
}