题解：P13726 [GCPC 2024] Kitten of Chaos
Chronomia_phi
·
·
题解
题意简述
给定两个字符串 s1 与 s2 。
要求输出操作后的字符串。
对于 $s2$ 中的每个字符：
若为 h，则水平翻转 $s1$。（例：bbq->pdd）
若为 v，则垂直翻转 $s1$。（例：bbq->ppd）
若为 r，则将 $s1$ 旋转 180 度。（例：bbq->bqq）
# 题目分析
## 1.操作实现【模拟】
对于题目中所提到的操作，直接通过代码模拟实现即可。
- ### 水平翻转
水平翻转中，对于每个字母而言，b 与 d 互相转换，p 与 q 互相转换。
与此同时，需要注意，字符串整体也需要进行水平翻转。也就是第零位与最后一位互换，第一位与倒数第二位互换，第二位与倒数第三位互换……
设 $s1$ 的长度为 $l1$。我们不难发现，字符串中需要互换的两位字符的下标相加等于 $l1-1$。
由此思路代码模拟操作即可。
**-代码实现-**
```cpp
void shuiping(){
for(int i=0;i<l1;i++){//水平翻转每个字符
if(s1[i]=='b') s1[i]='d';
else if(s1[i]=='d') s1[i]='b';
else if(s1[i]=='p') s1[i]='q';
else if(s1[i]=='q') s1[i]='p';
}
for(int i=0;i<l1/2;i++)//整体水平翻转，前后字符互换
swap(s1[i],s1[l1-i-1]);
}
- ### 垂直翻转
只需要把每个字母垂直翻转即可。b 与 p 互相转换，d 与 q 互相转换。
**-代码实现-**
```cpp
void chuizhi(){
for(int i=0;i<l1;i++){//垂直翻转每个字符
if(s1[i]=='b') s1[i]='p';
else if(s1[i]=='p') s1[i]='b';
else if(s1[i]=='d') s1[i]='q';
else if(s1[i]=='q') s1[i]='d';
}
}
- ### 旋转 180 度
根据题意，结合轴对称与旋转，不难发现：字符串旋转 180 度，相当于先水平翻转，再垂直翻转。
因而只需要把水平翻转与垂直翻转的操作结合，即可完成旋转操作。
**-代码实现-**
参考上文。
## 2.TLE 写法（什
代码实现操作后，我们很容易想到，只需要依次枚举 $s2$ 中每一个字符，并且执行对应的操作即可。
于是我们就得到了这样一篇代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int l1,l2;
void shuiping(){
for(int i=0;i<l1;i++){
if(s1[i]=='b') s1[i]='d';
else if(s1[i]=='d') s1[i]='b';
else if(s1[i]=='p') s1[i]='q';
else if(s1[i]=='q') s1[i]='p';
}
for(int i=0;i<l1/2;i++)
swap(s1[i],s1[l1-i-1]);
}
void chuizhi(){
for(int i=0;i<l1;i++){
if(s1[i]=='b') s1[i]='p';
else if(s1[i]=='p') s1[i]='b';
else if(s1[i]=='d') s1[i]='q';
else if(s1[i]=='q') s1[i]='d';
}
}
int main(){
cin>>s1>>s2;
l1=s1.size();l2=s2.size(); //记录s1、s2长度
for(int i=0;i<l2;i++){ //枚举s2中操作
if(s2[i]=='h') //若为h，水平翻转
shuiping();
else if(s2[i]=='v') //若为v，垂直翻转
chuizhi();
else { //否则（若为r），旋转
shuiping();
chuizhi(); //二者组合，完成旋转操作
}
}
cout<<s1;
return 0;
}
```
看起来似乎很有道理。
于是，本蒟蒻信心满满提交，然后 tle……
因此需要进行优化。
## 3.过程优化
由题中翻转与旋转操作的特性，可以得出：
1. 任何操作重复执行两次之后，都相当于没有执行该操作。
2. 执行一次旋转操作，相当于对字符串执行一次水平翻转与一次垂直翻转操作。
由此，我们可以先遍历 $s2$ 中每个字符，并且统计三项操作所对应的执行次数。
随后，分别将三项操作的执行次数对 $2$ 取模。这样对于每项操作而言，都排除掉了重复多余的操作，只保留实际有效的操作数。
然后，若留下的三项操作的次数均为一次，则三项操作刚好可以互相抵消。则不必保留任何操作。
最后，按照最终保留的操作执行即可。
**-代码实现-**
```cpp
for(int i=0;i<l2;i++){ //分别统计三项操作次数
if(s2[i]=='h') h++;
else if(s2[i]=='v') v++;
else if(s2[i]=='r') r++;
}
h%=2;v%=2;r%=2; //操作数对2取模，只保留有效操作
if(h&&v&&r)
h=v=r=0; //若三项操作均被保留下一次，则可互相抵消
for(int i=1;i<=h;i++) //按保留的操作执行
shuiping();
for(int i=1;i<=v;i++)
chuizhi();
for(int i=1;i<=r;i++){
shuiping();
chuizhi();
}
```
# 完整代码参考
```cpp
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int l1,l2;
int h=0,v=0,r=0;
void shuiping(){
for(int i=0;i<l1;i++){
if(s1[i]=='b') s1[i]='d';
else if(s1[i]=='d') s1[i]='b';
else if(s1[i]=='p') s1[i]='q';
else if(s1[i]=='q') s1[i]='p';
}
for(int i=0;i<l1/2;i++)
swap(s1[i],s1[l1-i-1]);
}
void chuizhi(){
for(int i=0;i<l1;i++){
if(s1[i]=='b')
s1[i]='p';
else if(s1[i]=='p')
s1[i]='b';
else if(s1[i]=='d')
s1[i]='q';
else if(s1[i]=='q')
s1[i]='d';
}
}
int main(){
cin>>s1>>s2;
l1=s1.size();l2=s2.size();
for(int i=0;i<l2;i++){
if(s2[i]=='h') h++;
else if(s2[i]=='v') v++;
else if(s2[i]=='r') r++;
}
h%=2;v%=2;r%=2;
if(h&&v&&r)
h=v=r=0;
for(int i=1;i<=h;i++)
shuiping();
for(int i=1;i<=v;i++)
chuizhi();
for(int i=1;i<=r;i++){
shuiping();
chuizhi();
}
cout<<s1;
return 0;
}
```