专栏文章

题解:P13726 [GCPC 2024] Kitten of Chaos

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

文章操作

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

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

题目描述

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

思路

我们可以先分析一下题目中的 33 种操作:
  1. 水平翻转操作:相当于先反转字符串,再将一种字符转换为另一种字符。
  2. 垂直翻转操作:相当于直接将一种字符转换为另一种字符。
  3. 旋转 180180 度操作:也相当于先反转字符串,再将一种字符转换为另一种字符。
这三种操作都不难实现。但是,如果我们直接一个接一个的执行操作的话,时间复杂度是 O(s×t )O(\lvert s \rvert \times \lvert t \rvert\ ),观察数据范围,很明显超时了。那该怎么办呢?

优化

我们不妨带入生活实际中:
假如一个杯子在空中水平翻转 22 次,其实相当于没变!
所以,如果有一个操作进行了偶数次,就不用进行了;如果有一个操作进行了奇数次,就只用进行一次了。现在,时间复杂度为 O(s+t )O(\lvert s \rvert + \lvert t \rvert\ ),可以轻松通过本题啦!

代码

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

评论

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

正在加载评论...