长治网站制作公司,推广网站推荐,株洲在线论坛,样asp.net做网站Swap and Reverse
题面翻译
题目描述
本题共有 t t t 组数据。
给定一个长度为 n n n 的字符串 s s s 和一个整数 k k k#xff0c; s s s 只包含小写字母#xff0c;你可以进行若干次操作#xff08;可以是零次#xff09;#xff0c;具体操作如下#xff1a; 选…Swap and Reverse
题面翻译
题目描述
本题共有 t t t 组数据。
给定一个长度为 n n n 的字符串 s s s 和一个整数 k k k s s s 只包含小写字母你可以进行若干次操作可以是零次具体操作如下 选取一个 i i i 1 ≤ i ≤ n − 2 1\le i\le n-2 1≤i≤n−2交换 a i a_i ai 和 a i 2 a_{i2} ai2 选取一个 i i i 1 ≤ i ≤ n − k 1 1\le i\le n-k1 1≤i≤n−k1翻转区间 s [ i , i k − 1 ] s_{[i,ik-1]} s[i,ik−1]。如果 s s 1 , s 2 , … , s i − 1 , s i , s i 1 , … , s i k − 2 , s i k − 1 , s i k , … , s n − 1 , s n ss_1,s_2,\dots,s_{i-1},s_i,s_{i1},\dots,s_{ik-2},s_{ik-1},s_{ik},\dots,s_{n-1},s_n ss1,s2,…,si−1,si,si1,…,sik−2,sik−1,sik,…,sn−1,sn可将其改为 s s 1 , s 2 , … , s i − 1 , s i k − 1 , s i k − 2 , … , s i 1 , s i , s i k , … , s n − 1 , s n ss_1,s_2,\dots,s_{i-1},s_{ik-1},s_{ik-2},\dots,s_{i1},s_i,s_{ik},\dots,s_{n-1},s_n ss1,s2,…,si−1,sik−1,sik−2,…,si1,si,sik,…,sn−1,sn
输出经过若干次操作后得到的的按字典顺序排列的最小字符串。
输入格式
第一行包含一个正整数 t t t具体含义见上。
第二行包含两个正整数 n n n 和 k k k。
接下来一行 包含一个长度为 n n n 的字符串 s s s。
输出格式
对于每个测试用例在进行若干次操作后输出按字典顺序排列的最小字符串。
数据范围 1 ≤ t ≤ 1 0 4 , 1 ≤ k ≤ n ≤ 1 0 5 1\le t\le10^4,1\le k\le n\le10^5 1≤t≤104,1≤k≤n≤105。
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_{i2} $ .Pick an index $ i $ ( $ 1 \le i \le n-k1 $ ) and reverse the order of letters formed by the range $ [i,ik-1] $ of the string. Formally, if the string currently is equal to $ s_1\ldots s_{i-1}s_is_{i1}\ldots s_{ik-2}s_{ik-1}s_{ik}\ldots s_{n-1}s_n $ , change it to $ s_1\ldots s_{i-1}s_{ik-1}s_{ik-2}\ldots s_{i1}s_is_{ik}\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:
Reverse the range $ [3,4] $ . The string turns into “niam”.Swap $ s_1 $ and $ s_3 $ . The string turns into “ainm”.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:
Swap $ s_3 $ and $ s_5 $ . The string turns into “paadn”.Swap $ s_1 $ and $ s_3 $ . The string turns into “aapdn”.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} ai 和 $ a_{i2} $ 可以得出此操作为交换距离为 2 2 2 的位数操作即偶数位可以互换
奇数位可以互换。 此时我们观察第二种操作选取一个 i i i 1 ≤ i ≤ n − k 1 1\le i\le n-k1 1≤i≤n−k1翻转区间 s [ i , i k − 1 ] , s_{[i,ik-1]}, s[i,ik−1], s s 1 , s 2 , s i − 1 , s i , s i 1 , , ˙ s i k − 2 , s i k − 1 , s i k , … , s n − 1 , s n ss_1,s_2,s_{i-1},s_i,s_{i1},\dot,s_{ik-2},s_{ik-1},s_{ik},\dots,s_{n-1},s_n ss1,s2,si−1,si,si1,,˙sik−2,sik−1,sik,…,sn−1,sn s s 1 , s 2 , s i − 1 , s i k − 1 , s i k − 2 , … , s i 1 , s i , s i k , … , s n − 1 , s n ss_1,s_2,s_{i-1},s_{ik-1},s_{ik-2},\dots,s_{i1},s_i,s_{ik},\dots,s_{n-1},s_n ss1,s2,si−1,sik−1,sik−2,…,si1,si,sik,…,sn−1,sn 当 k k k 为偶数的时候第二种操作就可以交换距离为奇数的字符那么结合第一 种操作我们就可以交换偶数与偶数奇数与奇数偶数与奇数奇数与偶数的 字符了那么我们直接 $sort\left ( \right ) $ 排序即可。 当 k k k 为奇数的时候只能交换距离为偶数的字符也就是说只能交换奇数与奇 数偶数与偶数位置的字符了所以我们分别针对 n n n 的奇偶性分别排序输出即可
#includebits/stdc.h
using namespace std;
const int N1e510;
int t;
char s[N]; //存储原始字符
char j[N],o[N]; //分别存储奇数与偶数位的字符
int main()
{cint;while(t--){int n0,k0;int l0,u0; //分别记录偶数与奇数的数量cinnks;if(k%20){sort(s,sn);coutsendl;}else {if(n%20){for(int i0;in;i){if((i1)%20)o[l]s[i];else j[u]s[i];}sort(o,ol);sort(j,ju);for(int i0;il;i) coutj[i]o[i];coutendl;}else {for(int i0;in;i){if((i1)%20)o[l]s[i];else j[u]s[i];//奇数}sort(o,ol);sort(j,ju);for(int i0;il;i) coutj[i]o[i];coutj[u-1];coutendl;}}}return 0;
}
