[ZOJ 4016] Mergable Stack

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4016

直接用栈爆内存，看网上大神用数组实现的，构思巧妙，学习了！

AC代码：

/* * 用数组实现栈的一些操作 */#include <cstdio>#include <cstring>using namespace std;const int maxn = 300005;int arr[maxn]; //存放所有的数据//top代表栈顶元素在arr中的下标，//Next代表栈顶元素下一个元素在arr中的下标，用于实现在栈顶元素被抛出后，栈顶新的指向，//bottom代表栈低元素在arr中的位置int top[maxn], Next[maxn], bottom[maxn];int main() {    int T;    scanf("%d", &T);    int n, q;    int op, cnt;    int s, v, t;    while (T--) {        cnt = 0;        memset(top, 0, sizeof(top));        memset(Next, 0, sizeof(Next));        memset(bottom, 0, sizeof(bottom));        scanf("%d%d", &n, &q);        while (q--) {            scanf("%d", &op);            if (op == 1) {                scanf("%d%d", &s, &v);                arr[  cnt] = v;                if (bottom[s] == 0) {  //如果原先栈为空，新加入的第一个元素将成为栈底元素                    bottom[s] = cnt;                }                //更新栈顶元素和栈顶的下一个元素                Next[cnt] = top[s]; //也可写作Next[top[s]] = top[s];                top[s] = cnt;            } else if (op == 2) {                scanf("%d", &s);                if (top[s]) {                    printf("%d\n", arr[top[s]]); //抛出栈顶元素，注意，top存放的是栈顶元素在arr中的下标                    top[s] = Next[top[s]]; //栈顶元素重定向                    if (top[s] == 0) {  //若栈为空，则栈顶和栈底都置为0，容易忽略这个判断                        bottom[s] = 0;                    }                } else {                    printf("EMPTY\n");                }            } else if (op == 3) {                scanf("%d%d", &s, &t);                if (top[t]) {                    if (bottom[s] == 0) {  //如果第s个栈为空，则s的栈底就是t的栈底                        bottom[s] = bottom[t];                    }                    //t的栈底元素的下一个为s的栈顶元素，这里不用在重定向s栈顶元素的下一个元素，因为t已经指定过了                    Next[bottom[t]] = top[s];                    top[s] = top[t];                }                top[t] = bottom[t] = 0; //把第t个栈置为空，容易忽略            }        }    }    return 0;}

我写的代码，不能AC

/* * Memory Limit Exceeded */#include <stack>#include <cstdio>using namespace std;const int maxn = 300005;stack<int> arr[maxn];int maze[maxn];int x, y, z;void solve_push(int y, int z) {    arr[y].push(z);}void solve_top(int y) {    if (!arr[y].empty()) {        int x = arr[y].top();        arr[y].pop();        printf("%d\n", x);    } else {        printf("EMPTY\n");    }}void solve_move(int y, int z) {    stack<int> temp;    int x;    while (!arr[z].empty()) {        x = arr[z].top();        arr[z].pop();        temp.push(x);    }    while (!temp.empty()) {        x = temp.top();        temp.pop();        arr[y].push(x);    }}int main() {    int t;    int n, q;    int flag;    scanf("%d", &t);    while (t--) {        flag = 0;        scanf("%d%d", &n, &q);        for (int i = 0; i < q; i  ) {            scanf("%d", &x);            if (x == 1) {                scanf("%d%d", &y, &z);                maze[flag  ] = y;                solve_push(y, z);            }            if (x == 2) {                scanf("%d", &y);                maze[flag  ] = y;                solve_top(y);            }            if (x == 3) {                scanf("%d%d", &y, &z);                maze[flag  ] = y;                maze[flag  ] = z;                solve_move(y, z);            }        }        for (int i = 0; i < flag; i  ) {            while (!arr[maze[flag]].empty()) {                arr[maze[flag]].pop();            }        }    }    return 0;}

来源：http://www.icode9.com/content-4-174751.html