AT3733 [ARC088C] Papple Sort解题报告

解题报告

AT3733 [ARC088C] Papple Sort解题报告：

更好的阅读体验

题意

• 给定一个字符串$S$，可以进行若干次操作使得某两个相邻字母交换，求最少需要多少次操作让这个字符串成为回文串。
• $1\leqslant |S|\leqslant 2\times 10^5$。

分析

我们考虑每一个字符在最后的回文串里会与什么字符配对，发现从前往后第$x$个字符$c$一定会与从后往前第$x$个字符$c$匹配。（因为交叉式的匹配一定不优于或等价与包含式的匹配）

解释：
c...c...c...c
第一个c与第四个c匹配一定比第一个c与第三个c匹配等价或更优

而确定了匹配的对象之后，我们不难发现对于两对匹配了的字符，不交换位置一定比交换位置优。

解释：
假设匹配后是：c...b...b...c
如果交换成匹配b...c...c...b，也不会对其他的匹配有任何帮助，还不如不交换位置

这样我们就有了一个基本的思路：枚举每一个没有匹配过的字符，找到与它对应的字符，然后把这两个字符移动到最外侧的位置，这样就可以把这一对字符视为已删除。

考虑当前字符之前的所有字符已经进行过了操作，所以$i$一定在最外侧，我们只需要把与它匹配的字符移动到末尾，我们只需要用一个树状数组维护当前的字符就好了。

对于单独的字符，我们标记一个flg，然后在之后的操作的费用都增加$1$就好了（因为之后的匹配的左端点需要向左移动一次）。

代码

#include<stdio.h>
#include<iostream>
#include<vector>
#define lowbit(x) x&-x
using namespace std;
const int maxn=200005,maxk=30;
int all,flg,n,now;
long long ans;
int a[maxn],used[maxn],t[maxn];
string s;
vector<int>v[maxk];
void update(int x,int v){
    for(int i=x;i<=n;i+=lowbit(i))
        t[i]+=v;
}
int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=t[i];
    return res;
}
int main(){
    cin>>s;
    n=s.size();
    for(int i=0;i<s.size();i++){
        a[i+1]=s[i]-96;
        v[s[i]-96].push_back(i+1);
    }
    for(int i=1;i<=26;i++)
        if(v[i].size()&1)
            all++;
    if(all>1){
        puts("-1");
        return 0;
    }
    for(int i=1;i<=n;i++)
        update(i,1),now++;
    for(int i=1;i<=n;i++){
        if(used[i])
            continue;
        int x=v[a[i]][v[a[i]].size()-1];
        if(x==i){
            v[a[i]].pop_back(),flg=1;
            used[i]=1,update(i,-1),now--;
            continue;
        }
        v[a[i]].pop_back();
        ans+=1ll*(now-query(x))+flg;
        used[i]=used[x]=1;
        update(i,-1),update(x,-1),now-=2;
    }
    printf("%lld\n",ans);
    return 0;
}