题意

给出n个数字的序列，现在让你分成三段，使得每一段翻转之后拼接起来的序列字典序最小。保证第一个数是序列中最大的数。

例如样例是{10, 1, 2, 3, 4}，分成{1, 10}, {2}, {3,4}，最后字符串变成{1, 10, 2, 4, 3}。

思路

首先考虑第一段，因为第一个数是最大的，因此只要使得某一个前缀翻转后的字典序最小，所以只要选择序列翻转后最小后缀。

对于第二段和第三段，如果像第一段一样直接找剩下的里面最小的后缀，是不可行的，因为直接取第二段最优就忽略了第三段的最优。

例如对于这个剩下的序列：{3, 1, 2, 3, 1, 4}，翻转后：{4, 1, 3, 2, 1, 3}，取最小后缀{1, 3}作为第二段，那么最后得到的第二三段翻转后的后缀合起来是：{1, 3, 4, 1, 3, 2}。

这样不如取后缀{1, 3, 2, 1, 3}作为第二段更优，最后得到{1, 3, 2, 1, 3, 4}。

可以发现，这是一个类似于环的东西，即第一段取了{1,3}，剩下一段{4, 1, 3, 2}就是接在{1,3}后面的，构成了一个环状的序列。

那么现在问题就转化为，求一个环状序列长度为n的字典序最小序列了。

因此，可以直接复制一遍序列放在后面，变成{4, 1, 3, 2, 1, 3, 4, 1, 3, 2, 1, 3}，这样再对这个序列求一个最小后缀（这个最小后缀要合法），得到的就是可行的了。

回过头来，为什么第一段就可以直接求？

因为第一个数是最大的，像个墙一样卡在那里，如果也是复制一遍的话，可以发现其实根本取不到后面（取[n,2*n)的字典序不可能比取[0,n)的后缀更小）。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

const int N = 2e5 + 11;

int t1[N*2], t2[N*2], c[N*2], s[N*2], str[N*2], Hash[N], sa[N*2], n;

bool cmp(int *r, int a, int b, int l) {

	return r[a] == r[b] && r[a+l] == r[b+l];

}

void SA(int s[], int sa[], int n, int m) {

	int i, j, p, *x = t1, *y = t2;

	for(i = 0; i < m; i++) c[i] = 0;

	for(i = 0; i < n; i++) c[x[i] = s[i]]++;

	for(i = 1; i < m; i++) c[i] += c[i-1];

	for(i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;

	for(j = 1; j <= n; j <<= 1) {

		p = 0;

		for(i = n - j; i < n; i++) y[p++] = i;

		for(i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i] - j;

		for(i = 0; i < m; i++) c[i] = 0;

		for(i = 0; i < n; i++) c[x[y[i]]]++;

		for(i = 1; i < m; i++) c[i] += c[i-1];

		for(i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];

		swap(x, y);

		p = 1; x[sa[0]] = 0;

		for(i = 1; i < n; i++)

			x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p - 1 : p++;

		if(p >= n) break;

		m = p;

	}

}

int main() {

	scanf("%d", &n);

	for(int i = 0; i < n; i++) scanf("%d", &s[i]), Hash[i] = s[i];

	sort(Hash, Hash + n);

	int m = unique(Hash, Hash + n) - Hash;

	// 离散化后注意区间是到m不是到n  !!!

	for(int i = 0; i < n; i++) s[i] = lower_bound(Hash, Hash + m, s[i]) - Hash;

	int p1, p2;

	reverse_copy(s, s + n, str);

	SA(str, sa, n, m);

	for(int i = 0; i < n; i++) {

		p1 = n - sa[i];

		if(p1 >= 1 && n - p1 >= 2) break;

		// 第一段至少有1个数并且剩下至少两个数(因为后面要分成两段)

	}

	int nn = n - p1;

	reverse_copy(s + p1, s + n, str);

	reverse_copy(s + p1, s + n, str + nn);

	SA(str, sa, 2 * nn, m);

	for(int i = 0; i < 2 * nn; i++) {

		if(sa[i] >= nn) continue;

		p2 = nn - sa[i] + p1;

		if(p2 - p1 >= 1 && n - p2 >= 1) break;

		// 第二段至少有1个数并且至少剩下一个数(还剩下一段)

	}

	for(int i = p1 - 1; i >= 0; i--) printf("%d\n", Hash[s[i]]);

	for(int i = p2 - 1; i >= p1; i--) printf("%d\n", Hash[s[i]]);

	for(int i = n - 1; i >= p2; i--) printf("%d\n", Hash[s[i]]);

	return 0;

}

/*

8

5 0 3 1 2 3 1 4

0

5

1

3

2

1

3

4

*/

巴特西

POJ 3581：Sequence（后缀数组）

题意

思路

最新文章

热门文章