「USACO 2022.12 Platinum」Palindromes 题解

题目大意

给定一个长度为 $N$ 的字符串，仅包含字符 G 和 H。对于所有 $\frac{N(N+1)}{2}$ 个连续子串，计算将该子串重新排列成回文串所需的最小相邻交换次数，如果无法重排成回文则贡献为 $-1$。输出所有子串的答案之和。

解题思路

关键观察

1. 回文可行性：一个子串能重排成回文 ⇔ 至多一个字符出现奇数次
2. 最小交换次数：将字符串重排成目标回文所需的相邻交换次数 = 逆序对数
3. 对称处理：只考虑以 H 为中心的对称情况，最后除以 2

算法核心

中心扩展法

代码采用以每个 H 字符为中心，向两边扩展的方法：

• solve(i, i)：以单个 H 为中心
• solve(ls, i)：以上一个 H 和当前 H 共同作为中心

维护数据结构

• C[x]：记录位置 x 的计数
• F：当前总代价
• df：差分值
• s：对称中心位置

通过巧妙的增量更新来高效计算所有子串的代价。

代码解析

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); i++)
using namespace std;
using LL = long long;

string S;
int N;

LL solve(int l, int r) {
    vector<int> C(2 * N + 2, 0);  // 计数数组
    int nr = r, s = l + r, df = 0, F = 0;  // nr: 下一个H位置, s: 对称中心
    LL ans = 0;
    
    // 增量操作：向右移动对称中心
    auto inc = [&]() {
        F += df, df += C[++s];
    };
    
    // 减量操作：向左移动对称中心  
    auto dec = [&]() {
        df -= C[s--], F -= df;
    };
    
    // 添加/删除字符
    auto add = [&](int x, int v) {
        C[x] += v * 2, df += x <= s ? v : -v, F += abs(x - s) * v;
    };

    // 初始化：移除中心字符（如果是单个字符）
    if (l == r)
        add(l * 2, -1);

    // 主循环：向左扩展
    for (; l; l--, dec()) {
        if (S[l - 1] == 'H') {
            // 遇到H，向右扩展到下一个H
            REP(i, 1, nr - r) inc();
            r = nr;
            
            if (r > N) break;
            
            // 找到下一个H的位置
            for (nr = r + 1; S[nr - 1] == 'G'; nr++)
                ;
            
            add(l + r, 2);  // 添加新的对称对
        }
        
        // 计算当前扩展的代价
        REP(i, 1, nr - r) ans += F & 1 ? -2 : F, inc();
        REP(i, 1, nr - r) dec();
    }
    
    return ans;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> S, N = S.size();
    LL ans = 0;
    
    // 遍历所有H字符作为中心
    for (int i = 1, ls = 0; i <= N; i++) {
        if (S[i - 1] == 'H') {
            ans += solve(i, i) + (ls ? solve(ls, i) : 0);
            ls = i;
        }
    }
    
    cout << ans / 2;  // 除以2因为对称计算了两次
    return 0;
}

算法正确性

为什么这样计算？

• 算法基于对称性：只考虑以H为中心的对称情况
• F 维护当前配置下的总不对成代价
• 通过增量更新避免重复计算

可行性判断

• 当 F 为奇数时：说明无法形成回文（字符频次不满足条件）
• 此时贡献为 -2（因为对称计算了两次）

复杂度分析

• 时间复杂度：$O(N^2)$
  • 外层循环遍历所有 H 字符：$O(N)$
  • solve 函数内部是均摊 $O(N)$ 的
• 空间复杂度：$O(N)$

样例验证

对于输入 GHHGGHHGH：

• 子串 G：已是回文，贡献 0
• 子串 GH：无法重排成回文，贡献 -1
• 子串 GHH：一次交换可成回文，贡献 1
• 子串 HHGG：两次交换可成回文，贡献 2
• 最终总和：12 ✓

总结

本题的巧妙解法在于：

1. 对称性利用：只计算一半情况，最后除以2
2. 增量更新：通过维护差分信息高效计算
3. 可行性整合：在计算过程中同时判断能否形成回文

这种基于对称中心和增量维护的思路，对于处理回文相关的高维问题具有很好的参考价值。