题解 P5041 [HAOI2009]求回文串

· · 题解

（我都没有发现交换次数是逆序对！/jk）

这里提供一个不一样的做法，

首先判断-1就直接看有没有超过两个出现次数为奇数的字符

发现数据范围过大，应该是贪心之类的算法，

一个 naive 考虑从最外面向里面一层一层的求交换次数，每次枚举最左边和最右边填什么字符，选择代价最小的一个填上去，求出总的答案即可。

填一个字符的代价就是找到最靠左的把它放到最左边，找到一个最靠右的，把它放到最右边的交换次数和。

发现这个自己手玩以下 hack 不掉，（后面我们慢慢讨论贪心证明的问题）

考虑实现，同一个字符交换后相对顺序不会发生改变，用一个 deque 存下来，每次一定是使用这个字符最左边和最右边的两个字符， pop_back 和 pop_front 即可

若我们删除了两个字符，相当于在原串挖两个空，考虑用树状数组动态维护当前位置实际位置在哪里。

举个例子

时间复杂度是O(n*26*\log n)

考虑证明上面的贪心，我们发现如果我们证明当前选择对后面没有影响即可

假设当前选择的是 AA，下一次选择的是 BB

我们分为3种情况：

1.若呈包含关系，比如 ABBA （这时明显 A 优于 B ），我们贪心的选择是更优的

2.若呈相交关系，比如 ABAB （ BABA 同理），这时若先选 A ，则对选 B 的影响是 -1，先选 B 对 A 的影响也是 -1 ,所以我们贪心选不会影响后面选择。

3.若呈不相交关系，比如 AABB （ BBAA 同理）若先选 A ，则对 B 的影响是 -2 ，先选 B 对 A 的影响是 -2 ，贪心不影响后面选择。

贪心会使答案更优，且不影响选择，所以贪心正确。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read()
{
    char c;
    int w=1;
    while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
    int ans=c-'0';
    while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
    return ans*w;
}
const int xx=1e6+5;
char s[xx];
deque<int>t[26];
int lb(int x){return x&(-x);}
int sum[xx],n;
void add(int x,int y)
{
    for(;x<=n;x+=lb(x))sum[x]+=y;
}
int ask(int x)
{
    int ans=0;
    for(;x;x-=lb(x))ans+=sum[x];
    return ans;
}
signed main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++)t[s[i]-'A'].push_back(i);
    int tot=0;
    for(int i=0;i<26;i++)if(t[i].size()&1)tot++;
    if(tot>1)return puts("-1"),0;
    ll ans=0;
    for(int i=1;i<=n/2;i++)
    {
        int res=2147483647;
        int now=0;
        for(int j=0;j<26;j++)
        {
            if(t[j].size()<2)continue;
            int l=t[j][0]-ask(t[j][0])-1;//求距离前面还有多远 
            int r=(n-(i-1)*2)-(t[j][t[j].size()-1]-ask(t[j][t[j].size()-1]));//求距离后面还有多远 
            if(l+r<res)res=l+r,now=j;
        }
        ans+=res;
        add(t[now][0],1);//在树状数组里面挖空 
        add(t[now][t[now].size()-1],1);
        t[now].pop_front();
        t[now].pop_back();
    }
    cout<<ans<<"\n";
    return 0;
}