AT_zone2021_d 宇宙人からのメッセージ 题解

PizzaYY · 2023-02-08 20:47:33 · 题解

前言

解决了 TLE 的问题。

分析

第一眼看到此题，双端队列的水题。

其实暴力的做法唯一缺陷是翻转字符串，我们就只需要优化一下就行了。

先来认识一下双端队列吧！

deque<int> q;//定义队列q，int可以替换成其他数据类型
q.push_front(x);//队首加入x
q.push_back(x);//队尾加入x
q.front();//查找队首元素
q.back();//查找队尾元素
q.pop_front();//删除队首元素
p.pop_back();//删除队尾元素
q.empty();//判断队列是否为空

接下来进入正题。

我们用 v 记录翻转的情况（翻转偶数次为 0，翻转奇数次为 1）。

加字母的情况：

完美的解决了 TLE。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
bool v; 
deque<char> q;
string s;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>s;
    for(int i = 0;i<s.size();i++)
    {
        if(s[i]=='R')
            v=!v;//取反 
        else if(v)
            if(!q.empty()&&q.front()==s[i])//删除元素
                q.pop_front();
            else q.push_front(s[i]);
        else
            if(!q.empty()&&q.back()==s[i])//删除元素 
                q.pop_back();
            else q.push_back(s[i]);
    }
    if(v)
        while(!q.empty())//输出
        {
            cout<<q.back();
            q.pop_back();
        }
    else
        while(!q.empty()) 
        {
            cout<<q.front();
            q.pop_front();
        }
    return 0;
}