数据结构总结——栈进阶

program_xwl · 2024-07-28 19:55:38 · 算法·理论

由于栈的原理与构造过于简单，直接开始讲题。

T1 [COCI2010-2011#7] GITARA

思路

用 6 个栈从小到大（大的这边是栈顶）存储在单根弦上每此按下的段。\ 对于每一个段，如果该段的音调大于栈顶（如果有的话），那么就弹出栈顶，弹出一个计数器就加一个 1 ，这是将所有同一根弦上的大于该段的段全部松开。不断执行上面的操作，直到栈顶大于或等于该段的音调或是栈空了。\ 然后，判断如果栈顶小于该段，将该段入栈，计数器++；等于的话什么也不用做，说明之前按过，虽然题目没说，但如果没有这条样例1就不成立了，这是一个细节点。

代码：

#include <bits/stdc++.h>
using namespace std;

long long T,p,cnt = 0;
stack<long long>st[15];

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T >> p;
    while(T--)
    {
        long long x,y;
        cin >> x >> y;
        while(st[x].size() && st[x].top() > y)
        {
            st[x].pop();
            cnt++;
        }
        if(st[x].size() && st[x].top() == y) continue;
        cnt++;
        st[x].push(y);
    }
    cout << cnt;
    return 0;
}

T2 『MGOI』Simple Round I | B. 魔法照相馆

本题和栈没什么关系。

思路：

用三个布尔变量存储三个幕布是否降下，初始时全部全部为 1 。对于背景的三种颜色，每次只要分别满足以下条件：

背景为白色：白幕布为降下状态。
背景为蓝色：蓝幕布为降下状态，白幕布为非降下状态
背景为红色：蓝幕布和白幕布都为非降下状态，红幕布为降下状态。

从前往后遍历所给字符串，输出三个变量一共改变了多少次即可。

代码：

#include <bits/stdc++.h>
using namespace std;

int T,cnt = 0;
bool bdown = 1,wdown = 1;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--)
    {
        char c;
        cin >> c;
        if(c == 'R')
        {
            if(bdown)
            {
                cnt++;
                bdown = 0;
            }
            if(wdown)
            {
                cnt++;
                wdown = 0;
            }
        }else if(c == 'B')
        {
            if(wdown)
            {
                cnt++;
                wdown = 0;
            }
            if(bdown == 0)
            {
                cnt++;
                bdown = 1;
            }
        }else
        {
            if(wdown == 0)
            {
                cnt++;
                wdown = 1;
            }
        }
    }
    cout << cnt;
    return 0;
}

T3 日志分析

思路：

我们用两个栈，一个模拟仓库，一个记录当前最大值。\ 由于删除操作只会影响栈顶元素，而不会影响栈顶以下的元素，每次查询操作直接输出最大值栈的栈顶，删除时两个栈顶一起弹出，这时候最大值栈的栈顶相当于回到了还没加入刚删除栈顶的时候了，具体如下图：

注意每次调用栈顶或是弹出栈顶时要判断栈是否为空

代码：

#include <bits/stdc++.h>
using namespace std;

int T;
stack<int>st,maxi;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--)
    {
        int op;
        cin >> op;
        if(op == 0)
        {
            int x;
            cin >> x;
            st.push(x);
            if(maxi.size()) maxi.push(max(maxi.top(),x));
            else maxi.push(x);
        }else if(op == 1)
        {
            if(st.size())
            {
                st.pop();
                maxi.pop();
            }
        }else
        {
            if(st.size()) cout << maxi.top() << '\n';
            else cout << "0\n";
        }
    }
    return 0;
}

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

思路：

一个一个把入栈序列（ pushed ）的元素压入栈，开一个指针 pt 指向出栈序列（ poped ）中位置最靠前的还未出栈的值。循环依次将入栈序列的值压入栈，如果栈顶（如果有的话）等于 poped_{pt} ，那么指针往后走一个元素，弹出栈顶。不断重复以上操作直到栈为空或是栈顶不等于 poped_{pt}。最后，如果栈为空，说明合法，反之亦然。

代码：

#include <bits/stdc++.h>
using namespace std;

int T,n,input[100005],output[100005];
stack<int>st;

bool check(void)
{
    int pt = 1;
    for(int i = 1;i <= n;i++)
    {
        st.push(input[i]);
        while(output[pt] == st.top())
        {
            st.pop();
            pt++;
            if(st.size() == 0) break;
        }
    }
    if(st.size()) return 0;
    return 1;
}

int main(void)
{
    while(st.size()) st.pop();
    cin >> T;
    while(T--)
    {
        cin >> n;
        for(int i = 1;i <= n;i++) cin >> input[i];
        for(int i = 1;i <= n;i++) cin >> output[i];
        while(st.size()) st.pop();
        if(check()) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

T5 [USACO11FEB] Best Parenthesis S

思路：

用栈存储每个当前层数的得分，具体操作如下：

左括号：放个 0 到栈顶，既表示新开了一层，也表示该层还没有嵌套的括号。
右括号：这意味着要结束一层，如果这一层的计数的得分为 0 说明里面没有嵌套的括号，得分为 1 给下层的计数器加上 1 即可；如果不为 0 说明里面还有嵌套括号的，将其乘 2 再加到下面的计数器即可。

开始时栈中应该有一个 0 以便累加。因为题目间接保证了括号序列一定合法，所以遍历完序列后栈的最后一个元素（其实就是开始加的那个 0 ）就是答案。

代码：

#include <bits/stdc++.h>
using namespace std;

const long long mod = 12345678910;
long long T;
stack<long long>cnt;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    cnt.push(0);
    while(T--)
    {
        long long op;
        char c;
        cin >> op;
        if(op == 0) c = '(';
        else c = ')';
        if(c == '(')
        {
            cnt.push(0);
        }else
        {
            long long u = cnt.top();
            cnt.pop();
            long long u2 = cnt.top();
            cnt.pop();
            if(u == 0)
            {
                cnt.push(u2+1);
            }else
            {
                cnt.push((u*2+u2)%mod);
            }
        }
    }
    cout << cnt.top();
    return 0;
}

T6 括号画家

思路：

用一个栈存储当前所有还未匹配的括号的下标。\ 当遇到前括号时，将其下标压入栈；遇到后括号时，如果其能与栈顶括号匹配（同种类型，并且是前括号），就弹出栈顶，配对成功；如果此时栈为空或是栈顶括号无法匹配，将其也压入栈表示它与它下面的都无法成功匹配。每次取个长度最大值：如果栈不为空，长度为当前位置到上一个未匹配括号的位置，如果栈为空，说明前面的全部都匹配上了，长度为当前点到起点的距离。

代码：

#include <bits/stdc++.h>
using namespace std;

string s;
int n,maxi = -1e9;
stack<int>st;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> s;
    n = s.size();
    s = " "+s;
    for(int i = 1;i <= n;i++)
    {
        if(st.size())
        {
            char u = s[st.top()];
            if((u == '{' && s[i] == '}') || (u == '[' && s[i] == ']') || (u == '(' && s[i] == ')')) st.pop();
            else st.push(i);
        }else
        {
            st.push(i);
        }
        if(st.size()) maxi = max(maxi,i-st.top());
        else maxi = max(maxi,i);
    }
    cout << maxi;
    return 0;
}