首页 > 代码库 > zoj 3816 Generalized Palindromic Number (二分+贪心)
zoj 3816 Generalized Palindromic Number (二分+贪心)
题目连接 : http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5348
牡丹江网络赛的题，比赛的时候想到做法的，但是一直没调出来，赛后也调了些时间，最近代码能力堪忧啊~
有好多做法， 我的做法是二分下界low，即判断在low到n-1之间是否存在符合要求的数。然后贪心去构造一个解(直觉告诉我直接构造最大解好像很麻烦的样子)。
构造解是这样的：首先low和n相同的前几位先放好，因为不管怎样这几位都是不变的，然后假如某一位不相同了，那么后面的位置上放数就不需要考虑下界了，直接贪心出最小解就行了，比较最小解与N的大小就行了，也就是最后问题变成了前几位确定的，总的位数也是确定的，求最小解，这个可以贪心搞的，不过需要枚举中间在哪里，注意可以在中间放0喔。具体细节看代码。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <time.h> 6 7 using namespace std; 8 typedef long long lld; 9 const int MAXN = 55; 10 const lld INF = 1LL<<62; 11 int bit[MAXN]; 12 int BIT[MAXN]; 13 lld n; 14 int m; 15 int arr[MAXN]; 16 17 lld calc(int a[], int cnt, int mid, int inx) { 18 if (2 * mid - cnt > inx) return INF; 19 lld ret = 0; 20 for (int i = m; i >= inx; i--) { 21 ret *= 10; ret += arr[i]; 22 } 23 for (int i = mid + 1; i <= cnt; i++) { 24 if (2 * mid - i <= 0 || a[i] != a[2 * mid - i]) return INF; 25 } 26 int ind = 2 * mid - cnt; 27 for (int i = inx - 1; i >= 1 && ind >= 1; i--) { 28 ret *= 10; 29 if (ind == 1) { 30 ret += a[ind]; 31 }else { 32 if (ind-1 == i || a[ind-1] <= a[ind]) { 33 ret += a[ind-1]; ind--; 34 }else { 35 ret += a[ind]; 36 } 37 } 38 } 39 return ret; 40 } 41 42 int isok(int inx) { 43 int cnt = 0; 44 int a[MAXN]; 45 for (int i = m; i >= inx; i--) { 46 if (arr[i] != 0) { 47 a[++ cnt] = arr[i]; 48 for (int j = i - 1; j >= inx; j--) { 49 if (a[cnt] != arr[j]) a[++ cnt] = arr[j]; 50 } 51 break; 52 } 53 } 54 for (int i = cnt/2; i <= cnt; i++) { 55 lld ret = calc(a, cnt, i, inx); 56 if (ret <= n) return 1; 57 } 58 a[++ cnt] = 0; 59 return calc(a, cnt, cnt, inx) <= n; 60 } 61 62 int solve() { 63 for (int i = m, fg = 0; i >= 1; i--) { 64 if (bit[i] == BIT[i] && !fg) { 65 arr[i] = bit[i]; continue; 66 } 67 int Max = (fg >= 1 ? 9 : BIT[i]); 68 for (int j = Max; j >= bit[i] + 1; j--) { 69 arr[i] = j; 70 if (isok(i)) return 1; 71 } 72 arr[i] = bit[i]; 73 fg ++; 74 } 75 int a[MAXN], cnt = 1; 76 a[1] = arr[m]; 77 for (int i = m - 1; i >= 1; i--) { 78 if (a[cnt] != arr[i]) a[++ cnt] = arr[i]; 79 } 80 for (int i = 1; i <= cnt/2; i++) { 81 if (a[i] != a[cnt-i+1]) return 0; 82 } 83 return 1; 84 } 85 86 int check(lld x) { 87 int len = 0; 88 memset(bit, 0, sizeof(bit)); 89 memset(arr, 0, sizeof(arr)); 90 while (x) { 91 bit[++ len] = x % 10; 92 x /= 10; 93 } 94 return solve(); 95 } 96 int main() { 97 int T; 98 scanf("%d", &T); 99 for (int cas = 1; cas <= T; cas++) {100 cin >> n;101 int ret;102 if (n == 1) {103 printf("0\n"); continue;104 }105 n = n - 1;106 lld l = 1, r = n;107 m = 0;108 lld tmp = n;109 while (tmp) {110 BIT[++ m] = tmp % 10;111 tmp /= 10;112 }113 while (r >= l) {114 lld mid = r + l >> 1;115 if (check(mid)) {116 l = mid + 1;117 }else {118 r = mid - 1;119 }120 }121 cout << l - 1 << endl;122 }123 return 0;124 }
zoj 3816 Generalized Palindromic Number (二分+贪心)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。