U41572 Portal2

题目背景

某地ENLIGHTENED的XM研究所正在研究Portal的处理法则，想要揭示XM能量的来源以及应用XM能量。ENLIGHTENED的首席科学家Jacks发现其能量的运算法则以及运算方法，但是方法十分复杂，仅靠人手工计算是很难算出答案的，所以它需要你协助他完成计算。

题目描述

Portal计算XM能量是通过个22个栈（00号栈，11号栈）实现的，它把对XM能量的操作如下

PUSHPUSH XX NUMNUM

把NUMNUM加入到X号栈的栈顶。

POPPOP XX

把XX号栈的栈顶元素删除。

ADDADD XX

取出00号栈和11号栈的元素各一个，并且把它的和放入XX号栈。

SUBSUB XX

取出00号栈和11号栈的元素各一个，并且把它的差的绝对值放入XX号栈。

DELDEL XX

清空XX号栈中所有元素不管栈是否为空。

MOVEMOVE XX YY

循环操直到YY号栈为空，把YY号栈的栈顶元素加入到XX号栈，删除YY号栈的栈顶元素。

数据保证X和Y不相同

SWAPSWAP

将两个栈的所有元素调换。

ENDEND

代表命令结束，并且分两行分别输出0号栈和1号栈由栈顶到栈底的元素的值，若栈内无元素，输出NONE。数据保证指令以END结束且仅有一个END，并且也需要输出SUCCESS。

~~AKNOIAKNOI~~

~~等为无效操作，无效操作后不接数字。~~

更正不会有类似无效操作

对于每一行指令，若当前指令成功执行输出SUCCESS，若取出或删除元素时栈内为空或者没有对应指令输出UNSUCCESS并且不执行该行指令。

输入输出格式

输入格式：

输入若干行指令，以END指令结束

输出格式：

对于每一次操作，都要对应输出SUCCESS或者UNSUCCESS，对于END根据指令描述输出栈内元素。

输入输出样例

输入样例#1：复制

PUSH 0 10

PUSH 0 20

PUSH 0 30

PUSH 0 40

PUSH 1 50

PUSH 1 60

ADD 0

ADD 0

ADD 0

END

输出样例#1：复制

SUCCESS

SUCCESS

SUCCESS

SUCCESS

SUCCESS

SUCCESS

SUCCESS

SUCCESS

UNSUCCESS

SUCCESS

150 30 20 10

NONE

输入样例#2：复制

PUSH 0 10

PUSH 0 20

PUSH 0 30

PUSH 0 40

PUSH 1 50

PUSH 1 60

MOVE 0 1

END

输出样例#2：复制

SUCCESS

SUCCESS

SUCCESS

SUCCESS

SUCCESS

SUCCESS

SUCCESS

SUCCESS

50 60 40 30 20 10

NONE

说明

对于20\%20%的数据数据保证不会出现MOVE/SWAP操作，$命令总数 \leq 100$

对于40\%40%的数据 $命令总数 \leq 1000$

对于60\%60%的数据数据保证MOVE/SWAP的操作次数不会超过1000010000次，$命令总数 \leq 10^5$

对于100\%100%的数据 $0 \leq X,Y \leq 1,命令总数 \leq 10^6$

数据保证无论任何情况，栈中元素的值XX满足$0 \leq x \leq 2^{63}-1$

题目创意来源OIERBBS

/*

最暴力的模拟思路了 60分

正解应该是在move和swap操作上用了什么奇奇怪怪的高级的东西。

*/

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

string s;

int x,y,top[];

long long num[],stack[][];

int main(){

    while(cin>>s){

        if(s[]=='P'&&s[]=='U'){

            scanf("%d%d",&x,&y);

            stack[x][++top[x]]=y;

            printf("SUCCESS\n");

        }

        else if(s[]=='P'&&s[]=='O'){

            scanf("%d",&x);

            if(top[x]==)    printf("UNSUCCESS\n");

            else{

                top[x]--;printf("SUCCESS\n");

            }

        }

        else if(s[]=='A'){

            scanf("%d",&x);

            if(top[]==||top[]==)    printf("UNSUCCESS\n");

            else{

                int x0=stack[][top[]--];

                int x1=stack[][top[]--];

                stack[x][++top[x]]=x0+x1;

                printf("SUCCESS\n");

            }

        }

        else if(s[]=='S'&&s[]=='U'){

            scanf("%d",&x);

            if(top[]==||top[]==)    printf("UNSUCCESS\n");

            else{

                int x0=stack[][top[]--];

                int x1=stack[][top[]--];

                stack[x][++top[x]]=abs(x0-x1);

                printf("SUCCESS\n");

            }

        }

        else if(s[]=='D'){

            scanf("%d",&x);top[x]=;

            printf("SUCCESS\n");

        }

        else if(s[]=='M'){

            scanf("%d%d",&x,&y);

            while(top[y]){

                int tmp=stack[y][top[y]];

                stack[x][++top[x]]=tmp;

                top[y]--;

            }

            printf("SUCCESS\n");

        }

        else if(s[]=='S'&&s[]=='W'){

            for(int i=;i<=top[];i++)

                num[i]=stack[][i];

            for(int i=;i<=top[];i++)

                stack[][i]=stack[][i];

            for(int i=;i<=top[];i++)

                stack[][i]=num[i];

            swap(top[],top[]);

            printf("SUCCESS\n");

        }

        else if(s[]=='E'){

            printf("SUCCESS\n");

            if(top[])

                for(int i=top[];i>=;i--)

                    cout<<stack[][i]<<" ";

            else printf("NONE");printf("\n");

            if(top[])

                for(int i=top[];i>=;i--)

                    cout<<stack[][i]<<" ";

            else printf("NONE");

            return ;

        }

    }

}

60分

所以说emm...正解是用链表进行维护的。

#include <bits/stdc++.h>

#define ll long long

#define rep(i,l,r) for (int i = l; i <= r; i++)

#define getc(x) getchar(x)

#define putc(x) putchar(x)

template <typename T> inline void read(T &x) {

    x = ; register char ch; register bool fl = ;

    while (ch = getc(), ch <  ||  < ch) fl ^= ch == '-'; x = (ch & );

    while (ch = getc(),  < ch && ch < ) x = (x << ) + (x << ) + (ch & );

    if (fl) x = -x;

}

template <typename T> inline void readc(T &x) {

    while (x = getc(), !islower(x) && !isupper(x));

}

template <typename T> inline void print(T x, char c = ' ') {

    static int buf[];

    if (x == ) { putc(''); putc(c); return; }

    if (x < ) putc('-'), x = -x;

    for (buf[] = ; x; x /= ) buf[++buf[]] = x %  + ;

    while (buf[]) putc((char) buf[buf[]--]);

    putc(c);

}

const int maxn = ;

int x, y, opt, cnt, finish_game;

int pre[maxn], nxt[maxn], hed[];

ll k, val[maxn];

inline void link(int u, int v) {

    nxt[u] = v;

    pre[v] = u;

}

inline void simple_push(int u, int v, ll w) {

    val[++cnt] = w;

    link(u, cnt);

    link(cnt, v);

}

inline void push(int x, ll k) {

    if (x == ) simple_push(pre[], , k);

    else simple_push(, nxt[], k);

}

inline ll pop(int u) {

    link(pre[u], nxt[u]);

    return val[u];

}

void printout(int u) {

    if (u == ) {

        if (pre[] == ) {

            printf("NONE\n");

            return;

        }

        for (int i = pre[]; i != ; i = pre[i])

            print(val[i]);

        putc('\n');

    } else {

        if (nxt[] == ) {

            printf("NONE\n");

            return;

        }

        for (int i = nxt[]; i != ; i = nxt[i])

            print(val[i]);

        putc('\n');

    }

}

int read_opt() {

    char c1, c2;

    readc(c1), readc(c2);

    if (c1 == 'P')

        return c2 == 'U' ?  : ;

    if (c1 == 'A')

        return ;

    if (c1 == 'S') {

        if (c2 == 'U')

            return ;

        readc(c2), readc(c2);

        return ;

    }

    if (c1 == 'D')

        return ;

    if (c1 == 'M')

        return ;

    if (c1 == 'E')

        return ;

    return ;

}

bool solve(int opt) {

    if (opt == ) {

        read(x), read(k);

        x = hed[x];

        push(x, k);

    } else if (opt == ) {

        read(x);

        x = hed[x];

        if (x == ) {

            if (pre[] == ) return false;

            pop(pre[]);

        } else {

            if (nxt[] == ) return false;

            pop(nxt[]);

        }

    } else if (opt == ) {

        read(x);

        x = hed[x];

        if (pre[] ==  || nxt[] == ) return false;

        push(x, pop(pre[]) + pop(nxt[]));

    } else if (opt == ) {

        read(x);

        x = hed[x];

        if (pre[] ==  || nxt[] == ) return false;

        push(x, std::abs(pop(pre[]) - pop(nxt[])));

    } else if (opt == ) {

        read(x);

        x = hed[x];

        if (x == ) link(, );

        else link(, );

    } else if (opt == ) {

        read(x), read(y);

        x = hed[x], y = hed[y];

        link(pre[], nxt[]);

        if (x == ) {

            link(pre[], );

            link(, );

        } else {

            link(, nxt[]);

            link(, );

        }

    } else if (opt == ) {

        std::swap(hed[], hed[]);

    } else if (opt == ) {

        finish_game = ;

    }

    return true;

}

int main() {

    cnt = ;

    link(, ), link(, );

    hed[] = , hed[] = ;

    while (!finish_game) {

        opt = read_opt();

        if (solve(opt)) puts("SUCCESS");

        else puts("UNSUCCESS");

    }

    printout(!hed[] ?  : );

    printout(!hed[] ?  : );

    return ;

}

巴特西

洛谷 U41572 Portal2

U41572 Portal2

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章