首页 > ACM题库 > HDU-杭电 > HDU 4286-Data Handler-模拟-[解题报告]HOJ
2015
05-23

HDU 4286-Data Handler-模拟-[解题报告]HOJ

Data Handler

问题描述 :

  You are in charge of data in a company, so you are called "Data Handler". Different from the data in computer, the data you have are really in huge volume, and each data contains only one integer. All the data are placed in a line from left to right. There are two "hand" to handle the data, call hand "L" and hand "R". Every hand is between two adjacent data or at the end of the data line.
  In one day, the company gives you many commands to handle these data, so you should finish them one by one. At the beginning, there are N data, and hand "L" and "R" are in some positions. Each command is one the following formats:
  (1)MoveLeft L/R: it means that you should move the hand "L"/"R" left one data unit;
circuits

  (2)MoveRight L/R: it means that you should move the hand "L"/"R" right one data unit;

circuits

  (3)Insert L X: it means that you should insert the data that contains X at the right of the hand "L";

circuits

  (4)Insert R X: it means that you should insert the data that contains X at the left of the hand "R";

circuits

  (5)Delete L: it means that you should delete the one data at the right of the hand "L";

circuits

  (6)Delete R: it means that you should delete the one data at the left of the hand "R";

circuits

  (7)Reverse: it means that you should reverse all the data between hand "L" and hand "R".

circuits

  After finish all the commands, you should record all the data from left to right. So please do it.

输入:

  The first line contains an integer T(1<=T<=10), the number of test cases.
  Then T test cases follow. For each test case, the first line contains an integer N(1<=N<=500000), the number of data at the beginning. The second line contains N integers, means the integer in each data, from left to right. The third line contains two integers L and R (1<=L<=R<=N), the positions of hand "L" and hand "R". It means that hand "L" is at the left of the L-th data and hand "R" is at the right of the R-th data. The fourth line contains one integer M(1<=M<=500000), the number of commands. Then M lines follow, each line contains a command in the above format. All the integers in the data will in range [-10000,10000].
  It is guaranteed that there are always some data between hand "L" and "R", and if the hand is at the left/right end of the data line, it will not receive the command MoveLeft/MoveRight.
  Because of large input, please use scanf instead of cin.

输出:

  The first line contains an integer T(1<=T<=10), the number of test cases.
  Then T test cases follow. For each test case, the first line contains an integer N(1<=N<=500000), the number of data at the beginning. The second line contains N integers, means the integer in each data, from left to right. The third line contains two integers L and R (1<=L<=R<=N), the positions of hand "L" and hand "R". It means that hand "L" is at the left of the L-th data and hand "R" is at the right of the R-th data. The fourth line contains one integer M(1<=M<=500000), the number of commands. Then M lines follow, each line contains a command in the above format. All the integers in the data will in range [-10000,10000].
  It is guaranteed that there are always some data between hand "L" and "R", and if the hand is at the left/right end of the data line, it will not receive the command MoveLeft/MoveRight.
  Because of large input, please use scanf instead of cin.

样例输入:

2
5
1 2 3 4 5
1 5
5
MoveLeft R
Insert R 6
Reverse
Delete R
Insert L 7
5
6536 5207 2609 6604 -4046
1 3
5
Delete L
Insert R -9221
Reverse
Delete L
MoveRight L

样例输出:

7 6 4 3 2 5
2609 5207 6604 -4046

Data Handler

题目:http://acm.hdu.edu.cn/showproblem.php?pid=4286

题意:给你一个数字串和一些操作指令,问你执行完操作后的数字串是什么。

题解:双向链表模拟。就是要判断第i个结点的前后结点分别是什么比较困难,这个问题可以通过给左指针前1位加个指针,右指针后1位加个指针解决。

ps:打代码一定要细心,特别是这种模拟题。T^T

代码:

#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
    int value;
    int pre,next;
} num[1000005];
int l,ll,r,rr,cnt;
void MoveLefe()
{
    char ch[5];
    scanf("%s",ch);
    if(ch[0]=='L')
    {
        if(num[ll].pre==l)
        {
            l=ll;
            ll=num[ll].next;
        }
        else
        {
            l=ll;
            ll=num[ll].pre;
        }
    }
    else
    {
        if(num[r].pre==rr)
        {
            rr=r;
            r=num[r].next;
        }
        else
        {
            rr=r;
            r=num[r].pre;
        }
    }
}
void MoveRight()
{
    char ch[5];
    scanf("%s",ch);
    if(ch[0]=='L')
    {
        if(num[l].pre==ll)
        {
            ll=l;
            l=num[l].next;
        }
        else
        {
            ll=l;
            l=num[l].pre;
        }
    }
    else
    {
        if(num[rr].pre==r)
        {
            r=rr;
            rr=num[rr].next;
        }
        else
        {
            r=rr;
            rr=num[rr].pre;
        }
    }
}
void Insert()
{
    char ch[5];
    int value;
    scanf("%s%d",ch,&value);
    if(ch[0]=='L')
    {
        num[cnt].pre=ll;
        num[cnt].next=l;
        if(num[ll].pre==l) num[ll].pre=cnt;
        else               num[ll].next=cnt;
        if(num[l].pre==ll) num[l].pre=cnt;
        else               num[l].next=cnt;
        l=cnt++;
        num[l].value=value;
    }
    else
    {
        num[cnt].pre=rr;
        num[cnt].next=r;
        if(num[rr].pre==r) num[rr].pre=cnt;
        else               num[rr].next=cnt;
        if(num[r].pre==rr) num[r].pre=cnt;
        else               num[r].next=cnt;
        r=cnt++;
        num[r].value=value;
    }
}
void Delete()
{
    char ch[5];
    int next;
    scanf("%s",ch);
    if(ch[0]=='L')
    {
        if(num[l].pre==ll) next=num[l].next;
        else               next=num[l].pre;
        if(num[ll].pre==l)  num[ll].pre=next;
        else               num[ll].next=next;
        if(num[next].pre==l) num[next].pre=ll;
        else                 num[next].next=ll;
        l=next;
    }
    else
    {
        if(num[r].pre==rr) next=num[r].next;
        else               next=num[r].pre;
        if(num[rr].pre==r)  num[rr].pre=next;
        else               num[rr].next=next;
        if(num[next].pre==r) num[next].pre=rr;
        else                 num[next].next=rr;
        r=next;
    }
}
void Reverse()
{
    if(num[r].pre==rr) num[r].pre=ll;
    else               num[r].next=ll;
    if(num[l].pre==ll) num[l].pre=rr;
    else               num[l].next=rr;
    if(num[ll].pre==l) num[ll].pre=r;
    else               num[ll].next=r;
    if(num[rr].pre==r) num[rr].pre=l;
    else               num[rr].next=l;
    l=l^r;
    r=l^r;
    l=l^r;
}
void out(int n)
{
    bool first=true;
    int pre=0;
    for(int i=num[0].next;i!=n+1;)
    {
        if(first)
        {
            printf("%d",num[i].value);
            first=false;
        }
        else printf(" %d",num[i].value);
        if(num[i].next!=pre)
        {
            pre=i;
            i=num[i].next;
        }
        else
        {
            pre=i;
            i=num[i].pre;
        }
    }
    printf("\n");
}
int main()
{
    int cas,n,m;
    char s[20];
    scanf("%d",&cas);
    for(; cas--;)
    {
        scanf("%d",&n);
        cnt=n+2;
        for(int i=1; i<=n; ++i)
        {
            scanf("%d",&num[i].value);
            num[i].pre=i-1;
            num[i].next=i+1;
        }
        scanf("%d%d",&l,&r);
        num[0].pre=0;
        num[0].next=1;
        num[n+1].pre=n;
        ll=num[l].pre;
        rr=num[r].next;
        scanf("%d",&m);
        for(; m--;)
        {
            scanf("%s",s);
            if(strcmp(s,"MoveLeft")==0)
                MoveLefe();
            else if(strcmp(s,"MoveRight")==0)
                MoveRight();
            else if(strcmp(s,"Insert")==0)
                Insert();
            else if(strcmp(s,"Delete")==0)
                Delete();
            else if(strcmp(s,"Reverse")==0)
                Reverse();
        }
        out(n);
    }
    return 0;
}

来源:http://blog.csdn.net/acm_ted/article/details/7961812

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_ted/article/details/7961812