自动搬运

查看原文

来自洛谷，原作者为

	jiazhaopeng 抓紧时间 提高效率 认真思考

搬运于2025-08-24 21:42:30，当前版本为作者最后更新于2019-12-08 09:15:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P2870 [USACO07DEC]最佳牛线，黄金Best Cow Line, Gold

题意

• 给一个字符串，每次只能从两边取，加入到答案，要求取出来之后答案的字典序最小。
• $len$<=$500000$

思路

因为这道题要求答案字典序最小，所以我们有一个贪心策略：每一次都取两端的较小者，一直取完。这一定是没有问题的，此时局部最优解就是全局最优解。关键是当两端相同时应该怎么办。

当字符串为 $ACERHA$ 时，我们发现取哪一个 $A$ 都可以，因为 $C$ 和 $H$ 都比$A$ 大，我们一定会取完两个 $A$ 再取里面的字母。

当字符串为 $CAEAAC$ 时，我们发现，如果取左边的 $C$，答案会是这个样子： $CACAAE$ ，而取右边会是： $CAACAE$。

多玩几组数据会发现，如果两端字母一样，就看看里面的那一位一样不一样。如果里面那一位不同，则取较小的字母所在的一端；如果里面那一位相同，就继续看里面的里面，一直到比出结果为止。（当然，如果当前字符串本身就是个回文串，就取哪端都行了）

优化

但是，这样做最坏是 $n^2$ 的。比如，给一个 $AAAAAAAAAAA$，我们每次都要判断两端取哪一个更优，这是 $O(n)$ 的，需要做 $n$ 次，复杂度爆炸。我们不得不考虑优化。我们发现，如果我们针对这种最劣情况，要是能用某种方法迅速找出两端相同的长度，就可以把最劣情况的每一次判断做到 $logn$，问题就解决了。你一定能想到，这个地方可以用哈希。

如果你不会哈希的基本操作的话，可以参考机房大佬的博客：lhm_的博客

$Code$:

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#define N 500010
#define M 98244353
#define base 131
template<typename T> inline void read(T &x) {
	x = 0; char c = getchar(); bool flag = false;
	while (!isdigit(c)) {if (c == '-') flag = true; c = getchar(); }
	while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
	if (flag)	x = -x;
}
using namespace std;
int n;
char s[N];
long long ha1[N], ha2[N], bas[N];
//因为要正着的串和反着的串比较，所以要用两个哈希 
//bas[i]:base^i
char ans[N];
int top;
int lef, rig;//left, right
inline int che(int len) {//hash基本操作：比较两端是否相同 
	long long l = ((ha1[lef + len - 1] - ha1[lef - 1] * bas[len]) % M + M) % M;
	long long r = ((ha2[rig - len + 1] - ha2[rig + 1] * bas[len]) % M + M) % M;
	return l == r;
}
inline int halffind() {
	int l = 1, r = (rig - lef + 1) >> 1;
	int mid, res = 1;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (che(mid)) {
			res = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return res;
}
int main() {
	read(n);
	for (register int i = 1; i < n; ++i) {
		s[i] = getchar();
		getchar();
	}
	s[n] = getchar();
	bas[0] = 1;
	for (register int i = 1; i <= n; ++i) {
		ha1[i] = (ha1[i - 1] * base + s[i]) % M;
		bas[i] = bas[i - 1] * base % M;
	}
	for (register int i = n; i; --i) {
		ha2[i] = (ha2[i + 1] * base + s[i]) % M;
	}
	
	lef = 1, rig = n;
	int len;
	for (register int i = 1; i < n; ++i) {
		if (s[lef] < s[rig]) {
			ans[++top] = s[lef++];
		} else if (s[rig] < s[lef]) {
			ans[++top] = s[rig--];
		} else {
			len = halffind();
			ans[++top] = s[lef + len] < s[rig - len] ? s[lef++] : s[rig--];
		}
	}
	ans[n] = s[lef];//最后一个直接扔到答案结尾即可，不用判断 
	for (register int i = 1; i <= n; ++i) {
		putchar(ans[i]);
		if (i % 80 == 0)	putchar('\n');
	}
	return 0;
}

第一次写题解，如果有错误，欢迎指出。