M_sea

洛谷5375 [THUPC2019]组合数据结构问题
LuoguLOJ分析做道傻逼题休闲一下本题考察了选手对于 STL 的熟练程度(直接模拟每个操作判断是否相等即可。注...
扫描右侧二维码阅读全文
15
2019/05

洛谷5375 [THUPC2019]组合数据结构问题

Luogu

LOJ

分析

做道傻逼题休闲一下

本题考察了选手对于 STL 的熟练程度(

直接模拟每个操作判断是否相等即可。

注意要取出时判一下数据结构空的情况。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n;
struct query { int op,v; } q[N];

inline int check_queue() {
    queue<int> Q;
    for (re int i=1;i<=n;++i) {
        if (q[i].op==1) Q.push(q[i].v);
        else {
            if (Q.empty()) return 0;
            if (Q.front()!=q[i].v) return 0;
            Q.pop();
        }
    }
    return 1;
}

inline int check_stack() {
    stack<int> Q;
    for (re int i=1;i<=n;++i) {
        if (q[i].op==1) Q.push(q[i].v);
        else {
            if (Q.empty()) return 0;
            if (Q.top()!=q[i].v) return 0;
            Q.pop();
        }
    }
    return 1;
}

inline int check_heap1() {
    priority_queue<int> Q;
    for (re int i=1;i<=n;++i) {
        if (q[i].op==1) Q.push(q[i].v);
        else {
            if (Q.empty()) return 0;
            if (Q.top()!=q[i].v) return 0;
            Q.pop();
        }
    }
    return 1;
}

inline int check_heap2() {
    priority_queue<int,vector<int>,greater<int> > Q;
    for (re int i=1;i<=n;++i) {
        if (q[i].op==1) Q.push(q[i].v);
        else {
            if (Q.empty()) return 0;
            if (Q.top()!=q[i].v) return 0;
            Q.pop();
        }
    }
    return 1;
}


int main() {
    n=read();
    for (re int i=1;i<=n;++i) q[i].op=read(),q[i].v=read();
    puts(check_queue()?"Yes":"No");
    puts(check_stack()?"Yes":"No");
    puts(check_heap1()?"Yes":"No");
    puts(check_heap2()?"Yes":"No");
    return 0;
}
最后修改:2019 年 05 月 26 日 10 : 08 PM

3 条评论

  1. Itst

    我们队差5s拿这道题一血(大哭

    1. memset0
      @Itst

      Orz Itst !

    2. M_sea
      @Itst

      Autst!!!

发表评论