CF1526D Kill Anton 做题记录

给定一个字符串 $a$，你可以任意打乱 $a$ 中字符的顺序，记打乱后的字符串为 $b$。记 $b$ 的价值为将 $b$ 转换为 $a$ 所需的最小交换次数（交换指交换两个相邻元素）。输出价值最大的 $b$。

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

$1\le |a|\le 10^5$。

这种题都有两个方向：直接构造 $T$ 和研究 $T$ 还原到 $S$ 的性质。

发现直接构造不好做，那么考虑研究 $T$ 还原到 $S$ 的性质。

显然若知道了 $p_i$ 表示 $T_i$ 最终要去的位置，那么把 $T$ 还原到 $S$ 所需的操作就是 $p$ 的逆序对个数。

不难发现，对于两个满足 $x<y,T_x=T_y$ 的位置 $x,y$，$p_x<p_y$ 显然是最优的，因为 $p_x>p_y$ 会增加至少一对逆序对，并且由于一个更大的数被放到前面了，所以逆序对个数并不会减少。

继续研究两个满足 $x<y,T_x=T_y,T_{[x+1,y-1]}\not=T_x$ 的两个位置 $x,y$，考虑 $x<k<y$，令 $Sx=\{k|x<k<y,p_x>p_k\},Sy=\{k|x<k<y,p_y<p_k\}$，显然有 $Sx\cap Sy=\varnothing$，那么令 $Sz=\{k|x<k<y\}-Sx-Sy$。

显然所有 $k\in Sx$ 和 $k\in Sy$ 的 $k$ 对逆序对个数都有 $1$ 的贡献，所有 $k\in Sz$ 的 $k$ 对逆序对个数都没有贡献。那么考虑把 $T_x$ 换到 $T_{y-1}$ 和把 $T_{y}$ 换到 $T_{x+1}$ 这两种操作：

• 把 $T_x$ 换到 $T_{y-1}$，此时逆序对个数会减少 $|Sx|$，但是又会加上 $|Sy|$；
• 把 $T_y$ 换到 $T_{x+1}$，此时逆序对个数会减少 $|Sy|$，但是又会加上 $|Sx|$；

并且两种操作都会造成一些额外的非负的来自 $k\in Sz$ 的逆序对个数贡献，这两种操作中对逆序对贡献更多的操作的贡献肯定至少为 $0$，那么让 $T_x$ 和 $T_y$ 相邻显然更优。

所以所有相同的字符相邻肯定是最优的。

那么枚举所有 $4!=24$ 种字符串，$O(n\log n)$ 计算逆序对个数即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int S=200005;

int n;
char a[S];
vector<int> pos[4];
int b[S],c[S];
char res[S];

inline int id(char x)
{
	return x=='A'?0:(x=='N'?1:(x=='T'?2:3));
}

inline char di(int x)
{
	return x==0?'A':(x==1?'N':(x==2?'T':'O'));
}

inline void add(int pos,int val)
{
	for(int i=pos;i<=n;i+=i&-i) c[i]+=val;
}

inline int que(int pos)
{
	int res=0;
	for(int i=pos;i>=1;i-=i&-i) res+=c[i];
	return res;
}

inline void slove()
{
	scanf("%s",a+1);
	n=strlen(a+1);
	for(int i=0;i<4;i++) pos[i].clear();
	for(int i=1;i<=n;i++) pos[id(a[i])].push_back(i);
	long long mx=-1;
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			if(i==j) continue;
			for(int k=0;k<4;k++)
			{
				if(i==k||j==k) continue;
				for(int l=0;l<4;l++)
				{
					if(i==l||j==l||k==l) continue;
					int p=0;
					for(int &u:pos[i]) b[++p]=u;
					for(int &u:pos[j]) b[++p]=u;
					for(int &u:pos[k]) b[++p]=u;
					for(int &u:pos[l]) b[++p]=u;
					for(int o=1;o<=n;o++) c[o]=0;
					long long pre=0;
					for(int o=n;o>=1;o--)
					{
						pre+=que(b[o]-1);
						add(b[o],1);
					}
					if(pre>mx)
					{
						mx=pre;
						p=0;
						for(int &u:pos[i]) res[++p]=di(i);
						for(int &u:pos[j]) res[++p]=di(j);
						for(int &u:pos[k]) res[++p]=di(k);
						for(int &u:pos[l]) res[++p]=di(l);
					}
				}
			}
		}
	}
	res[n+1]=0;
	printf("%s\n",res+1);
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}