加密字符串

题解思路

本题的核心在于模拟字符串的编辑过程，涉及字符串的操作、撤销机制和翻转操作。我们可以使用**双端队列（deque）**来高效地完成这些操作。

1. 使用双端队列（deque）存储字符串$t$：

   • R 代表反转字符串，可以使用一个标志位 reversed_flag 来追踪当前字符串是否处于反转状态。
   • Z 代表撤销上一步操作，我们需要记录上一步操作类型，并在遇到 Z 时进行相应撤销。
   • 其他普通字符直接加入 deque，如果当前处于反转状态，则从头部插入，否则从尾部插入。

2. 处理 R 操作：

   • 只需要翻转 reversed_flag，表示当前字符串应当被反转。

3. 处理 Z 操作：

   • 如果上一步是 R，则取消 R，恢复 reversed_flag 状态。
   • 如果上一步是普通字符，则需要删除该字符，考虑 reversed_flag 以决定从 deque 头部还是尾部删除。

4. 最终结果输出：

   • 如果 reversed_flag 为 True，则需要反转 deque 后再输出。

算法复杂度分析

• 遍历字符串 需要 O(n) 的时间复杂度。
• 插入和删除操作 由于使用 双端队列 deque，平均复杂度为 O(1)。
• 最终的反转操作 最坏情况 O(n)，但整体仍然是 O(n)。

因此，总的时间复杂度为 O(n)，在给定约束下是可行的。

代码实现

Python 代码

import sys
from collections import deque

def decrypt_string(s):
    t = deque()
    reversed_flag = False
    last_action = None  # 记录上一步操作
    last_char = None  # 记录上一次加入的字符

    for char in s:
        if char == 'R':
            reversed_flag = not reversed_flag
            last_action = 'R'
        elif char == 'Z':
            if last_action == 'R':
                reversed_flag = not reversed_flag  # 取消上次反转
            elif last_action == 'char' and t:
                if reversed_flag:
                    t.popleft()
                else:
                    t.pop()
            last_action = None  # 撤销后清除操作记录
        else:
            if reversed_flag:
                t.appendleft(char)
            else:
                t.append(char)
            last_action = 'char'
            last_char = char

    # 如果最终是翻转状态，需要反转
    if reversed_flag:
        t.reverse()
    
    return ''.join(t)

# 读取输入
input_data = sys.stdin.read().split()
T = int(input_data[0])
results = []
for i in range(1, T + 1):
    results.append(decrypt_string(input_data[i]))

# 输出结果
sys.stdout.write("\n".join(results) + "\n")

Java 代码

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int T = Integer.parseInt(br.readLine()); // 读取测试用例数
        StringBuilder result = new StringBuilder();
        
        while (T-- > 0) {
            String s = br.readLine();
            result.append(decryptString(s)).append("\n");
        }
        
        bw.write(result.toString());
        bw.flush();
        br.close();
        bw.close();
    }

    public static String decryptString(String s) {
        Deque<Character> t = new LinkedList<>();
        boolean reversedFlag = false;
        String lastAction = null;
        Character lastChar = null;
        
        for (char c : s.toCharArray()) {
            if (c == 'R') {
                reversedFlag = !reversedFlag;
                lastAction = "R";
            } else if (c == 'Z') {
                if ("R".equals(lastAction)) {
                    reversedFlag = !reversedFlag;
                } else if ("char".equals(lastAction) && !t.isEmpty()) {
                    if (reversedFlag) {
                        t.pollFirst();
                    } else {
                        t.pollLast();
                    }
                }
                lastAction = null;
            } else {
                if (reversedFlag) {
                    t.addFirst(c);
                } else {
                    t.addLast(c);
                }
                lastAction = "char";
                lastChar = c;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        while (!t.isEmpty()) {
            sb.append(reversedFlag ? t.pollLast() : t.pollFirst());
        }
        
        return sb.toString();
    }
}

C++ 代码

#include <iostream>
#include <deque>
#include <string>

using namespace std;

void decryptString(const string& s) {
    deque<char> t;
    bool reversedFlag = false;
    string lastAction;
    char lastChar;
    
    for (char c : s) {
        if (c == 'R') {
            reversedFlag = !reversedFlag;
            lastAction = "R";
        } else if (c == 'Z') {
            if (lastAction == "R") {
                reversedFlag = !reversedFlag;
            } else if (lastAction == "char" && !t.empty()) {
                if (reversedFlag) {
                    t.pop_front();
                } else {
                    t.pop_back();
                }
            }
            lastAction = "";
        } else {
            if (reversedFlag) {
                t.push_front(c);
            } else {
                t.push_back(c);
            }
            lastAction = "char";
            lastChar = c;
        }
    }
    
    if (reversedFlag) {
        while (!t.empty()) {
            cout << t.back();
            t.pop_back();
        }
    } else {
        while (!t.empty()) {
            cout << t.front();
            t.pop_front();
        }
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        decryptString(s);
    }
    
    return 0;
}

题目内容

小美有一个由大小写字母混合构成的加密字符串s，你需要按照以下准则将其解密得到字符串$t$。初始时字符串t为空，对于字符串$s$的每一个字符$s_i$:

• 如果$s$的第$i$个字符为‘$R$’(保证至多出现一次)，则反转字符串$t$;
• 如果$s$的第$i$个字符为‘$Z$’(保证至多出现一次)，则撤销上一步操作，具体地:

如果上一步为‘$R$’，则取消反转;

如果上一步为其他字符，删除这个字符；

上一步为空，则跳过这一操作；

• 其他情况，直接将这个字符添加到字符串$t$的结尾;

请你直接输出解密完成后的字符串$t$。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≦T≦2×10^5)$代表数据组数，

每组测试数据描述如下:

第一行输入一个长度为$1 ≦len(s)$$≤2×10^5$的字符串$s$代表加密字符串。

除此之外，保证单个测试文件的字符数量之和不超过$10^6$。

输出描述

对于每一组测试数据，新起一行输出解密完成后的字符串$t$。数据保证字符串长度不为$0$。

样例1

输入

2
meRDZ
DameDame

输出

em
DameDame

说明

对于第一组测试数据，解密过程依次为:

• 第一步，将‘$m$’加入，$t$= "$m$";
• 第二步，将‘$e$’加入，$t$="$me$";
• 第三步，翻转字符串，$t$= "$em$";
• 第四步，将‘$D$’加入，$t$="$emD$"
• 第五步，删除第五步加入的字母$t$=“$em$”