归档 221018 | 做题记录

K. Difference

https://loj.ac/p/2161

好耶我会打 \(n^3\)！这说明这道题 \(n\) 一定等于 \(10^3\)！

我超，是 \(10^6\)？？？？寄，，，，，

枚举出现次数最多的字符（假设为 \(x\)）和出现次数最少的字符（假设为 \(y\)）。

然后用一个类似于双指针的东西，额，我解释不大来，总之意思就是我们要让 \(y\) 和 \(x\) 第一次出现的地方分别成为起始区间的起点和终点。

说是起点和终点，但实际上你不用特别在意它们一开始的前后顺序，因为我们会把 \(26\times 26\) 中情况全部枚举一遍。。。而且不排除存在 \(x\) 反杀的可能性。

然后，如果右端点能往右挪，多塞下一个 \(x\)，我就肯定往右挪，此时统计的答案增加 \(1\)。如果 \(x\) 挪不了了，那就往右挪 \(y\)，不停下来是因为虽然 \(x\) 现在一时吃瘪，但后面还是有可能反杀 \(y\)。

那么问题来了，你怎么知道你枚举的这个区间里 \(x\) 一定出现次数最多，\(y\) 一定出现次数最少？？？

我可没这么说过嗷，你想，如果 \(x\) 出现次数不是最多，\(y\) 出现次数不是最少，说明答案也不是这个区间里最多的，所以后面还会被更新。

关于「往右挪」这个操作，我们预处理一下某个字符某一次出现的位置就好。

然后注意跳的时候如果出现了数量统计为负的情况就可以从 0 开始统计了！

然后最后的时间复杂度是 \(\mathcal O(n)\)，因为要非常严谨地 KA 掉常数，虽然这个常数是一个明显跑不满的 \(10^2\) 级别。。。

namespace XSC062 {
using namespace fastIO;
const int maxm = 28;
const int maxn = 1e6 + 5;
char s[maxn];
int cnt[maxm];
int d[maxm][maxn];
int n, l, r, res, ans, t, f;
inline int max(int x, int y) {
	return x > y ? x : y; 
}
int main() {
	read(n);
	reads(s + 1);
	for (int i = 1; i <= n; ++i)
		d[s[i] - 'a' + 1][++cnt[s[i] - 'a' + 1]] = i;
	for (int x = 1; x <= 26; ++x) {
		if (!cnt[x])
			continue;
		for (int y = 1; y <= 26; ++y) {
			if (!cnt[y] || x == y)
				continue;
			f = 0;
			t = cnt[x] + cnt[y];
			l = 1, r = 1, res = -1;
			while (t--) {
				if ((l <= cnt[x] && d[x][l] < d[y][r])
					|| r > cnt[y])
					++l, ++res;
				else ++r, res -= f, f = 1;
				if (res < 0)
					f = 0;
				ans = max(ans, res);
			}
		}
	}
	print(ans);
	return 0;
}
} // namespace XSC062