DDOSvoid's Blog

CF 1526D Kill Anton

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

题目描述

http://codeforces.com/contest/1526/problem/D

Solution

首先我们知道本质上就是构造使得求逆序对的个数最大

手玩或者简单想一下能够发现，相同字母一定排在一起最优

所以我们 $4!$ 枚举一下顺序就好，时间复杂度 $O(4!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
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define maxn 100010
#define ll long long
using namespace std;

int n;

int cnt[4][maxn];

char s[maxn];

vector<int> A[4];

int ch[256], p[4], hc[4];
void work() {
    cin >> s + 1; n = strlen(s + 1);
    for (int i = 0; i < 4; ++i) {
        A[i].clear();
        for (int j = 1; j <= n; ++j) cnt[i][j] = 0;
    }
    for (int i = 1; i <= n; ++i) cnt[ch[s[i]]][i] = 1, A[ch[s[i]]].push_back(i); 
    for (int i = 0; i < 4; ++i)
        for (int j = 1; j <= n; ++j) cnt[i][j] += cnt[i][j - 1];
    for (int i = 0; i < 4; ++i) p[i] = i; ll ans = 0; int Ans[4] = { 0, 1, 2, 3 };
    do {
        ll sum = 0;
        for (int i = 0; i < 4; ++i) 
            for (auto u : A[p[i]])
                for (int j = i + 1; j < 4; ++j) sum += cnt[p[j]][u];
        if (sum > ans) {
            for (int i = 0; i < 4; ++i) Ans[i] = p[i]; 
            ans = sum;
        }
    } while (next_permutation(p, p + 4));
    for (int i = 0; i < 4; ++i) 
        for (int j = 1; j <= A[Ans[i]].size(); ++j) cout << (char) hc[Ans[i]];
    cout << "\n"; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    ch['A'] = 0; ch['N'] = 1; ch['T'] = 2; ch['O'] = 3;
    hc[0] = 'A'; hc[1] = 'N'; hc[2] = 'T'; hc[3] = 'O';
    
    int T; cin >> T; 
    while (T--) work(); 
    return 0;
}