Swap and Reverse

題面翻譯

題目描述

本題共有 $t$ 組數(shù)據(jù)。

給定一個(gè)長(zhǎng)度為 $n$ 的字符串 $s$ 和一個(gè)整數(shù) $k$，$s$ 只包含小寫(xiě)字母，你可以進(jìn)行若干次操作（可以是零次），具體操作如下：

• 選取一個(gè) $i$（$1\le i\le n?2$），交換 $a_i$ 和 $a_{i+2}$

• 選取一個(gè) $i$（$1\le i\le n?k+1$），翻轉(zhuǎn)區(qū)間 $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$

輸出經(jīng)過(guò)若干次操作后得到的的按字典順序排列的最小字符串。

輸入格式

第一行包含一個(gè)正整數(shù) $t$，具體含義見(jiàn)上。

第二行包含兩個(gè)正整數(shù) $n$ 和 $k$。

接下來(lái)一行 包含一個(gè)長(zhǎng)度為 $n$ 的字符串 $s$。

輸出格式

對(duì)于每個(gè)測(cè)試用例，在進(jìn)行若干次操作后輸出按字典順序排列的最小字符串。

數(shù)據(jù)范圍

$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.

題目大意

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

解題思路

觀(guān)察這兩種操作

• 交換 $a_i$ 和 $ a_{i+2} $ 可以得出此操作為交換距離為 $2$ 的位數(shù)操作，即偶數(shù)位可以互換，

奇數(shù)位可以互換。

• 此時(shí)我們觀(guān)察第二種操作，選取一個(gè) $i$（$1\le i\le n?k+1$），翻轉(zhuǎn)區(qū)間 $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$

  • 當(dāng) $k$ 為偶數(shù)的時(shí)候，第二種操作就可以交換距離為奇數(shù)的字符，那么結(jié)合第一

  種操作，我們就可以交換偶數(shù)與偶數(shù)，奇數(shù)與奇數(shù)，偶數(shù)與奇數(shù)，奇數(shù)與偶數(shù)的

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

  • 當(dāng) $k$ 為奇數(shù)的時(shí)候，只能交換距離為偶數(shù)的字符，也就是說(shuō)只能交換奇數(shù)與奇

  數(shù)，偶數(shù)與偶數(shù)位置的字符了，所以我們分別針對(duì) $n$ 的奇偶性分別排序輸出即可

#include<bits/stdc++.h>
using namespace std;
const  int N=1e5+10;
int t;
char s[N];  //存儲(chǔ)原始字符
char j[N],o[N]; //分別存儲(chǔ)奇數(shù)與偶數(shù)位的字符
int main()
{cin>>t;while(t--){int n=0,k=0;int l=0,u=0;   //分別記錄偶數(shù)與奇數(shù)的數(shù)量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];//奇數(shù)}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;
}