Codeforces #723 div2 D

好難

但是我就是要把你給補了

#include <bits/stdc++.h>
using namespace std;
const int maxn =  1e5+10;
typedef long long ll;
string ans,s;
int a[maxn],cnt[maxn],save[maxn];
int sum[maxn][5];
void solve()
{
    int p[]={0,1,2,3,4};
    ll curmx = -1;

    cin>>s;
    int n = s.size();
    for(int i= 1;i<=4;i++)
    sum[0][i]=0,cnt[i]=0;

    for(int i=1;i<=n;i++)
    {
        a[i]=string("ANOT").find(s[i-1])+1;///映射ANOT 
    }
    ///a[i] 數組隻存放了1|2|3|4
    
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=n;j++) ///相當于枚舉原串
        cnt[i] =sum[j][i]=sum[j-1][i]+(i==a[j]); ///前j個位置裡面有多少個 種類為i的數量
    }
    
    ///目前位置的字首和

    do
    {
        for(int i=1;i<=4;i++)
            save[p[i]]= i;
        ll cur = 0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=4;j++)
            {
                if(save[j]<=save[a[i]])
                    continue;
                cur+=sum[i][j];
            }
        }
        if(cur>curmx)
        {
            curmx = cur;
            ans.clear();
            for(int i=1;i<=4;i++)
            ans+=string(cnt[p[i]],"ANOT"[p[i]-1]);
        }
    }while(next_permutation(p+1,p+5));

    cout<<ans<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t -- )
    solve();
    return 0;
}