首页 > 代码库 > [BZOJ 1692] [Usaco2007 Dec] 队列变换 【后缀数组 + 贪心】
[BZOJ 1692] [Usaco2007 Dec] 队列变换 【后缀数组 + 贪心】
---恢复内容开始---
题目链接:BZOJ - 1692
题目分析
首先,有个比较简单的贪心思路:如果当前剩余字符串的两端字母不同,就选取小的字母,这样显然是正确的。
然而若两端字母相同,我们怎么选取呢?
这时我们要从两端分别向内部比较,看那一端向内的字符串字典序小。
比如这个字符串 ABCDBA,从左端向内是 ABC.. 从右端向内是 ABD... 所以就选取左端的字符。
这样直接比较是 O(n^2) 的,我们可以使用后缀数组的 Rank 数组来比较。
我们在字符串后加上分隔符,然后再将字符串反转接在后面,求后缀数组的 Rank 数组。
这样就可以快速比较一个前缀,一个后缀的字典序大小了,具体见代码。
比如 ABCDBA ,就存成 ABCDBA#ABDCBA 。
代码
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MaxL = 60000 + 15;int n;int A[MaxL], Rank[MaxL], SA[MaxL];int VA[MaxL], VB[MaxL], VC[MaxL], Sum[MaxL];char S[MaxL], Sout[MaxL];inline bool Cmp(int *a, int x, int y, int l) { return (a[x] == a[y]) && (a[x + l] == a[y + l]);}void DA(int *A, int n, int m) { int *x, *y, *t; x = VA; y = VB; for (int i = 1; i <= m; ++i) Sum[i] = 0; for (int i = 1; i <= n; ++i) ++Sum[x[i] = A[i]]; for (int i = 2; i <= m; ++i) Sum[i] += Sum[i - 1]; for (int i = n; i >= 1; --i) SA[Sum[x[i]]--] = i; int p, q; p = 0; for (int j = 1; p < n; j <<= 1, m = p) { q = 0; for (int i = n - j + 1; i <= n; ++i) y[++q] = i; for (int i = 1; i <= n; ++i) { if (SA[i] <= j) continue; y[++q] = SA[i] - j; } for (int i = 1; i <= n; ++i) VC[i] = x[y[i]]; for (int i = 1; i <= m; ++i) Sum[i] = 0; for (int i = 1; i <= n; ++i) ++Sum[VC[i]]; for (int i = 2; i <= m; ++i) Sum[i] += Sum[i - 1]; for (int i = n; i >= 1; --i) SA[Sum[VC[i]]--] = y[i]; t = x; x = y; y = t; x[SA[1]] = 1; p = 1; for (int i = 2; i <= n; ++i) x[SA[i]] = Cmp(y, SA[i], SA[i - 1], j) ? p : ++p; } for (int i = 1; i <= n; ++i) Rank[SA[i]] = i;}int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { cin >> S[i]; A[i] = S[i] - ‘A‘ + 1; A[2 * n - i + 2] = A[i]; } A[n + 1] = 27; A[n * 2 + 2] = 28; DA(A, n * 2 + 2, 28); int l = 1, r = n, Top = 0; while (l <= r) { if (S[l] != S[r]) { if (S[l] < S[r]) { Sout[++Top] = S[l]; ++l; } else { Sout[++Top] = S[r]; --r; } continue; } if (l == r) { Sout[++Top] = S[l]; break; } if (Rank[l] < Rank[n * 2 - r + 2]) { Sout[++Top] = S[l]; ++l; } else { Sout[++Top] = S[r]; --r; } } for (int i = 1; i <= Top; ++i) { printf("%c", Sout[i]); if (i % 80 == 0) printf("\n"); } return 0;}
---恢复内容结束---
[BZOJ 1692] [Usaco2007 Dec] 队列变换 【后缀数组 + 贪心】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。