专栏文章

P13726 [GCPC 2024] Kitten of Chaos 题解

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mio8woxd
此快照首次捕获于
2025/12/02 15:17
3 个月前
此快照最后确认于
2025/12/02 15:17
3 个月前
查看原文
一道简单的模拟题，但细节还是挺多的。

0x01 分析

首先我们需要知道这三条铁律：
  1. 翻转满足交换律。
  2. 翻转两次等于没翻转。
  3. 旋转 180∘180^{\circ} 等于水平翻转+垂直翻转。
根据第一条，我们并不需要按顺序执行 tt 中的每个操作，只需记录操作次数即可。
根据第二条，我们并不需要执行所有的操作，仅当操作次数为奇数时执行。
根据第三条，我们并不需要专门写旋转 180∘180^{\circ} 的代码，而可以将其转化为翻转。

0x02 实现

一些小细节（和血与泪的教训）：
  • 翻转字符串时使用头插（tmp = s[i] + tmp）的复杂度为 O(n2)O(n^2)。
  • 字符替换时绝对不要使用连续if。
Talk is cheap, show me the code!
CPP
#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;
}

评论

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

正在加载评论...