CF2096E题解

· · 题解

将 B 看作 0，P 看作 1。我们发现，对 110 和 100 的情况，操作一次会使逆序对数减少 2，而对于 101 和 010 的情况，操作一次会使逆序对数减少 1，前者显然优于后者，我们称前者为优的操作，后者为不优的操作。

但是，我们不一定能通过仅操作 110 和 100 使得序列变为有序，因为在操作过程中，我们只能交换奇偶性相同的两个位置上的数。相反，通过操作 101 和 010，我们交换的是奇偶性不同的位置上的两个数。

不妨设有 c 个 0，初始时，有 x 个 0 位于奇数位置。由于有序的序列中，有 \lceil \frac{c}{2} \rceil 个 0 位于奇数位置，因此，我们至少要经过 |x-\lceil \frac{c}{2} \rceil| 次不优的操作，才能使序列的奇偶性正确。

现在我们需要证明两个结论，第一个结论是，我们可以进行 |x-\lceil \frac{c}{2} \rceil| 次操作来调整奇偶性，第二个结论是，除去那些调整奇偶性的操作，我们能仅通过优的操作使序列变为有序。

现在证明第一个结论。首先，若序列的有长度大于 1 的极长连续段位于序列两侧以外的其他位置，我可以通过不断采用优的操作将元素移动到序列两侧使得这些极长连续段的长度均不大于 1，不断重复该过程，最终得到的序列一定形如 000...1010101.....111，下面我们进行分类讨论。

如果 10 只重复一次，那么通过一次操作就可以使序列有序，接下来我们讨论重复至少两次的情况。

若前缀 0 的个数为偶数，那么 10 循环中的所有 0 都落在偶数位。假设 10 循环重复了 k 次，那么我们需要 \lceil \frac{k}{2} \rceil 次操作把 \lceil \frac{k}{2} \rceil 个位于偶数位的 0 改到奇数位。考虑每两个 10 为一组，操作 1010 中的前 3 个数 101 即可。此时若 k 是奇数，则再取边界右侧后一个 1 进行操作即可（若边界右侧没有 1，则在前面操作完之后可以通过优的操作移动过去，可以证明这一定是可行的）。

若前缀 0 的个数是奇数，同理，我们需要 \lceil \frac{k}{2} \rceil 次操作把 \lceil \frac{k}{2} \rceil 个位于奇数位的 0 改到偶数位，类似可得。

现在我们证明了第一个结论，不妨用同样的性质证明第二个结论。由于形如 000...1010101.....111 的所有序列中只有有序的序列奇偶性正确，因此通过优的操作必然能排出有序的序列。

于是我们证明了这种贪心策略是可行的，直接统计答案即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve(){
    int ans = 0, cntp = 0, n, x = 0, c = 0;
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;
    for(int i = 1; i <= n; i++){
        if(s[i] == 'P') cntp++;
        else ans += cntp, x += i % 2, c++;
    }
    int t = abs((c + 1) / 2 - x);
    cout << (ans - t) / 2ll + t << '\n';
}

signed main(){
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}