Educational Codeforces Round 96 (Rated for Div. 2) 解题报告

CF1430E String Reversal

Educational Codeforces Round 96 第五题,签到题。

题目链接

题意翻译

给定一个长度为 \( n \) 的字符串 \( A \),\( B \) 为翻转后的 \( A \) 字符串,请你求出 \( B \) 最少需要多少次相邻字符互换操作才能与 \( A \) 完全一致。\( 1 \leq n \leq 2 \times 10 ^ 5 \)。

题解

给每个字符一个目标位置,生成一个目标序列,然后统计一遍这个序列的逆序对就是答案。

考虑到 \(a\) 的逆序对数量要最少。那么自然我们想到对于相同字符,把他们的 \( a _ i \) 倒序赋值就是最优解。

这个结论比较显然,因为序列 \( a \) 越接近升序,他的逆序对就越少。

#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
inline int read(void)
{
    reg char ch = getchar();
    reg int res = 0;
    while (ch < '0' || '9' < ch)
        ch = getchar();
    while ('0' <= ch && ch <= '9')
        res = 10 * res + ch - '0', ch = getchar();
    return res;
}

const int MAXN = 2e5 + 5;

int n;
char s[MAXN];     //字符串
stack<int> S[26]; //用栈维护字符位置
int pos[MAXN];    //目的序列

namespace BIT //用树状数组求逆序对
{
    inline int lowbit(reg int x)
    {
        return x & (-x);
    }
    int n, unit[MAXN];
    inline void Init(reg int S)
    {
        n = S;
        memset(unit, 0, sizeof(unit));
        return;
    }
    inline void update(reg int id, reg int val)
    {
        for (reg int i = id; i <= n; i += lowbit(i))
            unit[i] += val;
        return;
    }
    inline int query(reg int id)
    {
        reg int res = 0;
        for (reg int i = id; i; i ^= lowbit(i))
            res += unit[i];
        return res;
    }
} // namespace BIT

int main(void)
{
    scanf("%d%s", &n, s + 1);
    for (int i = 1; i <= n; ++i)
        S[s[i] - 'a'].push(i);
    for (reg int i = 1; i <= n; ++i)
    {
        pos[n - i + 1] = S[s[i] - 'a'].top(); //生成目的序列
        S[s[i] - 'a'].pop();
    }
    reg ll ans = 0;
    BIT::Init(n); //初始化
    for (reg int i = n; i >= 1; --i)
    {
        ans += BIT::query(pos[i]); //求逆序对
        BIT::update(pos[i], 1);
    }
    printf("%lld\n", ans); //输出
    return 0;
}
Pages: 1 2 3 4 5 6 7 8 9