Skip to content

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

3 12
1 1
1 2
2 3
0 1
-1
1 4
0 2
0 1
0 3
-2
0 1
0 3

Sample Output

2
3
4
0
2
0

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;
}