P10058 Reverse and Rotate 题解

不难想到可以用类似双向链表的思想解决。

之后不难想到，两次反转操作会抵消，故我们只需要记录第一个字符 \(s_1\) 在操作后的位置，并记录反转次数的奇偶性，最后即可还原出答案字符串。

namespace hellolin {
string s, t, op;
int n, m, x;
ll head;
bool rev;
void main() {
  util.read(s, m);
  head = 0;
  n = s.length();

  for (int i = 1; i <= m; ++i) {
    util.read(op);

    if (op == "rev")
      rev = !rev;
    else {
      util.read(x);
      if (op == ">") x = -x;
      if (rev) x = -x;
      head += x;
      ((head %= n) += n) %= n;
    }
  }

  for (int i = head; i < n; ++i)
    t += s[i];
  for (int i = 0; i < head; ++i)
    t += s[i];
  if (rev) reverse(t.begin(), t.end());

  util.writeln(t);
}
} // namespace hellolin

P10058 Reverse and Rotate 题解

评论