HDU 4286 Data Handler（12天津网络赛-模拟）

题目链接：Click here~~

题意：

给一列数字，一个左指针 L 和一个右指针 R。

然后有7种操作。

最后输出操作完的结果。

比赛时敲了2个小时才敲出来。。。各种弱。

解题思路：

观察这7种操作，我们发现，除了翻转，另外6种操作都是对于 L 或 R 这两点进行的。

这不就是双向队列么。

于是想到用三个队列来储存所有的数据：L 左边的，L 到 R 的，R 右边的。

对于翻转操作，用一个变量记录下当前的队列是正向还是逆向。

然后每次操作的时候，如果当前的队列是逆向的，则 L 相当于 R，R 相当于 L。

然后就没有然后了，模拟吧。

贴上我简化后的代码。

#include <deque>#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;bool rev,first;deque<int> A,B,C;deque<int>::iterator it;int pop_Front(deque<int>& d){   int tmp = d.front();   d.pop_front();   return tmp;}int pop_Back(deque<int>& d){   int tmp = d.back();   d.pop_back();   return tmp;}void Print(){    if(first)    {        first = false;        printf("%d",*it);    }    else        printf(" %d",*it);}void Out(){    first = true;    for(it=A.begin();it!=A.end();it++)        Print();    if(!rev)        for(it=B.begin();it!=B.end();it++)            Print();    else        for(it=B.end()-1;it!=B.begin()-1;it--)            Print();    for(it=C.begin();it!=C.end();it++)        Print();    puts("");}int main(){    int L,R,Q,z,n,x;    scanf("%d",&z);    while(z--)    {        A.clear();        B.clear();        C.clear();        rev = false;        scanf("%d",&n);        for(int i=1;i<=n;i++)        {            scanf("%d",&x);            B.push_back(x);        }        scanf("%d%d",&L,&R);        for(int i=1;i<L;i++)            A.push_back(pop_Front(B));        for(int i=R+1;i<=n;i++)            C.push_front(pop_Back(B));        scanf("%d",&Q);        char cmd[12],loc[5];        while(Q--)        {            scanf("%s",cmd);            if(cmd[0] == 'R')            {                rev = !rev;                continue;            }            scanf("%s",loc);            if(cmd[0] == 'M')            {                if(cmd[4] == 'L')   //向左                {                    if(loc[0] == 'L')                    {                        x = pop_Back(A);                        !rev ? B.push_front(x) : B.push_back(x);                    }                    else                    {                        x = (!rev) ? pop_Back(B) : pop_Front(B);                        C.push_front(x);                    }                }                else            //向右                {                    if(loc[0] == 'L')                    {                        x = (!rev) ? pop_Front(B) : pop_Back(B);                        A.push_back(x);                    }                    else                    {                        x = pop_Front(C);                        !rev ? B.push_back(x) : B.push_front(x);                    }                }            }            else if(cmd[0] == 'I')            {                scanf("%d",&x);                if(!rev)                    loc[0] == 'L' ? B.push_front(x) : B.push_back(x);                else                    loc[0] == 'R' ? B.push_front(x) : B.push_back(x);            }            else if(cmd[0] == 'D')            {                if(!rev)                    loc[0] == 'L' ? B.pop_front() : B.pop_back();                else                    loc[0] == 'R' ? B.pop_front() : B.pop_back();            }        }        Out();    }    return 0;}