CF1864B Swap and Reverse 题解

Links

洛谷

Codeforces

Description

给定正整数 \(n,k\) 和一个长度为 \(n\) 的字符串 \(s\)，找到能通过任意次数的以下操作得到的具有最小字典序的字符串。

选择一个 \(i \in [1,n - 2]\)，交换 \(s_{i}\) 和 \(s_{i + 2}\)。
选择一个 \(i \in [1,n - k + 1]\)，将字符串的区间 \(s[i \dots i + k-1]\) 翻转。

多组测试数据， \(1\leq k < n \leq 10^{5}\)。

Solution

操作一：看到可以任意次数交换 \(s_{i}\) 和 \(s_{i + 2}\)，就可以想到神奇的排序算法，就相当于可以交换 奇偶性相同的两个字符。
操作二：翻转长度为 \(k\) 的区间
- 若 \(k\) 为奇数，可以通过操作一实现，没有任何意义。
- 若 \(k\) 为偶数，可以改变某字符出现位置奇偶性，结合操作一，可以任意交换字符串内字符。

因此我们只需分类讨论 \(k \bmod 2\) 的值进行排序即可。

Codes

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define max_n 510101
void read(int &p)
{
    p = 0;
    int k = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            k = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        p = p * 10 + c - '0';
        c = getchar();
    }
    p *= k;
    return;
}
void write_(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
    {
        write_(x / 10);
    }
    putchar(x % 10 + '0');
}
void writesp(int x)
{
    write_(x);
    putchar(' ');
}
void writeln(int x)
{
    write_(x);
    putchar('\n');
}
int T;
int n,k;
char s[max_n];
void solution()
{
    read(n),read(k);
    scanf("%s",s + 1);
    if(k & 1)
    {
        vector<char> mp[2];
        for(int i = 1;i <= n;i++)
        {
            mp[i & 1].push_back(s[i]);
        }
        sort(mp[1].begin(),mp[1].end());
        sort(mp[0].begin(),mp[0].end());
        int cnt[2];
        cnt[0] = cnt[1] = 0;
        for(int i = 1;i <= n;i++)
        {
            putchar(mp[i & 1][cnt[i & 1]++]);
        }
        puts("");
    }
    else
    {
        sort(s + 1,s + n + 1);
        for(int i = 1;i <= n;i++)
        {
            putchar(s[i]);
        }
        puts("");
    }
}
signed main()
{
    read(T);
    while(T--)
    {
        solution();
    }
    return 0;
}