题解：P13726 [GCPC 2024] Kitten of Chaos

· · 题解

题目链接：P13726 [GCPC 2024] Kitten of Chaos

题目描述

给你一个字符串和几次操作，让你求出最后的字符串。

思路

我们可以先分析一下题目中的 3 种操作：

  1. 水平翻转操作：相当于先反转字符串，再将一种字符转换为另一种字符。
  2. 垂直翻转操作：相当于直接将一种字符转换为另一种字符。
  3. 旋转 180 度操作：也相当于先反转字符串，再将一种字符转换为另一种字符。

这三种操作都不难实现。但是，如果我们直接一个接一个的执行操作的话，时间复杂度是 O(\lvert s \rvert \times \lvert t \rvert\ )，观察数据范围，很明显超时了。那该怎么办呢？

优化

我们不妨带入生活实际中：

假如一个杯子在空中水平翻转 2 次，其实相当于没变！

所以，如果有一个操作进行了偶数次，就不用进行了；如果有一个操作进行了奇数次，就只用进行一次了。现在，时间复杂度为 O(\lvert s \rvert + \lvert t \rvert\ )，可以轻松通过本题啦！

代码

#include <bits/stdc++.h>
using namespace std;
string s,t,l;
int h,v,r;//分别表示三种操作进行的次数
int main(){
    cin>>s>>t;
    //遍历操作字符串
    for(int i=0;i<t.size();i++){
        //记录三种操作进行的次数
        if(t[i]=='h') h++;
        else if(t[i]=='v') v++;
        else r++;
    }
    //分别进行操作
    if(h%2==1){
        //先反转
        l="";
        for(int i=s.size()-1;i>=0;i--){
            l+=s[i];
        }
        s=l;
        //再转换
        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';
        }
    }
    if(v%2==1){
        //直接转换
        for(int i=0;i<s.size();i++){
            if(s[i]=='b') s[i]='p';
            else if(s[i]=='p') s[i]='b';
            else if(s[i]=='d') s[i]='q';
            else s[i]='d';
        }
    }
    if(r%2==1){
        //同上先反转
        l="";
        for(int i=s.size()-1;i>=0;i--){
            l+=s[i];
        }
        //再转换
        s=l;
        for(int i=0;i<s.size();i++){
            if(s[i]=='b') s[i]='q';
            else if(s[i]=='q') s[i]='b';
            else if(s[i]=='p') s[i]='d';
            else s[i]='p';
        }
    }
    cout<<s;
    return 0;   
}