CF1864B Swap and Reverse

思路

刚看懂题意时感觉很难，但是观察样例后，大胆猜测，\(k\) 为偶数时，直接排序；\(k\) 为奇数时，分奇偶位排序。

快速了写了程序，一交果然 AC。

其实很简单，这里给出证明：

首先，操作 \(1\) 保证了奇数位和偶数位上的字符可以任意变动顺序。

然后，操作 \(2\) 当 \(k\) 为偶数时，可以改变一个字符的位置的奇偶性，可以先通过操作 \(2\) 把字符放在应该的奇偶位上，再用操作 \(1\) 即可，因为 \(k<n\) 所以不会出现没办法使用操作 \(2\) 的情况，但是操作 \(2\) 一次会改变 \(k\) 个字符的奇偶性，如何证明一定可以把所有的字符的位置都改变成想要的奇偶呢？因为 \(k<n\) 且 \(k\) 为偶数，所以一定有奇偶位可以不在某次操作 \(2\) 的范围内，所以可以把要转换的字符经过操作 \(2\) 后，移出去，然后再进行一次操作 \(2\) 把其他字符再转换回去，等于一次交换了两个字符的位置的奇偶性，因为需要调整的奇偶性一定是成对的，所以一定可以交换到自己想要的奇偶性位置。

其次，是操作 \(2\) 当 \(k\) 为奇数时，因为 \(k\) 为奇数，所以无法改变奇偶性，所以只能按位置分奇偶排序。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,m;
char ch[100005],s1[50005],s2[50005]; 
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%s",&n,&m,ch+1);
		if(m%2==0){sort(ch+1,ch+n+1),printf("%s\n",ch+1);continue;}
		for(int i=1;i<=n;++i)
		{
			if(i%2) s1[(i+1)/2]=ch[i];
			else s2[i/2]=ch[i];
		}
		sort(s1+1,s1+(n+1)/2+1),sort(s2+1,s2+n/2+1);
		for(int i=1;i<=n/2;++i) printf("%c%c",s1[i],s2[i]);
		if(n%2) printf("%c",s1[(n+1)/2]);
		puts("");
	}
	return 0;
}