11120: 【原1120】二哥的嘲讽

题目

题目描述

author: Huihuang Zheng 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1120

Description

助教说，今晚的最后一次机考题目都不难，所以要争取拿满分哦~O(∩_∩)O~，加油！！

二哥有了女朋友后，常常夜不归宿，问其去干嘛了，他说跟女朋友通宵自习去了。。。

这天晚上，二哥的舍友小Z在写编译器大作业，二哥又要去见妹子了。走之前，二哥幸福地唱

道：“在宿舍里面有两个可怜的小码农，深夜码代码，在写编译器”...小Z面对二哥的嘲讽，愤愤地说，你能解决下面这个问题再嘲讽吧..= =

C++中，在花括号中再次声明一个同名变量时，会有以下特性：

int x = 0;
{
    int x = 1;
    printf("%d\n", x); // 输出1，不再是上一层x
    x = 3;
    printf("%d\n", x); // 输出3
}
printf("%d\n", x); // 输出0 花括号里的变量x空间被释放后不存在了

现在假设有变量x1,x2...xn,都被初始化为0，在花括号中他们可能被重新声明或者赋值，也有可能需要用到他们的值，请你在需要用到他们时，输出他们正确的值。

Input Format

第1行，两个正整数 N, K 代表有N个变量，分别标号x1...xn，之后有k行代码为表示方便，接下来的k行输入都是整数代表代码，每行只有一种代码，有这几种代码：第一种，一个整数 -1 代表花括号开始第二种，一个整数 -2 代表花括号结束第三种，两个整数 0 m，代表你需要输出xm的值,m是正整数，下也是。第四种，两个整数 m v，若这个花括号中还没声明xm，则代表声明xm变量并赋值为v；若已声明xm，则只代表xm被赋值为v。

Output Format

每次 0 m 操作输出一行，输出xm的值

Sample Input

Sample Output

Restrictions

数据保证花括号匹配，所有整数在int型里足够。N <= 1000, K <= 400000,时间限制1.0s

FineArtz's solution

/* 二哥的嘲讽 */
#include <iostream>
using namespace std;

struct Node{
    int data = 0;
    int layer = 0;
    Node *next = nullptr;

    Node(int d = 0, int l = 0, Node *n = nullptr)
        : data(d), layer(l), next(n) {}
};

struct LinkStack{
    Node *head = new Node();
    int size = 0;

    void push(int d, int l){
        Node *p = new Node(d, l, head);
        head = p;
        ++size;
    }

    int top(){
        return head->data;
    }

    int topLayer(){
        return head->layer;
    }

    void pop(){
        Node *p = head;
        head = p->next;
        delete p;
    }

    void resetTop(int x){
        head->data = x;
    }

    void clear(){
        Node *p = head, *q;
        while (p){
            q = p;
            p = p->next;
            delete q;
        }
    }
};

LinkStack a[1005], b[200005];
int n, k, layer = 0;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    while (k--){
        int op, x;
        cin >> op;
        switch (op){
        case -1:
            ++layer;
            break;
        case -2:
            while (b[layer].top() != 0){
                a[b[layer].top()].pop();
                b[layer].pop();
            }
            --layer;
            break;
        case 0:
            cin >> x;
            cout << a[x].top() << '\n';
            break;
        default:
            cin >> x;
            if (a[op].topLayer() == layer)
                a[op].resetTop(x);
            else{
                a[op].push(x, layer);
                b[layer].push(op, 0);
            }
            break;
        }
    }
    return 0;
}