首页 > 代码库 > zoj 3816 Generalized Palindromic Number(暴力枚举)
zoj 3816 Generalized Palindromic Number(暴力枚举)
题目链接:zoj 3816 Generalized Palindromic Number
题目大意:给定n,找一个最大的数x,保证x小于n,并且x为palindromic number
解题思路:枚举前i个放于n相同的数,然后去构造后半部分即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
int n = 0, bit[30], num[30], ans[30];
bool judge(int* a, int* b, int n) {
for (int i = n - 1; i >= 0; i--) {
if (a[i] != b[i])
return a[i] > b[i];
}
return false;
}
bool cmp (int* a, int* b, int d) {
for (int i = 1; i <= d; i++) {
if (a[n-i] != b[n-i])
return a[n-i] > b[n-i];
}
return false;
}
void dfs (int d, int p, bool flag) {
if (d < p) {
if (judge(bit, num, n) && judge(num, ans, n))
memcpy(ans, num, sizeof(num));
return;
}
int end = (flag ? bit[d] : 9);
for (int i = end; i >= 0; i--) {
int v = p;
if (cmp(ans, num, n - d - 1))
return;
num[d] = i;
if (num[d] != num[d+1]) {
while (v <= d) {
num[v++] = num[d];
dfs(d - 1, v, flag && i == end);
}
} else
dfs(d - 1, p, flag && i == end);
}
}
ll solve () {
ll a;
scanf("%llu", &a);
memset(ans, 0, sizeof(ans));
memset(bit, 0, sizeof(bit));
memset(num, 0, sizeof(num));
n = 0;
while (a) {
bit[n++] = a % 10;
a /= 10;
}
num[n] = 0;
dfs(n-1, 0, 1);
ll ret = 0;
for (int i = n - 1; i >= 0; i--)
ret = ret * 10 + ans[i];
return ret;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
printf("%llu\n", solve());
}
return 0;
}
zoj 3816 Generalized Palindromic Number(暴力枚举)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。