题解：P12347 [蓝桥杯 2025 省 A 第二场] 栈与乘积

张英毛 · 2025-04-27 15:01:46 · 题解

双栈模拟即可

大佬们都用线段树，退休 OIer 在考场上不想写。 所以强行模拟了一下，私以为是可行的，敬请斧正。

想法

将入栈元素分为三类：

• 其他正整数。

  为什么要这么分类呢？

  如果按照题意直接去模拟，对于操作 3 会超时，超时的原因就是因为 0 和 1 的存在！针对操作 3，我们做如下讨论：

  • 普普通通的其他正整数：累乘到 2^{32}，最多需要 32 次罢了，常数而已！——不需要特殊处理。
  • 毫无意义的数字 1：对它做乘法，对答案毫无贡献，反而会导致超时！——数字 1 不配入栈。
  • 毁天灭地的数字 0：如果累乘区间里有数字 0，那么其他数字都不再有意义！——数字 0 单独处理。

    思路

    1. 创建两个栈（普通栈、零栈）去模拟题意中的一个栈（实际栈）：
  • 普通栈：存放其他正整数及其在实际栈中的位置，也就是普通栈的入栈元素是数对<数值，位置>。
  • 零栈：存放数字 0 在实际栈中的位置。
  • 实际栈:只维护其栈顶指针 top 即可。
  • 那么没有记录的就是毫无意义的数字 1 了。
    2. 对于操作 1，就分门别类的入栈就行了，该去哪去哪。
    3. 对于操作 2，出栈时先判断那两个栈的栈顶元素与当前要出实际栈的栈顶位置是不是一致，如果一致就一块出栈；否则说明要出栈的是数字 1，只更改实际栈的栈顶即可。
    4. 对于操作 3：
  • 先判断是否 y \le top，如果否，则输出 ERROR。
  • 再根据零栈的栈顶元素，判断数字 0 是否在实际栈的前 y 个元素中，如果是，则输出 0。
  • 然后累乘普通栈的栈顶前几个元素计算答案就可以了，根据元素的位置信息就可判断其是否在实际栈的前 y 个元素中，并且最多累乘 32 次就会超出大小限制，如果超出限制则输出 OVERFLOW，否则就输出累乘的结果。

    时间复杂度：O(Q)

  • 操作 1：O(1)。
  • 操作 2：O(1)。
  • 操作 3：最多累乘 32 次。

    实现：

    
    #include<iostream>
    #include<cstring>
    #include<string>
    using namespace std;
    struct lp{
    long long val;
    int pos;
    }a[100005];
    int Q,op,y,top,cnt,zero[100005],tz;
    long long ans,x; 
    int main() {
    cin>>Q;
    while (Q--) {
    cin>>op;
    if (op==1) {
        cin>>x;
        top++;
        if (x==0) zero[++tz] = top; //零 入栈 
        else if (x!=1) {  //非1正整数  入栈 
            cnt++;
            a[cnt].val=x;
            a[cnt].pos=top; 
        }
    }
    else if (op==2) {
        if (top) {
            if (top==zero[tz]) { //零 出栈 
                top--;
                tz--;
            }
            else if (top==a[cnt].pos) {//非1正整数 出栈 
                top--;
                cnt--;
            } 
            else top--;//壹 出栈 
        }
    }
    else if (op==3) {
        cin>>y;
        if (y>top) cout<<"ERROR"<<endl;
        else if (tz&&top-zero[tz]+1<=y) cout<<0<<endl; //零 
        else {              //累积 
            ans=1;
            int t=0;
            while (top-a[cnt-t].pos+1<=y) {
                ans*=a[cnt-t].val;
                if (ans>=4294967296) break;
                t++;
            } 
            if (ans>=4294967296) cout<<"OVERFLOW"<<endl;
            else cout<<ans<<endl;
        }
    }
    }

}