题解 P2201 【数列编辑器】

这道题我写的是链表;

至少这样写还好想;

但是有一点需要注意:每次操作完都要去更新当前点;

所以插入就是断开点前点与前一个点的连接,加入新点;

删除就是把当前点的前后两个点连接;

左移右移显然直接移动;

查询最好是用数组记录,这样不会TLE;

所以就直接写个链表模拟就好了;

我是每次都更新,这样不会错,而且保险;

#include "iostream"
#include "stdio.h"
#include "algorithm"
#define II int
#define R register
#define U NULL
#define I 1000010
using namespace std;

struct node {
    II o,sum,wei;
    node *up,*next;
};
node * begin(R II x)
{
    node * ret=new node;
    ret->up=U;
    ret->next=U;
    ret->o=x;
    ret->sum=0;
    return ret;
}
node *root=begin(0),*now,*en;

II ans[I];

void ppp(node *pi) 
{
    pi->wei=pi->up->wei+1;
    pi->sum=pi->up->sum+pi->o;
    ans[pi->wei]=max(ans[pi->wei-1],pi->sum);
}

void add()
{
    R II x;
    scanf("%d",&x);
    R node *pi=begin(x);
    R node *qian=now->up;
    now->up=pi;
    pi->next=now;
    pi->up=qian;
    qian->next=pi;
    ppp(pi);
    ppp(now);
}

void del()
{
    R node *de=now->up;
    R node *qian=de->up;
    qian->next=now;
    now->up=qian;
    ppp(now);
}

void just() 
{ 
    now=now->up;
    ppp(now);
}

void back() 
{ 
    now=now->next;
    ppp(now);
}

void query()
{
    R II k;
    scanf("%d",&k);
    printf("%d\n",ans[k]);
}

int main()
{
//    freopen("1.in","r",stdin);

    R II n; R char a;
    scanf("%d",&n);
    now=begin(0);
    now->up=root; now->next=root;
    root->up=now;
    root->next=now;
    ans[0]=-1e9;

    while (n--) {
        cin>>a;
        if(a=='I') add();
        if(a=='D') del();
        if(a=='L') just();
        if(a=='R') back();
        if(a=='Q') query();
    }
    exit(0);
}

发表于 2017-11-05 18:46:17 in 题解