Asusetic
0%

CF1526D Kill Anton

发表于 分类于 ， Valine：
本文字数： 1.2k 阅读时长 ≈ 1 分钟

CF1526D Kill Anton

应该能发现交换次数是和逆序对有关的，具体来说是原串的字符在构造的串中下一次出现的位置的数组的逆序对

比如 s=ANTON t=NNOTAs=\mathrm{ANTON} \ t=\mathrm{NNOTA} 位置数组为 P=[5,1,4,3,2]P=[5,1,4,3,2] 逆序对数为 77 需要交换七次

手玩或者口胡一下会发现如果相同的字符放在一起不会更劣

证明：

设我们现在找到的字符串长这样 ....AAAx....AyAA...\mathrm{....AAA_x....A_yAA...} (Ax,AyA_x,A_y 仅用于标记，这两个字符 PP 中分别位于 i,ji,j)

考虑两种合并方式 ....AAAxAy...AA...\mathrm{....AAA_{x}A_{y}...AA...} 和 ...AA...AxAyAA\mathrm{...AA...A_{x}A_{y}AA}

考虑第一种产生/消除的逆序对数量和为 D1=∑k=i+1j−1sign(Pk−Pi)D_1=\sum\limits_{k=i+1}^{j-1} \mathrm{sign}(P_k-P_i)

其中 sign(x)=x∣x∣\mathrm{sign}(x)=\dfrac{x}{|x|} 就是取符号

第二种为 D2=∑k=i+1j−1sign(Pj−Pk)D_2=\sum\limits_{k=i+1}^{j-1}\mathrm{sign}(P_j-P_k)

事实上不可能有 D1+D2<0D_1+D_2 < 0

这样就意味着至少存在有某个 kk 使得 sign(Pk−Pi)+sign(Pj−Pk)<0\mathrm{sign}(P_k-P_i)+\mathrm{sign}(P_j-P_k) < 0

即 $P_k < P_i $ 且 Pk>Pj⇒Pj<PiP_k > P_j \Rightarrow P_j <P_i 矛盾

那么有 D1+D2≥0D_1+D_2 \ge 0 意味着这两者中至少有一个大于等于 00

那么按同样的方法把所有的相同字符放在一起不会更劣

枚举放每种字符的顺序共 4!4! 种，每种 nlog⁡nn\log n 求逆序对比较大小即可

复杂度 O(nlog⁡n)O(n\log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int N = 100004;
string s;
int t;
int tmp[N];
long long qres;
int a[N];
void msort(int l, int r) {
    if (l >= r)
        return;
    int m = l + r >> 1;
    msort(l, m);
    msort(m + 1, r);
    int i = l, j = m + 1;
    int k = 0;
    while (i <= m && j <= r) {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            qres += 1ll * m - i + 1ll;
        }
    }
    while (i <= m)
        tmp[k++] = a[i++];
    while (j <= r)
        tmp[k++] = a[j++];
    for (i = l, k = 0; i <= r; i++, k++)
        a[i] = tmp[k];
}
int main() {
    cin >> t;
    auto turn = [&](char c) -> int {
        if (c == 'A') {
            return 1;
        }
        if (c == 'N') {
            return 2;
        }
        if (c == 'O') {
            return 3;
        }
        if (c == 'T') {
            return 4;
        }
    };
    while (t--) {
        cin >> s;
        vector<int> v[5];
        for (int i = 0; i < s.length(); i++) {
            v[turn(s[i])].push_back(i + 1);
        }
        char chr[]     = {'A', 'N', 'O', 'T'};
        string ans     = "";
        long long mmax = 0;
        do {
            qres       = 0;
            string res = "";
            int cnt    = 0;
            for (int i = 0; i < 4; i++) {
                for (auto p : v[turn(chr[i])]) {
                    res += chr[i];
                    a[++cnt] = p;
                }
            }
            msort(1, cnt);
            if (qres >= mmax) {
                mmax = qres;
                ans  = res;
            }
        } while (next_permutation(chr, chr + 4));
        cout << ans << endl;
    }
    return 0;
}
// Asusetic eru quionours