__xxy_free_ioi__ @ 2023-05-26 20:43:19

#include <bits/stdc++.h>
using namespace std;
stack<int> s;
int q,n;
int a[100001],b[100001]; 
int main() {
    cin>>q;
    while(q--) {
        cin>>n;
        while(!s.empty()) s.pop(); 
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];
        int j=1;
        for(int i=1;i<=2*n;i++) {
            if(s.empty()) s.push(a[i]);
            if(s.top()==b[j]) s.pop(),j++;
            else if(i<=n) s.push(a[i]);
        }
        if(s.empty()) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

by SCAR_L @ 2023-05-27 09:06:16

@zhangchenggang 您的代码思路没有问题，只是for(int i=1;i<=2*n;i++)里有一点小问题，应该为：

for(int i=1;i<=2*n;i++) 
{
    if(i <= n)s.push(a[i]);
    while(!s.empty() && s.top() == b[j]) s.pop(),j++;
}

by SCAR_L @ 2023-05-27 09:09:10

@zhangchenggang 您可以参考一下我的代码：

// #include<bits/stdc++.h> 
#include <bits/stdc++.h>
using namespace std;
const int NR = 1e5+5;
stack<int> s;
int n;
int a[NR], b[NR]; 
int main() 
{
    int Q;
    cin >> Q;
    while(Q--) 
    {
        cin >> n;
        while(!s.empty()) s.pop(); 
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= n; i++) cin >> b[i];
        int pos = 1;
        for(int i = 1; i <= n; i++) 
        {
            while(!s.empty() && s.top() == b[pos]) s.pop(), pos++;
            s.push(a[i]);
        }
        while(!s.empty() && pos <= n && b[pos] == s.top()) s.pop(), pos++;
        if(pos == n + 1) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

by mooktian @ 2023-05-27 10:19:39

#include <bits/stdc++.h>
using namespace std;
stack<int> s;
int q,n;
int a[100001],b[100001]; 
int main() {
    cin>>q;
    while(q--) {
        cin>>n;
        while(!s.empty()) s.pop(); 
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];
        int j=1;
        for(int i=1;i<=n;i++) {
            s.push(a[i]);
            while(s.top()==b[j]) {
                s.pop(),j++;
                if(s.empty()) break;    
            }
        }
        if(s.empty()) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

by mooktian @ 2023-05-27 10:22:06

@zhangchenggang

#include <bits/stdc++.h>
#define f(i,a,b) for(int i=a;i<=b;i++)
#define g(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int q,n,top,p1=1,p2=1;
int a[100011],b[100011],c[100011];
int push(int x);
int pop();

int main(){
    cin >> q;
    while(q--) {
        cin >> n;

        f(i,1,n) cin >> a[i];
        f(i,1,n) cin >> b[i];
        for(;p1<=n;p1++) {
            push(a[p1]);
            while(b[p2] == c[top]) { //这里不能用if
                pop();
                p2++;
                if(p2 > n) break;
            }
        }
    /*  for(;p2<=n;p2++) {
            if(b[p2] == c[top]) pop();
            else {
                break;
            }
        }   */
        if(top>0) cout << "No\n";
        else cout << "Yes\n";
        top = 0;
        p1 = 1;
        p2 = 1;

    }
    return 0;
}
int push(int x) {
    top++;
    c[top] = x;
    //cout << "push: " << x;
    return x;
}
int pop() {
    top--;
    //cout << "pop: " << c[top+1];
    return c[top+1];
}

by SCAR_L @ 2023-05-27 12:17:49

@mooktian 您代码有的部分不是很严谨（虽然能过）。每次在调用top()和pop()之前都应该先调用empty()防止 RE。

by mooktian @ 2023-05-28 15:57:06

@SCAR_L 这个我自己胡乱写的，规范的化肯定是STL的stack，这题是模板题，能搞清楚原理就好。

by SCAR_L @ 2023-05-29 07:14:23

@mooktian 嗯嗯

by lihefan @ 2023-06-03 11:42:12

@zhangchenggang ```cpp

include <iostream>

include <stack>

using namespace std;

const int N = 100010; int a[N], b[N];

int main() { int q; cin >> q; while (q -- ) { int n; cin >> n; for (int i = 0; i < n; i ++ ) cin >> a[i]; for (int i = 0; i < n; i ++ ) cin >> b[i];

    stack<int> stk;
    int j = 0;
    for (int i = 0; i < n; i ++ )
    {
        stk.push(a[i]);
        while (stk.size() && stk.top() == b[j])
        {
            stk.pop();
            j ++ ;
        }
    }

    if (stk.empty()) puts("Yes");
    else puts("No");
}

return 0;

}