P13726 [GCPC 2024] Kitten of Chaos 题解

imnotcfz · 2025-08-19 16:09:49 · 题解

一道简单的模拟题，但细节还是挺多的。

0x01 分析

首先我们需要知道这三条铁律：

1. 翻转满足交换律。
2. 翻转两次等于没翻转。
3. 旋转 180^{\circ} 等于水平翻转+垂直翻转。

根据第一条，我们并不需要按顺序执行 t 中的每个操作，只需记录操作次数即可。

根据第二条，我们并不需要执行所有的操作，仅当操作次数为奇数时执行。

根据第三条，我们并不需要专门写旋转 180^{\circ} 的代码，而可以将其转化为翻转。

0x02 实现

一些小细节（和血与泪的教训）：

• 翻转字符串时使用头插（tmp = s[i] + tmp）的复杂度为 O(n^2)。
• 字符替换时绝对不要使用连续if。

Talk is cheap, show me the code!

#include <algorithm>
#include <iostream>
using namespace std;

string s, op;
bool h, v;  // 我们只关心操作次数的奇偶性

int main() {
  // 无需开 I/O 优化即可通过本题
  // 但开了可以砍掉一半的时间
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> s;
  cin >> op;
  for (auto i : op) {
    if (i == 'r') h ^= 1, v ^= 1;
    else if (i == 'h') h ^= 1;
    else if (i == 'v') v ^= 1;
  }
  if (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 if (s[i] == 'q') s[i] = 'p';
    }
    reverse(s.begin(), s.end());  // STL 大法好
  }
  if (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 if (s[i] == 'q') s[i] = 'd';
    }
  }
  cout << s;
  return 0;
}