注意到交换操作，无法改变下标的奇偶性，因此只能通过考虑翻转操作改变。注意到如果 \(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;
}