题解 P4940 【Portal2】

7KByte · 2019-03-17 13:49:43 · 题解

上一篇唯一的题解涉嫌抄袭被$Delete$了（考古那我来补一篇 ----------------- 先扯一句，题面说什么无效操作，事实上没有（弄的我多打了100行…… 从题面透露出的信息我们可以感受到这题是个大型模拟看到目前的提交大多数是栈和链表然而本蒟蒻并不会，所以就打了一个**双端队列（模拟栈）+启发式合并** 除了$MOVE$操作，其他操作还是比较简单吧……按照题意打就可以了对于$MOVE$操作我们进行启发式合并，因为最多有$10^6$次操作，如果按照题意暴力合并复杂度能够达到$O(N^2)$，而启发式合并能够保证复杂度为$O(N log_2 N)

我们开两个双端队列模拟栈，最初队首为栈底，队尾为栈顶，前面四个操作直接在队尾执行，每次复杂度O(1)

对于第5个操作DEL，直接暴力讲队列清空，每次复杂度O(n)，均摊复杂度O(1)

对于第7个操作SWAP，我们记录f_0和f_1，表示输入的x号栈对应的是第f_x号队列，操作时直接讲f_0和f_1 SWAP即可，注意，f_0 f_1一定要分别置初值{0,1}，每次复杂度O(1)

对于毒瘤的第6个操作MOVE，我们考虑两种情况（注意，题目要求将Y栈移动到X栈）：

当Y栈小于X栈时，直接暴力将Y栈里的元素移到X栈里

当Y栈大于X栈
我们借助Tag_0\text{和}Tag_1表示这个队列是否反转，即队头变队尾，队尾变队头，初始化都为零，表示没有反转
我们将X栈里的元素按照出栈顺序一一移动到Y栈
然后再将Tag_Y\ XOR\ \ 1，因为两次反转则等于没有反转
最后SWAP(f_x,f_y)
为什么这样是对的，因为将Y栈移动到X栈正好是将X栈移动到Y栈的反转序列，自己画个图就知道了

每次复杂度O(n)，均摊复杂度O(log_2N)

Code:$ $O(N log_2 N)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
deque<ll>q[2];
int f[2]={0,1};
int tag[2]={0,0};
int main()
{
    char k[10];int x,y;ll X,Y;
    while(true){
        scanf("%s",k);
        if(k[0]=='P'&&k[1]=='O'){
            scanf("%d",&x);
            if(!q[f[x]].size()){
                puts("UNSUCCESS");
            }
            else{
                puts("SUCCESS");
                if(tag[f[x]]){
                    q[f[x]].pop_front();
                }
                else q[f[x]].pop_back();
            }
        }
        else if(k[0]=='P'&&k[1]=='U'){
            scanf("%d%lld",&x,&Y);
            puts("SUCCESS");
            if(tag[f[x]]){
                q[f[x]].push_front(Y);
            }
            else q[f[x]].push_back(Y);
        }
        else if(k[0]=='A'&&k[1]=='D'){
            scanf("%d",&x);
            if(!q[0].size()||!q[1].size()){
                puts("UNSUCCESS");
            }
            else{
                puts("SUCCESS");
                ll a,b;
                if(tag[0])a=q[0].front(),q[0].pop_front();
                else a=q[0].back(),q[0].pop_back();
                if(tag[1])b=q[1].front(),q[1].pop_front();
                else b=q[1].back(),q[1].pop_back();
                if(tag[f[x]]){
                    q[f[x]].push_front(a+b);
                }
                else{
                    q[f[x]].push_back(a+b);
                }
            }
        }
        else if(k[0]=='S'&&k[1]=='U'){
            scanf("%d",&x);
            if(!q[0].size()||!q[1].size()){
                puts("UNSUCCESS");
            }
            else{
                puts("SUCCESS");
                ll a,b;
                if(tag[0])a=q[0].front(),q[0].pop_front();
                else a=q[0].back(),q[0].pop_back();
                if(tag[1])b=q[1].front(),q[1].pop_front();
                else b=q[1].back(),q[1].pop_back();
                if(tag[f[x]]){
                    q[f[x]].push_front(abs(a-b));
                }
                else{
                    q[f[x]].push_back(abs(a-b));
                }
            }
        }
        else if(k[0]=='D'&&k[1]=='E'){
            scanf("%d",&x);
            puts("SUCCESS");
            tag[f[x]]=0;
            while(q[f[x]].size())q[f[x]].pop_back();
        }
        else if(k[0]=='M'&&k[1]=='O'){
            scanf("%d%d",&x,&y);
            puts("SUCCESS");
            if(q[f[x]].size()<q[f[y]].size()){
                while(q[f[x]].size()){
                    ll a;
                    if(tag[f[x]])a=q[f[x]].front(),q[f[x]].pop_front();
                    else a=q[f[x]].back(),q[f[x]].pop_back();
                    if(tag[f[y]])q[f[y]].push_front(a);
                    else q[f[y]].push_back(a);
                }
                tag[f[y]]^=1;
                swap(f[0],f[1]);
            }
            else{
                while(q[f[y]].size()){
                    ll a;
                    if(tag[f[y]])a=q[f[y]].front(),q[f[y]].pop_front();
                    else a=q[f[y]].back(),q[f[y]].pop_back();
                    if(tag[f[x]])q[f[x]].push_front(a);
                    else q[f[x]].push_back(a);
                }
            }
        }
        else if(k[0]=='S'&&k[1]=='W'){
            swap(f[0],f[1]);puts("SUCCESS");
        }
        else if(k[0]=='E'&&k[1]=='N'){
            puts("SUCCESS");
            if(!q[f[0]].size())puts("NONE");
            else {
                if(tag[f[0]]){
                    while(q[f[0]].size())
                      printf("%lld ",q[f[0]].front()),q[f[0]].pop_front();
                }
                else{
                    while(q[f[0]].size())
                      printf("%lld ",q[f[0]].back()),q[f[0]].pop_back();
                }
                puts("");
            }
            if(!q[f[1]].size())puts("NONE");
            else {
                if(tag[f[1]]){
                    while(q[f[1]].size())
                      printf("%lld ",q[f[1]].front()),q[f[1]].pop_front();
                }
                else{
                    while(q[f[1]].size())
                      printf("%lld ",q[f[1]].back()),q[f[1]].pop_back();
                }
                puts("");
            }
            break;
        }
    }
    return 0;
}