当前位置：首页 > news >正文

信奥赛-刷题笔记-栈篇-T3-P4387验证栈序列0520

news 2025/5/21 6:51:20

总题单

本部分总题单如下

【腾讯文档】副本-CSP-JS+NOI 题单 (未完待续)

https://docs.qq.com/sheet/DSmJuVXR4RUNVWWhW?tab=BB08J2

栈篇题单

请在此添加图片描述

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

题目描述

给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 $n(n\le100000)$ 。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。请注意，给定的序列一定是一个排列（即没有重复数字）。

为了防止骗分，每个测试点有多组数据，不超过 $5$ 组。

输入格式

第一行一个整数 $q$ ，询问次数。

接下来 $q$ 个询问，对于每个询问：

第一行一个整数 $n$ 表示序列长度；

第二行 $n$ 个整数表示入栈序列；

第三行 $n$ 个整数表示出栈序列；

输出格式

对于每个询问输出答案。

输入输出样例 #1

输入 #1

输出 #1

Yes
No

代码1

#include<iostream>
#include<stack>
using namespace std;
stack<int>q;//栈q 
int p,n;//p组数据，n为序列长度 
int main()
{cin>>p;while(p--){cin>>n;int a[n+1],b[n+1],sum=1;//入栈队列a，待检验队列b，计数器sum for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];//平平无奇的输入 for(int i=1;i<=n;i++){q.push(a[i]);//入栈 while((q.top())==b[sum])//当栈顶元素与b中当前元素相同时出栈 {q.pop(),sum++;//sum++到b下一个元素 if(q.empty())break;//注意这里，第一次RE就因为当栈空时还用了出栈操作，所以要手动结束循环 }}if(q.empty()) cout<<"Yes"<<endl;//如果栈为空说明出栈序列b正确 else cout<<"No"<<endl;while(!q.empty())q.pop();//清空栈 // stack<int>().swap(q);// 这种也能清空}return 0;//谢幕 
}

代码2

✅ 正确的解法思路（模拟栈）

我们模拟一个栈的操作过程：

维护一个栈和一个指针 i，指向 pushed 序列；
遍历 poped 数组，对于每一个要 pop 的元素：
- 如果当前栈顶不是该元素，则不断将 pushed[i] 压入栈中，直到 i == n 或者栈顶等于目标 pop 元素；
- 如果栈顶等于当前要 pop 的元素，则弹出；
- 否则返回 "No"。

最终如果栈为空，说明 poped 是合法的。

#include <bits/stdc++.h>
using namespace std;const int MAXN = 100010;int main() {int q;cin >> q;while (q--) {int n;cin >> n;vector<int> pushed(n), popped(n);for (int i = 0; i < n; ++i) cin >> pushed[i];for (int i = 0; i < n; ++i) cin >> popped[i];stack<int> st;int j = 0; // 指向 popped 的指针for (int num : pushed) {st.push(num);// 如果栈顶匹配当前 poped[j]，就弹出while (!st.empty() && st.top() == popped[j]) {st.pop();j++;}}if (j == n) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}

现场真题注意事项

https://cspoj.com/contest.php?cid=1002Fus5yz4x3EcSJH1Z

注意事项

文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用freopen()进行提交）

C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是0。

提交的程序代码文件的放置位置请参考各省的具体要求。

因违反以上三点而出现的错误或问题，申述时一律不予受理。

若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。

程序可使用的栈空间内存限制与题目的内存限制一致。

全国统一评测时采用的机器配置为：Inter® Core™ i7-8700K CPU @3.70GHz，内存 32GB。上述时限以此配置为准。

只提供 Linux 格式附加样例文件。

评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准

假设输入样例数据存在文件test.in中，输出样例数据存在文件test.out中，

则在CSP、NOI等比赛的代码中，需添加freopen、fclose语句，

内容详见模板代码如下。

#include <bits/stdc++.h>
#include<cstdio>//必须包含cstdio头文件
#include<iostream>
using namespace std;int main(){freopen("test.in","r",stdin);freopen("test.out","w",stdout);cout<<"Hello NOI"<<endl;fclose(stdin);fclose(stdout);return 0;
}

复制

下面为函数的简介，详细可参见 http://www.cplusplus.com/reference/clibrary/cstdio/freopen.html

函数名：freopen

声明：FILE _freopen( const char_ path, const char _mode, FILE_ stream );

所在文件： stdio.h

参数说明：

path: 文件名，用于存储输入输出的自定义文件名。

mode: 文件打开的模式。和fopen中的模式（如r-只读, w-写）相同。

stream: 一个文件，通常使用标准流文件。

返回值：成功，则返回一个path所指定文件的指针；失败，返回NULL。（一般可以不使用它的返回值）

功能：实现重定向，把预定义的标准流文件定向到由path指定的文件中。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。通过调用freopen，就可以修改标准流文件的默认值，实现重定向。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){freopen("7532.in", "r", stdin);freopen("7532.out", "w", stdout);//原来的代码保持不变double a, b, r;int k;cin >> a >> b;k = int(a/b);r = a - b * k;printf("%g", r);//-------------fclose(stdin);fclose(stdout);return 0;
}