CF1864B Swap and Reverse 题解

注意到交换操作，无法改变下标的奇偶性，因此只能通过考虑翻转操作改变。注意到如果 \(i\) 是奇数，那么要令 \(i+k-1\) 为偶数的话 \(k\) 必须为偶数，若 \(i\) 是偶数，要令 \(i+k-1\) 是奇数的话，\(k\) 也应为偶数，而 \(k\) 为奇数的情况翻转了也无法改变奇偶性。

因此通过 \(k\) 的奇偶性进行分类，分完类 \(k\) 就没用了。

\(k\) 为偶数的时候，将整个字符串进行排序就好，反之按照下标的奇偶性进行分类排序。

#include <cstdio>
#include <algorithm>

int t;
int n,k;
int s1[100005],s2[100005];
int cnt1,cnt2;

void solve() {
	cnt1=cnt2=0;
	scanf("%d%d",&n,&k);
	char c;
	for(int i=1;i<=n;i++) {
		scanf(" %c",&c);
		if(i&1) s1[++cnt1]=c-'a';//按照下标奇偶性分类 
		else s2[++cnt2]=c-'a';
	}
	std::sort(s1+1,s1+cnt1+1);//排序 
	std::sort(s2+1,s2+cnt2+1);
	s1[cnt1+1]=s2[cnt2+1]=90;
	if(k&1) {//按照k的奇偶性分类 
		int tot1=0,tot2=0;
		for(int i=1;i<=n;i++) {
			if(i&1) printf("%c",s1[++tot1]+'a');
			else printf("%c",s2[++tot2]+'a');
		}
	} else {
		int tot1=1,tot2=1;
		for(int i=1;i<=n;i++) {
			if(s1[tot1]<s2[tot2]) {
				printf("%c",s1[tot1]+'a');
				++tot1;
			} else {
				printf("%c",s2[tot2]+'a');
				++tot2;
			}
		}
	}
	printf("\n");
}

int main() {
	scanf("%d",&t);
	while(t--) solve();
	return 0;
}