1 条题解
-
0
动态清单:讲解
思路与 STL 接口
用 vector 保存清单。PUSH 对应 push_back;POP 先检查 empty,再读取 back 并 pop_back。GET 先检查负下标及 i<size,再用下标访问;SIZE 用 size。
复杂度
PUSH 的均摊时间 O(1),其他操作 O(1);总时间 O(q),额外空间 O(q)。
常见错误
把下标误认为从 1 开始;先转换成无符号再检查负值;空容器调用 back;误以为 pop_back 返回被删除值。
验证方法
Python oracle 独立读取操作并模拟或排序,不调用标准程序。正式数据含手算样例、边界、固定种子随机和两个最大规模用例;另做 200 次小规模差分,验证器拒绝非法状态和多余 token。common_wrong.cpp 保留上述一种常见逻辑错误,正式数据必须能够拒绝它。
C++17 参考实现
#include <bits/stdc++.h> using namespace std; int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int q;cin>>q;vector<long long>a;while(q--){string op;cin>>op;if(op=="PUSH"){long long x;cin>>x;a.push_back(x);}else if(op=="POP"){if(a.empty())cout<<"EMPTY\n";else{cout<<a.back()<<'\n';a.pop_back();}}else if(op=="GET"){long long i;cin>>i;if(i<0 || i>=static_cast<long long>(a.size()))cout<<"OUT_OF_RANGE\n";else cout<<a[i]<<'\n';}else cout<<a.size()<<'\n';}}
- 1
信息
- ID
- 5254
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- 递交数
- 3
- 已通过
- 2
- 上传者