题解：P13726 [GCPC 2024] Kitten of Chaos

Doraeman · 2025-08-19 13:35:46 · 题解

简化题意

给定一个字符串 s，输出对它进行若干次水平翻转、垂直翻转、180\degree 旋转后的结果。

旋转

现在，我们需要分别写 3 种旋转方式的代码。

水平翻转

观察自测样例：bbp \rightarrow pdd。
可以发现：水平翻转就是整个字符串从右往左看，每个字母也都要从右往左看。

字母从右往左看

分类讨论 4 种字母：

• b \rightarrow d；
• d \rightarrow b；
• p \rightarrow q；
• q \rightarrow p。

循环对每个字母都进行更改即可。

for(int i=0; i<s.size(); i++)
    if(s[i] == 'b') s[i] = 'd';
    else if(s[i] == 'd') s[i] = 'b';
    else if(s[i] == 'p') s[i] = 'q';
    else s[i] = 'p';

字符串从右往左看

设 s 下标从 0 开始。
那么，对于所有的整数 i 满足 0\le i<\lfloor\frac{|s|}{2}\rfloor，只要交换 s_i 与 s_{|s|-i-1} 的值，就可以实现。

for(int i=0; i<s.size()/2; i++)
    swap(s[i], s[s.size()-i-1]);

垂直翻转

垂直翻转更加简单：所有字母从下往上看。

仍然分类讨论：

• b \rightarrow p；
• d \rightarrow q；
• p \rightarrow b；
• q \rightarrow d。

for(int i=0; i<s.size(); i++)
    if(s[i] == 'b') s[i] = 'p';
    else if(s[i] == 'd') s[i] = 'q';
    else if(s[i] == 'p') s[i] = 'b';
    else s[i] = 'd';

旋转 180\degree

观察可以发现规律：旋转 180\degree 的操作就是水平翻转 + 垂直翻转。
直接调用那两个函数就可以了。

细节

最后还有一件非常重要的事情：每个实现函数的时间复杂度都是 \operatorname{O}{(N)}。（N 是字符串长度）。
也就是说，如果我们遍历字符串 t 并根据每个字符进行旋转操作，时间复杂度最高可达 \operatorname{O}{(N^2)}。快乐地超时了。

再次观察规律：这 3 种操作中无论什么操作，翻转 2 次与不翻转效果相同。
所以可以记录每种操作出现的次数，最后再对 2 取模。
也可以使用 bool 值记录，在循环中每次遇到对应字符就取反。

AC 代码

#include<bits/stdc++.h>
using namespace std;

string s, opt;
int h, v, r;

void H(){
    for(int i=0; i<s.size(); i++)
        if(s[i] == 'b') s[i] = 'd';
        else if(s[i] == 'd') s[i] = 'b';
        else if(s[i] == 'p') s[i] = 'q';
        else s[i] = 'p';
    for(int i=0; i<s.size()/2; i++)
        swap(s[i], s[s.size()-i-1]);
}
void V(){
    for(int i=0; i<s.size(); i++)
        if(s[i] == 'b') s[i] = 'p';
        else if(s[i] == 'd') s[i] = 'q';
        else if(s[i] == 'p') s[i] = 'b';
        else s[i] = 'd';
}
void R(){
    H(); V();
}

int main(){
    cin >> s >> opt;
    for(int i=0; i<opt.size(); i++)
        h ^= (opt[i] == 'h'),
        v ^= (opt[i] == 'v'),
        r ^= (opt[i] == 'r');

    if(h) H();
    if(v) V();
    if(r) R();

    cout << s;
}