2008-2009 ACM-ICPC, NEERC, Southern Subregional ContestF

Problem F.

Text Editor Input file: stdin Output file: stdout Time limit: 1 second Memory limit: 64 megabytes

The simplest text editor “Open Word” allows to create and edit only one word. The editor processes keys ’a’ – ’z’, and also ’L’ (to the left) and ’R’ (to the right). After starting his work the editor immediately creates an empty word and sets its cursor to the left-most position. When one of keys ’a’ – ’z’ is pressed, the text editor inserts corresponding symbol just after the cursor. After that a cursor moves one position to the right in such a way that it is placed just after new symbol. When key ’L’ or ’R’ is pressed, the cursor moves one position to the left or to the right respectively. If the cursor can’t be moved because it is placed at the left-most or right-most position the command is ignored. Developers of “Open Word” didn’t think about the effectiveness so the editor is working slowly if a lot of keys have been pressed. Your task is to write a program that can process a sequence of key pressings emulating this editor and output result string. Input The input file contains one string which consists of symbols ’a’ – ’z’, ’L’ and ’R’. The string length is not less than 1 and doesn’t exceed 106 . Output Write a required string to the output file. Examples stdin stdout

abLcd

acdb

icpLLLLLacmRRRRRRRRRRRRc

acmicpc

题意：编辑文档，光标L往左移一位，R往右移一位，字母就在光标前一位输入。

题解：我室友给了我一种方法，挺巧妙，就是用两个栈，一个储存左边的，一个储存右边的。最后再把右边的存入左边就可以。

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define PI 3.14159265
using namespace std;
const int maxn=1e6+5;
const ll inf=0xfffffffffffffff;
char s[maxn],l[maxn],r[maxn];
int n1,n2;
int main()
{    
    //std::ios::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
    scanf("%s",s);
    int len=strlen(s);
    for(int i=0;i<len;i++)
    {
        if(s[i]=='L')
         {
             if(n1)r[n2++]=l[--n1];
         }
         else if(s[i]=='R')
         {
             if(n2)l[n1++]=r[--n2];
         }
         else
         {
             l[n1++]=s[i];
         }
    }
    while(n2)l[n1++]=r[--n2]; 
    printf("%s
",l);
    return 0;
}

还有一种方法就是用双向链表模拟找出前后关系；

#include<bits/stdc++.h>
#define eps 1e-9
#define PI 3.141592653589793
#define bs 1000000007
#define bsize 256
#define MEM(a) memset(a,0,sizeof(a))
typedef long long ll;
const int maxn=1e6+5;
using namespace std;
list<char>s;
string a;
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>a;
    list<char>::iterator it;
    it=s.begin();
    for(int i=0;i<a.size();i++)
    {
        if(a[i]=='L')
        {
            if(it!=s.begin())it--;
        }
        else if(a[i]=='R')
        {
            if(it!=s.end())it++;
        }
        else
        {
            s.insert(it,a[i]);
        }
    }
    it=s.begin();
    for(;it!=s.end();it++)cout<<*it;
    cout<<endl;
 }

题目链接：http://codeforces.com/gym/101504/attachments