CF1526D　「Kill Anton」

原题链接

原题翻译

题外话：

首先拜谢drk，感谢他提供的证明方法/bx/bx/bx/bx

题意：

给定一个字符串a（只包含N,A,T,O四种字符），你可以任意打乱a中字符的顺序，记打乱后的字符串为b。记b的价值为将b转换为a所需的最小交换次数（交换指交换两个相邻元素）。输出b使得b的价值最大。

若有多种答案，任意输出一种。

SAMPLE I/O

I

4
ANTON
NAAN
AAAAAA
OAANTTON

O

NNOTA
AANN
AAAAAA
TNNTAOOA

思路：

首先来补充几个前置知识：

逆序对

逆序对就是序列中且的有序对。如何求一个序列的逆序对？

首先可以求出这个序列所有数对的排列数，就是对，然后减去不是逆序对的有序对，就是序列中且的有序对，那么看到这个发现可以用值域线段树来做。但因为线段树常数巨大~~卡的要死~~，可以将其替换为树状数组。

思路如下：

将原序列a[i]离散化;
ans = 0;
for i:1~n
    ans += query(a[i]);
    add(a[i], 1);
print(n*(n-1)/2-ans);

无重复元素的逆序对

解决了最基本的逆序对，现在再来看到这个：

P5149

现在校长在校园网上公布了一份座位表，位老师从左到右依次排成一行。老师们都对这个座位很满意。

然而到了开会时，校长不小心把座位表打乱了，老师们很不满。老师们并不在意自己的位置变了多少，但如果有一对老师和，他们原来的座位是在左边，现在变成了在右边，那么这一对老师便会贡献一单位不满值。

校长想知道这些老师的总不满值是多少。

发现不满值就是逆序对个数，我们可以给每一个名字赋一个初值，使这些初值满足原本的顺序排列。之后根据这些初值，把打乱的顺序表的名字都变成数字，这样就可以看出来原本的顺序关系，然后再求逆序对个数即可。

思路如下：

for i:1~n
    cin>>name;
    if(idx[name]==0)
        idx[name] = ++num;
for i:1~n
    cin>>name;
    a[i] = idx[name];
ans = 0;
for i:1~n
    ans += query(a[i]);
    change(a[i], 1);
print(n*(n-1)/2-ans);

有重复元素的逆序对

P3531

给出两个长度相同的的只含大写字母的字符串，每次可以交换中相邻两个字符，求最少的交换次数，使得交换后的得到的字符串与相同。

发现到这道题和上面那道题很相似，也考虑逆序对。但是这些字符有重复的地方。那该怎么赋值呢？

首先，我们要知道，交换两个相同的字母是一次无效的交换。这个并没有减少逆序对的个数。比如说：BB->BB。所以我们一定不能让两个相同的字母交换，从而减少逆序对的个数。

根据这个结论，考虑将每个相同的字母按照出现的顺序编号。并且交换之后这些字母的相对出现顺序也不能改变。

举个例子：

ABBAAB->BBBAAA

这里赋值就是

A	B	B	A	A	B	->	B	B	B	A	A	A
1	2	3	4	5	6		2	3	6	1	4	5

让他们的相对位置不改变，就可以避免出现交换相同字母的情况。

思路如下：

input(n);
input(s+1);//字符串存储从1开始
num = 0;
for(int i=1;i<=n;i++)
    idx[s[i]-'A'].push(i);
input(s+1);
ans = 0;
for i:1~n
    a[i] = idx[s[i]-'A'].front();
    idx[s[i]-'A'].pop();
    ans += query(a[i]);
    change(a[i], 1);
print(n*(n-1)/2-ans);

有重复元素的逆序对与排列的结合

最后再来看到原题：

我们要考虑如何构造字符串使他的逆序对数最大。（这里为了方便，假设这4个字符为ABCD）

只有两种字符的情况

假设只有两种字符的情况：

BBABABABABAAA

现在我们把A固定：

BBABABABABAAA

然后再钦定一个分界线，将B都往这个分界线上面移动，这样就增加了逆序对的个数（就是所有B经过A的个数之和）：
AAABBBB | BBAAAA

这个时候我们会发现这个字符串总是A...AB…BA...A的形式，然后我们看到分界线左边的B比右边的B多，那么就把这些B都绑到一起，一起往右移动：

AAAAAAABBBBBB

每个分界线左边的B往右移动一个字符贡献+1，每个分界线右边的B往右移动贡献-1，所以发现，当移到最边上时，贡献是最多的。

同理可得，如果分界线左边的B比右边的少，那么往左边移动到边界；如果分界线左边的B和右边的一样，那么随便选定一个方向移动到最边上，贡献都不变。为了讨论方便，这里也把他移到最边上。

我们发现，不管这个分界线选到哪里，最后都会变为形如A…AB…B的形式或者B…BA…A的形式，只是顺序不一样。这里可以考虑枚举两种顺序，用上一道题的思路来解决这种情况，然后求最大值。

有多种字符的情况

那么多种字符的话呢？

这里我们可以先把A拎出来，把其他字符都看成同一种字符

就会变成类似A?A???A??AAA??的字符串。

经过一轮变换后，就变为了A…A?…?或是?…?A…A的形式。我们发现A是连到一起的。

之后再把B拎出来，经过一轮变换后B也就连到一起了。之后第三轮、第四轮变换之后C、D也就都是连在一起的。就变为了类似于C…CA…AD…DB…B的形式。

之后就像两种字符一样，枚举排列。因为只有种排列，很小，所以可以考虑枚举排列，然后像上一道题一样，把每一个字符根据顺序赋值，然后再根据顺序来给排列的每一个位置赋值，使每种字符的相对顺序不变。然后再计算逆序对的个数，求最大值，即可。

代码如下：

#include<bits/stdc++.h>
#define debug cerr<<"HERE"
using namespace std;
const int N = 2085<<7;
typedef long long ll;
ll n, tr[N];

int lowbit(int x){
    return x&-x;
}

void change(int x, ll w){
    while(x<=n){
        //cerr<<x<<endl;
        tr[x] += w;
        x += lowbit(x);
    }
}

ll query(int x){
    ll ans = 0;
    while(x){
        ans += tr[x];
        x -= lowbit(x);
    }
    return ans;
}
char c[N], re[] = "*NATO";
int mp[128];
int tot[5], vis[5], now[5], res[N];
ll finans=0;

void solve(){
    queue<int> q[5];
    int nowcnt=0;
    for(int i=1;i<=4;i++){
        for(int j=1;j<=tot[now[i]];j++){
            q[now[i]].push(++nowcnt);
            //cerr<<now[i]<<" "<<nowcnt<<endl;
        }
    }
    //debug;
    ll nowans = 0;
    for(int i=1;i<=n;i++){
        int nowidx = q[mp[c[i]]].front(); q[mp[c[i]]].pop();
        //cerr<<nowidx<<endl;
        nowans += query(nowidx);
        change(nowidx, 1);
    }
    nowans = n*(n-1)/2-nowans;
    if(nowans > finans){
        nowcnt = 0;
        finans = nowans;
        for(int i=1;i<=4;i++){
            for(int j=1;j<=tot[now[i]];j++){
                res[++nowcnt] = now[i];
            }
        }
    }
    for(int i=1;i<=n;i++){
        tr[i] = 0;
    }
}

void dfs(int nowt){
    //cerr<<nowt<<endl;
    if(nowt==5) solve();
    for(int i=1;i<=4;i++){
        if(!vis[i]){
            vis[i] = 1;
            now[nowt] = i;
            dfs(nowt+1);
            vis[i] = 0;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    mp['N'] = 1, mp['A'] = 2, mp['T'] = 3, mp['O'] = 4;
    cin>>t;
    while(t--){
        cin>>(c+1);
        n = strlen(c+1);
        for(int i=1;i<=n;i++){
            tot[mp[c[i]]] ++;
        }
        finans = -1;
        dfs(1);
        //cout<<finans<<" ";
        for(int i=1;i<=n;i++){
            cout<<re[res[i]];
        }
        cout<<"\n";
        for(int i=1;i<=4;i++){
            tot[i] = 0;
        }
    }
    return 0;
}

CF1526D 「Kill Anton」

题外话：

题意：

SAMPLE I/O

I

O

思路：

逆序对

无重复元素的逆序对

有重复元素的逆序对

有重复元素的逆序对与排列的结合

只有两种字符的情况

有多种字符的情况

代码如下：

CF1526D　「Kill Anton」