每日一题cf

Swap and Reverse

题意：

给定一个长度为n的正整数数组，给定k。可以进行任意次一下操作

• 选定$i$，交换$a_i$和$a_{i+2}$的值
• 选定$i$，对区间$[a_i,a_{i+k-1}]$进行翻转

题解：

• 对于操作一：只能交换下标奇偶性相同的值。
• 对于操作二：若k为奇数，也只能交换下标奇偶性相同的值，若k为偶数，结合操作一则可以任意交换两个相邻的元素，所以对于所有位置元素可以任意交换。

代码：

#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1e5+10;
typedef long long ll;

char str[N];

void sovle() {
	
	int n, k;
	cin >> n >> k;
	cin >> str;
//当k为奇数时，回用到进行分下标为奇数和偶数排序
	vector<char> a, b;
	
	if (k % 2 == 0) {
		sort(str, str + n);
		for (int i = 0; i < n; i++)cout << str[i];
	}
	else {
		
//只需要分奇数和偶数排序，就能涵盖所有点
		
		for (int i = 0; i <= n - 1; i += 2) a.push_back(str[i]);
		for (int i = 1; i <= n - 1; i += 2) b.push_back(str[i]);
		
		sort(a.begin(), a.end());
		sort(b.begin(), b.end());
		
//交叉打印
		int l1 = 0, l2 = 0;
		
		for (int i = 1; i <= n; i++) {
			if (i % 2) {
				cout << a[l1];
				l1++;
			}
			else {
				cout << b[l2];
				l2++;
			}
		}
	}
	
	cout << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t;
	cin >> t;
	while (t--) {
		sovle();
	}
	return 0;
}