听取 WA 声一片

P4387 【深基15.习9】验证栈序列

Maple_plain @ 2023-03-23 20:54:37

在此打扰了，

各位奆奆可否帮蒟蒻看一下哪里出了问题？

无一幸免地 \colorbox{red}{\textcolor{white}{wa}} 掉了

by Maple_plain @ 2023-03-23 20:55:03

#include <bits/stdc++.h>

using namespace std;
int pusheed[100001];

int main (){
    stack<int> pushed;
    queue<int> poped;
    int q,n,a,u=1;
    bool g=false;
    cin>>q;
    while(q--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>pusheed[i];
        }
        for(int i=1;i<=n;i++){
            cin>>a;
            poped.push(a);
        }
        while(u<=n||(g!=false&&pushed.empty()!=true)){
            if(u<=n)
             pushed.push(pusheed[u++]);
            if(pushed.top()==poped.front()){
                g=true;
                pushed.pop();
                poped.pop();
            }
            else{
                g=false;
            }
        }
        if(g==true) cout<<"Yes";
        else cout<<"No";
        poped=queue<int>();
        pushed=stack<int>();
        g=false;
        u=1;
    }
    return 0;
}

by Maple_plain @ 2023-03-27 20:08:30

#include <bits/stdc++.h>

using namespace std;
int pusheed[100001];

int main (){
    stack<int> pushed;
    queue<int> poped;
    int q,n,a,u=1;
    bool g=false;
    cin>>q;
    while(q--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>pusheed[i];
        }
        for(int i=1;i<=n;i++){
            cin>>a;
            poped.push(a);
        }
        while(u<=n||(g!=false&&pushed.empty()!=true)){
            if(u<=n)
             pushed.push(pusheed[u++]);
            if(pushed.top()==poped.front()){
                g=true;
                pushed.pop();
                poped.pop();
            }
            else{
                g=false;
            }
        }
        if(g==true) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        poped=queue<int>();
        pushed=stack<int>();
        g=false;
        u=1;
    }
    return 0;
}

by Maple_plain @ 2023-03-27 20:29:21

#include <bits/stdc++.h>

using namespace std;
int pusheed[100001];

int main (){
    stack<int> pushed;
    int q,n,a=1,m;
    cin>>q;
    while(q--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>pusheed[i];
        }
        for(int i=1;i<=n;i++){
            cin>>m;
            pushed.push(m);
            while(pushed.top()==pusheed[a]){
                a++;
                pushed.pop();
                if(pushed.empty()==true) break;
            }
        }
        if(pushed.empty()==true)
         cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        pushed=stack<int>();
        a=1;
    }
    return 0;
}

by sunfish @ 2023-03-28 22:16:31

呃，你把入栈出栈搞反了吧。。

by sunfish @ 2023-03-28 22:30:27

先入后出，反推肯定是不对的。。。

需要先加一个popeed数组记录可能的出栈队列，把

for(int i=1;i<=n;i++){
    cin>>m;
    pushed.push(m);
    while(pushed.top()==pusheed[a]){
    a++;
    pushed.pop();
    if(pushed.empty()==true) break;
     }
 }

改成

for (int i = 1; i <= n; i++) {
    cin >> popeed[i];
}
for (int i = 1; i <= n; i++) {
  pushed.push(pusheed[i]);
  while (pushed.top() == popeed[a]) {
    a++;
    pushed.pop();
    if (pushed.empty() == true)
        break;
    }
}

就可以ac了

by sunfish @ 2023-03-28 22:31:57

不太会用洛谷的格式，粘贴上的代码怪怪的。。。将就看吧@Dream_Crosyia

by Maple_plain @ 2023-03-30 18:00:45

@sunfish 谢高人指点

|