【Atcoer】ARC088 E - Papple Sort

【题目】E - Papple Sort

【题意】给定长度为n的小写字母串，只能交换相邻字母，求形成回文串的最小步数。n<=2*10^5。

【算法】数学

【题解】官方题解

本题题解中有以下重要的思想：

①分析多复杂因素相互干扰的问题时，先排除无关因素，然后转化关联因素为独立因素后逐个分析。

②位置移动的问题中，常用转绝对位置为相对位置，考虑两两相对的情况。

③回文的性质：嵌套。

奇数串和偶数串对做法没有影响，忽略。

首先，对于串中所有字母x，交叉移动没有任何意义，所以一定是最左-最右,次左-次右...的组合。这样我们可以将长度为n的串视为n/2对字母。

现在，考虑串中任意两对字母AA和BB的相对位置和对应交换策略：

1.[...A...A...B...B...]，A作为外围字母（A移动到B右边对称位置）和B作为外围字母（B移动到A左边对称位置）移动距离一致，无影响。

2.[...A...B...A...B...]，移动距离一致，无影响。

3.[...A...B...B...A...]，A-A必须作为外围字母而B-B必须作为内围字母。

注意：这里很容易认为在前两种情况中，A移动还是B移动会对中间省略号的部分造成影响。但是请注意这里是只考虑A-A和B-B这两对的相对位置，从A必须相对于B-B回文而不是全局回文也可以看出。在每次移动都会牵扯很多数字的情况下，我们刻意不在所有数字都存在的全局范围内讨论移动，而是单独考虑两两对之间的位置和对应策略，这样就不会有全局的复杂关联因素。

综上所述，为了保证不会发生第三种情况的内越外，当(l1,r1)和(l2,r2)满足l1<l2时，(l1,r2)必须是外围字母。

因此，必须从左往右做，每次将对应字母移动到回文位置，这样就能保证所有(l2,r2),l1>l2的r2都在最外围(不会越过)，而会越过所有(l2,r2),l1<l2的r2。

提前判断无解后，统计步数用树状数组记录当前剩余元素来实现（每次都视为移动到n，移动过的元素在最外围直接删除）。

#include<cstdio>

#include<cstring>

#include<cctype>

#include<cmath>

#include<queue>

#include<stack>

#include<set>

#include<vector>

#include<algorithm>

#define ll long long

#define lowbit(x) x&-x

using namespace std;

int read(){

    char c;int s=,t=;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

int min(int a,int b){return a<b?a:b;}

int max(int a,int b){return a<b?b:a;}

int ab(int x){return x>?x:-x;}

//int MO(int x){return x>=MOD?x-MOD:x;}

//void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}

/*------------------------------------------------------------*/

const int inf=0x3f3f3f3f,maxn=;

int n,c[maxn],num[maxn];

bool vis[maxn];

char s[maxn];

vector<int>v[];

void modify(int x,int k){for(int i=x;i<=n;i+=lowbit(i))c[i]+=k;}

int query(int x){int ans=;for(int i=x;i>=;i-=lowbit(i))ans+=c[i];return ans;}

int main(){

    scanf("%s",s+);

    n=strlen(s+);

    for(int i=;i<=n;i++)num[s[i]-'a']++,v[s[i]-'a'].push_back(i);

    int ok=;

    for(int i=;i<;i++){

        if(num[i]%)ok++;

    }

    if(ok>){printf("-1");return ;}

    for(int i=;i<=n+;i++)modify(i,);

    ll ans=;

    for(int i=;i<=n;i++)if(!vis[i]){

        int c=s[i]-'a';

        int x=v[c][v[c].size()-];

        if(i==x){

            ans+=(query(n)-query(i))/;

        }

        else{

            ans+=(query(n)-query(x));

        }

        modify(i,-);modify(x,-);

        vis[i]=vis[x]=;

        v[c].erase(v[c].end()-);

    }

    printf("%lld",ans);

    return ;

}

巴特西

【Atcoer】ARC088 E - Papple Sort

最新文章

热门文章