AT_zone2021_d 宇宙人からのメッセージ 题解
题目
思路
首先考虑暴力模拟，那么时间复杂度为 o ( n 2 ) o(n^2) o(n2),TLE
那我们需要思考如何快速解决反转的问题。
我们会发现我们并不需要花费一个for循环去真的反转，只需要改变插入字符的前后位置。
例如：abcRcba
abc反转后变成cba，之后拼上cba，变成cbacba,其实我们可以把这个"cba"放到"abc"前面插上。变成了abcabc。最后反过来输出就好了。
那么我们用一个变量记录R的次数，如果次数为偶数那么数字就往后面插，奇数往前面插。
最后倒过来输出就是答案。
实现方法
STL大法。
使用双端队列deque,双端队列。
注意不要访问访问空的队列，会RE。
代码
#include<bits/stdc++.h>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<map>
#define ll long long
#define lhs printf("\n");
using namespace std;
const int N=1e5+10;
const int M=2024;
const int inf=0x3f3f3f3f;
string s;
deque<char> t;
int flag;
int main()
{cin>>s; for(int i=0;i<s.size();i++){if(s[i]!='R'){if(!flag){if(!t.empty() and t.front()!=s[i]){t.push_front(s[i]);}else if(t.empty()){t.push_front(s[i]);}else{if(!t.empty())t.pop_front();}}else{if(!t.empty() and t.back()!=s[i]){t.push_back(s[i]);}else if(t.empty()){t.push_back(s[i]);}else{if(!t.empty())t.pop_back();}}}else{flag^=1;}}if(flag){ while(!t.empty()){cout<<t.front();t.pop_front();}}else{while(!t.empty()){cout<<t.back();t.pop_back();}}return 0;
}
//abcRRRRabcRabcabc