题解：CF2069D Palindrome Shuffle

· · 题解

线性做法

特判掉原串是回文串，答案是 0。

先删掉首尾相等的字符，因为一定不会操作到这里。此时假设字符串的长度为 L。

现在这个字符串首尾不相等，则选择的区间一定包含首或包含尾（不然首尾仍然不相等，不能回文），因此选择的区间一定是当前字符串的前缀或后缀。

然后我们先找到中间最长的回文串。比如字符串是 abcababac，我们会找到 abc[aba]bac。此时如果两侧每个字符的出现次数都相等，那么我们只需重排其中一侧即可。上面我们只需重排左侧的 abc 或右边的 bac 即可。

如果出现次数不相等，比如 aa[bb]cc，我们直接枚举前缀和后缀的长度即可。这个长度一定超过 \lfloor \frac{L}{2} \rfloor，比如上面，我们只选 aab 是不可行的。

我们现在枚举了一个后缀 S，剩下的前缀为 P，如何判断它是不是合法的？

比较简便的方法就是：如果每个字符在 P 中的出现次数不超过在 S 中的出现次数，则合法，否则不合法。

简单证明一下。因为题目保证有解，所以至多有一个字符出现了奇数次。

如果没有字符出现了奇数次，则我们在 S 中选出一个与 P 相同的子集 P^\prime，翻转过来并放到后缀。此时每个字符在 P 和 P^\prime 个出现一次，都出现了偶数次，因此也剩下了偶数次，在中间对半分即可。

如果有一个字符出现了奇数次，设出现了 x 次，则左边选了小于等于 \lfloor \frac{x}{2} \rfloor 就合法，大于等于 \lceil \frac{x}{2} \rceil 个就不合法。这满足“在 P 中的出现次数不超过在 S 中的出现次数则合法，否则不合法”。对于出现偶数次的，和前面“没有字符出现了奇数次”的情况相同。

所以这个判断方法是正确的。我们用两个桶记录，枚举时维护前缀和后缀每个字符的出现个数，到最后一个合法的位置即可。

代码

C++ 20 大法好。

#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;
}