麻了,把这讨论区所有出现的例子都试了一下,都能过,就是提交过不了

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

画船听雨 @ 2022-01-13 19:55:21

#include<iostream>
#include<stack>
#include<queue>
using namespace std;

int main() {
    int q, n, i, j,temp,temp1,temp2,temp3,sum,con,max=0,flag=0,acc=0;
    stack<int> a,c;
    queue<int> b;
    cin >> q;
    for (i = 0; i < q; i++) {
        cin >> n;
        sum = 0;
        for (j = 0; j < n; j++) {
            cin >> temp;
            a.push(temp);
            if (temp > max)
                max = temp;

        }
        for (j = 0; j < n; j++) {
            cin >> temp1;       
            b.push(temp1);

        }
        con = b.size();
        while (!b.empty()) {
            temp2 = b.front();
            temp3 = a.top();
            if (temp2 == max) {//如果出现最大值了,就说明出栈序列之后都不能存在逆序输出的。比如1 2 3 4 5和1 2 5 3 4。5出现之后记录下来,然后它后面的3和5隔了一个4,这样就不可行了。
                    flag = 1;
                }
            if (temp2 != temp3) {
                c.push(a.top());
                a.pop();
                if (flag == 1) {
                    acc++;
                    if (c.size() > 0) {
                        cout << "No" << endl;
                        while (!a.empty()) {
                            a.pop();
                        }
                        while (!b.empty()) {
                            b.pop();
                        }
                        while (!c.empty()) {
                            c.pop();
                        }
                        break;
                    }
                }

            }
            else {

                b.pop();
                a.pop();

                while (!c.empty()) {/*把c
 中所有的元素放到a里面*/
                    a.push(c.top());
                    c.pop();
                }
            }
            //sum++;
            //if (sum >= (con+1)*n/2) {
            //  cout << "No" << endl;
            //  break;
            //}
        if (b.size() == 0)
            cout << "Yes" << endl;
        }

    }
    return 0;
}

by Dream_weavers @ 2022-01-13 19:59:37

没有那么麻烦吧,一个栈就够了

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

by devans @ 2022-01-13 20:02:44

Counter Test:

Input:
2
2
1 2
1 2
3
1 2 3
2 3 1
Answer:
Yes
Yes
Output:
Yes
No

by 画船听雨 @ 2022-01-14 17:14:12

@Dream_weavers 确实进行栈模拟快且方便,但我当时没想到啊啊啊啊啊。第一次在洛谷系统写题,没经验


by 画船听雨 @ 2022-01-14 17:16:56

@siXYZit 我靠,好专业的大佬。可以冒昧问一句您是怎么发现反例的吗


by 画船听雨 @ 2022-01-14 17:45:15

@Dream_weavers 而且我发现我这种方法利用的内存确实要小很多,但是太浪费时间了,直接TLE


|