BAPC2010-I Keylogger

链表模拟

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int N=1e6+10;
int arr[N],arrh;
struct Node{
    int L,R,v;
}a[N];
char str[N];
int Now,st,ed;
int n;
void work()
{
    scanf("%s",str);n=strlen(str);
    Now=0;//当前指针
    st=0;ed=1;
    a[0].L=-1;a[0].R=ed;
    a[1].L=st;a[1].R=-1;
    arrh=2;
    for (int i=0;i<n;i++){
        if (str[i]=='<'){
            if (Now==st)continue;
            Now=a[Now].L;
        }else if (str[i]=='>'){
            if (a[Now].R==ed)continue;
            Now=a[Now].R;
        }else if (str[i]=='-'){
            if (Now==st)continue;
            arrh--;arr[arrh]=Now;
            Now=a[Now].L;

            int tmp=a[a[Now].R].R;
            a[Now].R=tmp;
            a[tmp].L=Now;
        }else {
            int id=arr[arrh];arrh++;
            a[id].L=Now;a[id].R=a[Now].R;a[id].v=str[i];

            a[a[Now].R].L=id;
            a[Now].R=id;
            Now=id;
        }
    }
    st=a[st].R;
    while (st!=ed){
        if (st!=0 && st!=1){
            arrh--;arr[arrh]=st;
        }
        printf("%c",a[st].v);
        st=a[st].R;
    }
    puts("");
}
int main()
{
    //freopen("1.txt","r",stdin);
    for (int i=0;i<N;i++)arr[i]=i;
    arrh=0;
    int Case;scanf("%d",&Case);
    while (Case--)work();
    return 0;
}