P10058 题解

FurippuWRY · 2024-01-14 18:44:27 · 题解

可以将 S 抽象成一个环，可以发现：无论怎么左移右移反转，最终的字符串都可以从环上按照一定顺序读出。那么可以先对三种操作进行统计，把修改字符串放到最后，而非直接暴力。

定义变量 cnt=0,p=0，如果右移 x 位，cnt\leftarrow cnt + x，如果左移 x 位，cnt\leftarrow cnt - x，如果反转 cnt\leftarrow -cnt,p\leftarrow p+1。

若最终的 p 为奇数，则翻转，然后判定 cnt 的正负，若为正，向右移动 (cnt \bmod |S|) 位（你要是不取模就 T 飞了），若为负，向左移动 (-cnt\bmod |S|) 位。

至于为什么 cnt 要取模，假设 |S| = 114,cnt=228，这时移动 228 位，很明显，字符串没变，如果 |S| = 114,cnt=229，这时字符串只移动了 1 位，即 229\bmod 114=1，也就是说，字符串的移动位数只和 |cnt|\bmod |S| 有关。

可以用双端队列模拟，感觉会比纯数组方便的多。

#include<bits/stdc++.h>
#define int long long

using namespace std;

deque<char> n;
int t, x, len, cnt = 0, p = 0;
string opt, s;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> s;
    len = s.size();
    for (int i = 0; i < len; ++i) n.push_back(s[i]);
    cin >> t;
    while (t--) {
        cin >> opt;
        if (opt[0] == '<') {
            cin >> x;
            cnt -= x;
        }
        else if (opt[0] == '>') {
            cin >> x;
            cnt += x;
        }
        else {
            p++;
            cnt = -cnt;
        }
    }
    if (p & 1) reverse(n.begin(), n.end());
    if (cnt > 0) {
        for (int i = 1; i <= cnt % len; ++i) {
            n.push_front(n.back());
            n.pop_back();
        }
    }
    else if (cnt < 0) {
        for (int i = 1; i <= -cnt % len; ++i) {
            n.push_back(n.front());
            n.pop_front();
        }
    }
    for (auto i : n) cout << i;
    return 0;
}