Swap and Reverse 题解

Swap and Reverse

题面翻译

题目描述

本题共有 $t$ 组数据。

给定一个长度为 $n$ 的字符串 $s$ 和一个整数 $k$，$s$ 只包含小写字母，你可以进行若干次操作（可以是零次），具体操作如下：

• 选取一个 $i$（$1\le i\le n-2$），交换 $a_i$ 和 $a_{i+2}$

• 选取一个 $i$（$1\le i\le n-k+1$），翻转区间 $s_{[i,i+k-1]}$。如果 $s=s_1,s_2,\dots ,s_{i-1},s_i,s_{i+1},\dots ,s_{i+k-2},s_{i+k-1},s_{i+k},\dots ,s_{n-1},s_n$，可将其改为：$s=s_1,s_2,\dots ,s_{i-1},s_{i+k-1},s_{i+k-2},\dots ,s_{i+1},s_i,s_{i+k},\dots ,s_{n-1},s_n$

输出经过若干次操作后得到的的按字典顺序排列的最小字符串。

输入格式

第一行包含一个正整数 $t$，具体含义见上。

第二行包含两个正整数 $n$ 和 $k$。

接下来一行 包含一个长度为 $n$ 的字符串 $s$。

输出格式

对于每个测试用例，在进行若干次操作后输出按字典顺序排列的最小字符串。

数据范围

$1\le t\le 10^4,1\le k\le n\le 10^5$。

Translate by @Moss_spresd

题目描述

You are given a string $ s $ of length $ n $ consisting of lowercase English letters, and an integer $ k $ . In one step you can perform any one of the two operations below:

• Pick an index $ i $ ( $ 1 \le i \le n - 2 $ ) and swap $ s_{i} $ and $ s_{i+2} $ .
• Pick an index $ i $ ( $ 1 \le i \le n-k+1 $ ) and reverse the order of letters formed by the range $ [i,i+k-1] $ of the string. Formally, if the string currently is equal to $ s_1\ldots s_{i-1}s_is_{i+1}\ldots s_{i+k-2}s_{i+k-1}s_{i+k}\ldots s_{n-1}s_n $ , change it to $ s_1\ldots s_{i-1}s_{i+k-1}s_{i+k-2}\ldots s_{i+1}s_is_{i+k}\ldots s_{n-1}s_n $ .

You can make as many steps as you want (possibly, zero). Your task is to find the lexicographically smallest string you can obtain after some number of steps.

A string $ a $ is lexicographically smaller than a string $ b $ of the same length if and only if the following holds:

• in the first position where $ a $ and $ b $ differ, the string $ a $ has a letter that appears earlier in the alphabet than the corresponding letter in $ b $ .

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le k < n \le 10^5 $ ).

The second line of each test case contains the string $ s $ of length $ n $ consisting of lowercase English letters.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, print the lexicographically smallest string after doing some (possibly, zero) steps.

样例 #1

样例输入 #1

5
4 2
nima
5 3
panda
9 2
theforces
7 3
amirfar
6 4
rounds

样例输出 #1

aimn
aandp
ceefhorst
aafmirr
dnorsu

提示

In the first test case, we can obtain the string “aimn” using the following operations:

1. Reverse the range $ [3,4] $ . The string turns into “niam”.
2. Swap $ s_1 $ and $ s_3 $ . The string turns into “ainm”.
3. Reverse the range $ [3,4] $ . The string turns into “aimn”.

It can be proven that we cannot obtain any string lexicographically smaller than “aimn”. Therefore, “aimn” is the answer.

In the second test case, we can obtain the string “aandp” using the following operations:

1. Swap $ s_3 $ and $ s_5 $ . The string turns into “paadn”.
2. Swap $ s_1 $ and $ s_3 $ . The string turns into “aapdn”.
3. Swap $ s_3 $ and $ s_5 $ . The string turns into “aandp”.

It can be proven that we cannot obtain any string lexicographically smaller than “aandp”. Therefore, “aandp” is the answer.

题目大意

两种操作后，能得到的字典序排列最小的字符串

解题思路

观察这两种操作

• 交换 $a_i$ 和 $ a_{i+2} $ 可以得出此操作为交换距离为 $2$ 的位数操作，即偶数位可以互换，

奇数位可以互换。

• 此时我们观察第二种操作，选取一个 $i$（$1\le i\le n-k+1$），翻转区间 $s_{[i,i+k-1]},$

  $s=s_1,s_2,s_{i-1},s_i,s_{i+1},\dot{,}{s}_{i+k-2},s_{i+k-1},s_{i+k},\dots ,s_{n-1},s_n$，

  $s=s_1,s_2,s_{i-1},s_{i+k-1},s_{i+k-2},\dots ,s_{i+1},s_i,s_{i+k},\dots ,s_{n-1},s_n$

  • 当 $k$ 为偶数的时候，第二种操作就可以交换距离为奇数的字符，那么结合第一

  种操作，我们就可以交换偶数与偶数，奇数与奇数，偶数与奇数，奇数与偶数的

  字符了，那么我们直接 $sort\left ( \right ) $ 排序即可。

  • 当 $k$ 为奇数的时候，只能交换距离为偶数的字符，也就是说只能交换奇数与奇

  数，偶数与偶数位置的字符了，所以我们分别针对 $n$ 的奇偶性分别排序输出即可

#include<bits/stdc++.h>
using namespace std;
const  int N=1e5+10;
int t;
char s[N];  //存储原始字符
char j[N],o[N]; //分别存储奇数与偶数位的字符
int main()
{cin>>t;while(t--){int n=0,k=0;int l=0,u=0;   //分别记录偶数与奇数的数量cin>>n>>k>>s;if(k%2==0){sort(s,s+n);cout<<s<<endl;}else {if(n%2==0){for(int i=0;i<n;i++){if((i+1)%2==0)o[l++]=s[i];else j[u++]=s[i];}sort(o,o+l);sort(j,j+u);for(int i=0;i<l;i++) cout<<j[i]<<o[i];cout<<endl;}else {for(int i=0;i<n;i++){if((i+1)%2==0)o[l++]=s[i];else j[u++]=s[i];//奇数}sort(o,o+l);sort(j,j+u);for(int i=0;i<l;i++) cout<<j[i]<<o[i];cout<<j[u-1];cout<<endl;}}}return 0;
}