1 条题解

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

    指令计算栈:讲解

    思路与 STL 接口

    stack 保存中间数。二元运算先读取 top 并 pop 得到 b,再得到 a,最后 push 结果;NEG 修改 top;DUP 把 top 的值 push 一份。使用 stoll 识别数字。C++17 整数除法向 0 取整。

    复杂度

    每个 token 执行 O(1) 次栈操作,总时间 O(n),空间 O(n)。范围保证结果和所有中间值都在 long long 内;乘法实际结果的绝对值≤10¹²。

    常见错误

    把弹出的第一项当成左操作数,减法与除法会反向;用 int 溢出;Python 对照若用 // 会向负无穷取整,须用整数绝对值除法后恢复符号。

    验证方法

    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 n;cin>>n;stack<long long>s;while(n--){string t;cin>>t;if(t=="NEG")s.top()=-s.top();else if(t=="DUP")s.push(s.top());else if(t=="+"||t=="-"||t=="*"||t=="/"){long long b=s.top();s.pop();long long a=s.top();s.pop();if(t=="+")s.push(a+b);else if(t=="-")s.push(a-b);else if(t=="*")s.push(a*b);else s.push(a/b);}else s.push(stoll(t));}cout<<s.top()<<'\n';}
    
    
    • 1

    信息

    ID
    5258
    时间
    2000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    1
    已通过
    1
    上传者