B、Swap and Reverse

跳转原题点击此：该题地址

1、题目大意

给你一个字符串和k，你可以对该字符串做一下两个操作：

交换\(a_i\) 和 \(a_{i+2}\)的字符；
对 \([i, i+k-1]\) 这个区间的字符就行反转；
问你通过这两个操作后，原字符串所能生成新的字典序最小的字符串是什么。

2、题目解析

我们发现，操作一是对同奇或同偶下标的字符进行交换。而操作二则随着k的奇偶而改变：

当k是奇数时，与操作一类似，只能对同奇或同偶下标的字符进行交换，例如：当k为3时，只能对 \([i, i + 2]\) 这个区间交换，原数的奇偶不会发生改变，所以奇数下标和偶数下标的字符分别按照字典序排序。
当k是偶数时，我们发现当对\([i, i + k - 1]\) 和 \([i + 1, i + k]\)这个两个区间进行反转时，\(a_{i+k-1}\) 和 \(a_{i+k}\)这两个字符下标的奇偶发生了改变，而其余字符不改变。此时我们就能通过k为奇数时的操作改变新的字符。所以可以通过若干次操作一和操作二达到所有字符按照字典序排序。
举例：\([1,2,3,4,5]\)，\(k = 4\)，两次反转后结果为\([4,5,1,2,3]\)，我们发现，4和5的奇偶下标被改变了，其余字符的下标依旧。

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5+10;
int T;
int n, k;
string s;

void solve()
{
	cin >> n >> k;
	cin >> s;
	// 如果是偶数，可以通过[i, i + k - 1]和[i + 1, i + k]来改变第i+k-1和第i+k位两个元素的奇偶位
	// 然后就能通过k为奇数时的操作来改变位置
	if(! (k & 1))
	{
		sort(s.begin(), s.end());
		cout << s << endl;
	}
	// 如果是奇数，无论是哪种操作，奇数位只能和奇数位交换，偶数位同理
	else
	{
		string t[2];
		for(int i = 0; i < s.size(); i++)
			t[i % 2] += s[i];
		// 奇偶分别排序
		sort(t[0].begin(), t[0].end());
		sort(t[1].begin(), t[1].end());
		
		for(int i = 0; i < t[0].size(); i++)
		{
			cout << t[0][i];
			if(i < t[1].size())	// 存入偶数位的字符，因为字符串的奇数长度一定大于等于偶数长度
				cout << t[1][i];
		}
		cout << endl;
	}
}

int main()
{
	cin >> T;
	while (T--)
	{
		solve();
	}

	return 0;
}