【2022 NOIP 模拟赛 46】Palindrome 做题记录

给定一个字符串 $a$，你每次可以交换 $a$ 的相邻两个字符，问最少进行多少次交换才能使得 $a$ 变为回文串。数据保证一定能够在有限次交换操作后使得 $a$ 变为回文串。

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

设 $p_i$ 表示最后第 $i$ 个位置的字符原来是哪个位置上的，显然答案就是 $p$ 的逆序对个数，并且确定了 $p_{[1,\lfloor\frac{n}{2}\rfloor]}$ 就可以确定 $p_{[\lfloor\frac{n}{2}\rfloor+1,n]}$。

这里有个结论：$p_{[1,\lfloor\frac{n}{2}\rfloor]}$ 一定是递增的。

证明：

若存在 $1\le i< \lfloor\frac{n}{2}\rfloor$ 满足 $p_i>p_{i+1}$，则我们可以交换 $p_i$ 和 $p_{i+1}$，此时逆序对个数一定会减 $1$，相应的我们也要交换 $p_{n-i}+1$ 和 $p_{n-i}$，这会让逆序对个数加 $1$ 或者减 $1$，所以这样调整一定是不劣的。

那么乱贪就行了，代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <deque>

using namespace std;

const int S=1000005;

int n;
char a[S];
deque<int> q[30];
int c[S],res[S];

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

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

int main()
{
	scanf("%s",a+1);
	n=strlen(a+1);
	for(int i=1;i<=n;i++) a[i]=a[i]-'a'+1;
	for(int i=1;i<=n;i++) q[a[i]].push_back(i);
	for(int i=1;i<=n/2;i++)
	{
		int mnval=1e8,idx=0;
		for(int j=1;j<=26;j++)
		{
			if(q[j].size()>1)
			{
				int pre=abs(q[j].front()-i);
				if(pre<mnval) mnval=pre,idx=j;
			}
		}
		res[i]=q[idx].front();
		res[n-i+1]=q[idx].back();
		q[idx].pop_front();
		q[idx].pop_back();
	}
	if(n&1) for(int j=1;j<=26;j++) if(q[j].size()>=1) res[n/2+1]=q[j].front();
	long long ans=0;
	for(int i=n;i>=1;i--)
	{
		ans+=que(res[i]);
		add(res[i],1);
	}
	printf("%lld\n",ans);
	return 0;
}