专栏文章
题解:P13726 [GCPC 2024] Kitten of Chaos
P13726题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mio8gbcm
- 此快照首次捕获于
- 2025/12/02 15:04 3 个月前
- 此快照最后确认于
- 2025/12/02 15:04 3 个月前
题目描述
给你一个字符串和几次操作,让你求出最后的字符串。
思路
我们可以先分析一下题目中的 种操作:
- 水平翻转操作:相当于先反转字符串,再将一种字符转换为另一种字符。
- 垂直翻转操作:相当于直接将一种字符转换为另一种字符。
- 旋转 度操作:也相当于先反转字符串,再将一种字符转换为另一种字符。
这三种操作都不难实现。但是,如果我们直接一个接一个的执行操作的话,时间复杂度是 ,观察数据范围,很明显超时了。那该怎么办呢?
优化
我们不妨带入生活实际中:
假如一个杯子在空中水平翻转 次,其实相当于没变!
所以,如果有一个操作进行了偶数次,就不用进行了;如果有一个操作进行了奇数次,就只用进行一次了。现在,时间复杂度为 ,可以轻松通过本题啦!
代码
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 条评论,欢迎与作者交流。
正在加载评论...