专栏文章

题解：P13726 [GCPC 2024] Kitten of Chaos

DDoraeman
P13726题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio8zjfg
此快照首次捕获于
2025/12/02 15:19
3 个月前
此快照最后确认于
2025/12/02 15:19
3 个月前
查看原文

简化题意

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

旋转

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

水平翻转

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

字母从右往左看

分类讨论 44 种字母：
  • b →\rightarrow d；
  • d →\rightarrow b；
  • p →\rightarrow q；
  • q →\rightarrow p。
循环对每个字母都进行更改即可。
CPP
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';

字符串从右往左看

设 ss 下标从 00 开始。
那么，对于所有的整数 ii 满足 0≤i<⌊∣s∣2⌋0\le i<\lfloor\frac{|s|}{2}\rfloor，只要交换 sis_i 与 s∣s∣−i−1s_{|s|-i-1} 的值，就可以实现。
CPP
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。
CPP
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°180\degree

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

细节

最后还有一件非常重要的事情：每个实现函数的时间复杂度都是 O⁡(N)\operatorname{O}{(N)}。（NN 是字符串长度）。
也就是说，如果我们遍历字符串 tt 并根据每个字符进行旋转操作，时间复杂度最高可达 O⁡(N2)\operatorname{O}{(N^2)}。快乐地超时了。
再次观察规律：这 33 种操作中无论什么操作，翻转 22 次与不翻转效果相同。
所以可以记录每种操作出现的次数，最后再对 22 取模。
也可以使用 bool 值记录，在循环中每次遇到对应字符就取反。

AC 代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...