专栏文章

题解：CF2069D Palindrome Shuffle

llrx___
CF2069D题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipmnc06
此快照首次捕获于
2025/12/03 14:29
3 个月前
此快照最后确认于
2025/12/03 14:29
3 个月前
查看原文

线性做法

特判掉原串是回文串，答案是 00。
先删掉首尾相等的字符，因为一定不会操作到这里。此时假设字符串的长度为 LL。
现在这个字符串首尾不相等，则选择的区间一定包含首或包含尾（不然首尾仍然不相等，不能回文），因此选择的区间一定是当前字符串的前缀或后缀。
然后我们先找到中间最长的回文串。比如字符串是 abcababac，我们会找到 abc[aba]bac。此时如果两侧每个字符的出现次数都相等，那么我们只需重排其中一侧即可。上面我们只需重排左侧的 abc 或右边的 bac 即可。
如果出现次数不相等，比如 aa[bb]cc，我们直接枚举前缀和后缀的长度即可。这个长度一定超过 ⌊L2⌋\lfloor \frac{L}{2} \rfloor，比如上面，我们只选 aab 是不可行的。
我们现在枚举了一个后缀 SS，剩下的前缀为 PP，如何判断它是不是合法的？
比较简便的方法就是：如果每个字符在 PP 中的出现次数不超过在 SS 中的出现次数，则合法，否则不合法。
简单证明一下。因为题目保证有解，所以至多有一个字符出现了奇数次。
如果没有字符出现了奇数次，则我们在 SS 中选出一个与 PP 相同的子集 P′P^\prime，翻转过来并放到后缀。此时每个字符在 PP 和 P′P^\prime 个出现一次，都出现了偶数次，因此也剩下了偶数次，在中间对半分即可。
如果有一个字符出现了奇数次，设出现了 xx 次，则左边选了小于等于 ⌊x2⌋\lfloor \frac{x}{2} \rfloor 就合法，大于等于 ⌈x2⌉\lceil \frac{x}{2} \rceil 个就不合法。这满足“在 PP 中的出现次数不超过在 SS 中的出现次数则合法，否则不合法”。对于出现偶数次的，和前面“没有字符出现了奇数次”的情况相同。
所以这个判断方法是正确的。我们用两个桶记录，枚举时维护前缀和后缀每个字符的出现个数，到最后一个合法的位置即可。

代码

C++ 20 大法好。
CPP
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#ifndef ONLINE_JUDGE
#include <format>
#define debug(...) std::cerr << std::format(__VA_ARGS__)
#else
#define debug(...)
#endif
template<typename T>
void ckmax(T& a, T b) {
	if (a < b) a = b;
}
template<typename T>
void ckmin(T& a, T b) {
	if (b < a) a = b;
}

#include <algorithm>
#include <string>
#include <ranges>
#include <vector>
void solve() {
	std::string s;
	std::cin >> s;
	std::ranges::for_each(s, [&](char& c) {c -= 'a';});
	int n = static_cast<int>(s.size());
	if (std::ranges::equal(s, s | std::views::reverse)) { // 特判回文串
		std::cout << "0\n";
		return;
	}

	// 将首尾相同的部分删掉
	int len = *std::ranges::find_if_not(std::views::iota(0, n), [&](int i) {return s[i] == s[n - i - 1];}); // 找到第一个不满足的下标
	s.erase(s.begin(), s.begin() + len);
	s.erase(s.end() - len, s.end());
	n -= len << 1;
	
	// 找出中间回文的长度
	int midl = (n - 1) >> 1, midr = n >> 1;
	len = *std::ranges::find_if_not(std::views::iota(0, n), [&](int i) {return s[midl - i] == s[midr + i];}); // 找到第一个不满足中间回文的长度
	midl -= len;
	midr += len;
	// [midl + 1, midr - 1] 这一段是回文的

	// 判断 [0, midl] 和 [midr, n) 每个字符的出现次数是否相同
	std::string lef = s.substr(0, midl + 1), rig = s.substr(midr);
	std::vector<int> b1(26, 0), b2(26, 0);
	std::ranges::for_each(lef, [&](char c) {++b1[c];});
	std::ranges::for_each(rig, [&](char c) {++b2[c];});
	if (b1 == b2) { // 相同，则只需重排一侧即可
		std::cout << lef.size() << "\n";
		return;
	}

	// 此时一定选一个前缀或一个后缀，并且要跨过中间的回文区
	std::vector<int> buc(26, 0), chosen(26, 0);
	std::ranges::for_each(s, [&](char c) {++buc[c];});
	int ans = n;
	// 选后缀，保留左边，枚举保留几位，找到第一个不满足的
	int i = *std::ranges::find_if(std::views::iota(0, (n + 1) / 2), [&](int i) {
		--buc[s[i]];
		++chosen[s[i]];
		return buc[s[i]] < chosen[s[i]]; // 代表不满足
	}) - 1;
	ckmin(ans, n - i - 1);
	std::ranges::fill(buc, 0);
	std::ranges::fill(chosen, 0);
	std::ranges::for_each(s, [&](char c) {++buc[c];});
	// 保留右边
	i = *std::ranges::find_if(std::views::iota(0, (n + 1) / 2), [&](int i) {
		--buc[s[n - i - 1]];
		++chosen[s[n - i - 1]];
		return buc[s[n - i - 1]] < chosen[s[n - i - 1]];
	}) - 1;
	ckmin(ans, n - i - 1);
	std::cout << ans << "\n";
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int t;
	std::cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...