1 条题解

  • 0
    @ 2026-11-16 20:48:26

    动态清单:讲解

    思路与 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
    上传者