【蓝桥杯2025备赛】栈和单调栈

【蓝桥杯2025备赛】栈和单调栈

码农世界 2024-05-24 前端 77 次浏览 0个评论

栈

  • 栈(伪代码) 
    #include
using namespace std;
const int N=10010;
int stk[N],tt;
//插入
stk[++tt]=x;
//删除
tt--;
//判断是否为空
if(tt>0) not empty;
else empty;

    【模板】栈

    题目描述

    请你实现一个栈（stack），支持如下操作：

    • push(x)：向栈中加入一个数 x x x。
    • pop()：将栈顶弹出。如果此时栈为空则不进行弹出操作，输出 Empty。
    • query()：输出栈顶元素，如果此时栈为空则输出 Anguei!。
    • size()：输出此时栈内元素个数。

      输入格式

      本题单测试点内有多组数据。

      输入第一行是一个整数 T T T，表示数据组数。对于每组数据，格式如下：

      每组数据第一行是一个整数，表示操作的次数 n n n。

      接下来 n n n 行，每行首先由一个字符串，为 push，pop，query 和 size 之一。若为 push，则其后有一个整数 x x x，表示要被加入的数， x x x 和字符串之间用空格隔开；若不是 push，则本行没有其它内容。

      输出格式

      对于每组数据，按照「题目描述」中的要求依次输出。每次输出占一行。

      样例 #1

      样例输入 #1
      2
5
push 2
query
size
pop
query
3
pop
query
size
      样例输出 #1
      2
1
Anguei!
Empty
Anguei!
0

      提示

      样例 1 解释

      对于第二组数据，始终为空，所以 pop 和 query 均需要输出对应字符串。栈的 size 为 0。

      数据规模与约定

      对于全部的测试点，保证 1 ≤ T , n ≤ 1 0 6 1 \leq T, n\leq 10^6 1≤T,n≤106，且单个测试点内的 n n n 之和不超过 1 0 6 10^6 106，即 ∑ n ≤ 1 0 6 \sum n \leq 10^6 ∑n≤106。保证 0 ≤ x < 2 64 0 \leq x \lt 2^{64} 0≤x<264。

      提示

      • 请注意大量数据读入对程序效率造成的影响。

      • 因为一开始数据造错了，请注意输出的 Empty 不含叹号，Anguei! 含有叹号。

        注意两点:unsigned long long的范围是 0 0 0到 2 64 − 1 2^{64}-1 264−1,而long long的正数最大范围是到 2 63 − 1 2^{63}-1 263−1​

        二是要栈清空

        #include
using namespace std;
#define int unsigned long long//1.要unsigned long long,long long 会错 
const int N=1e6+5;
int x;
int tt;
int stk[N];
signed main()
{   int t;
    cin>>t;string s;
    while(t--)
    {
        int n;cin>>n;tt=0;//2.栈清空
        while(n--)
        {
            cin>>s;
            if(s=="push")
            {
                
                cin>>x;
                stk[++tt]=x;
            }
            else if(s=="query")
            {
                if(tt>0)cout<
                printf("%d\n",tt);
            }
            else if(s=="pop")
            {
                if(tt>0)tt--;
                else printf("Empty\n");
            }
            
        }
    }
    return 0;
}

        括号配对

        设表达式中允许包含3种括号：圆括号、方括号和大括号。即小括号、中括号和大括号。 编写一个算法来判断表达式中的括号是否正确配对，要求利用栈的结构实现。

        输入格式:

        输入一行带圆括号、方括号和大括号的字符串。

        输出格式:

        若匹配，输出yes。若不匹配，输出no。

        输入样例:

        在这里给出一组输入。例如：

        ([1+2])

        输出样例:

        在这里给出相应的输出。例如：

        yes

        输入样例:

        在这里给出一组输入。例如：

        ([

        输出样例:

        在这里给出相应的输出。例如：

        no

        思路：

        遇到“（”，“]”,"{"就入栈，遇到“）”，“]“，”}“就出栈和有符号进行比对，如果成功匹配就进行下一个，如果每个都成功的匹配，那么括号匹配就完全正确，如果中间有不匹配就break

        #include
using namespace std;
int main()
{
    string str;
    getline(cin,str);int flag=0;
    char topstr;stacks;
    for(int i=0;i   
        topstr=str[i];
        if(topstr=='('||topstr=='['||topstr=='{')s.push(topstr);
        if(topstr==')'||topstr==']'||topstr=='}')
        {
            if(s.empty()){flag=1;break;}//这一步的作用在于如果没有"(" "[" "{"的话，栈是空的，就不可能能匹配
            else 
            {
            if((s.top()=='('&&topstr==')')||(s.top()=='['&&topstr==']')||       (s.top()=='{'&&topstr=='}'))
                {
                    s.pop();
                }
                else {flag=1;break;}
            }
        }
        
    }
    if(flag==0&&s.empty())cout<<"yes";
    else cout<<"no";
    return 0;
}

        后缀表达式

        题目描述

        所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

        本题中运算符仅包含 +-*/ \texttt{+-*/} +-*/。保证对于 / \texttt{/} / 运算除数不为 0。特别地，其中 / \texttt{/} / 运算的结果需要向 0 取整（即与 C++ / 运算的规则一致）。

        如： 3*(5-2)+7 \texttt{3*(5-2)+7} 3*(5-2)+7 对应的后缀表达式为： 3.5.2.-*7.+@ \texttt{3.5.2.-*7.+@} 3.5.2.-*7.+@。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号。

        输入格式

        输入一行一个字符串 s s s，表示后缀表达式。

        输出格式

        输出一个整数，表示表达式的值。

        样例 #1

        样例输入 #1
        3.5.2.-*7.+@
        样例输出 #1
        16

        样例 #2

        样例输入 #2
        10.28.30./*7.-@
        样例输出 #2
        -7

        提示

        数据保证， 1 ≤ ∣ s ∣ ≤ 50 1 \leq |s| \leq 50 1≤∣s∣≤50，答案和计算过程中的每一个值的绝对值不超过 1 0 9 10^9 109。

        思路：

        表达式分为前缀表达式，中缀表达式和后缀表达式，其中对于人类来说最容易理解的就是我们的中缀表达式，我们每天进行的加减乘除，例如这种（1+1）*（2+2），运算符在操作数中间，这种表达式要考虑符号优先级，对于电脑来说中缀表达式很复杂，难以理解，相反，对于人类难以理解的后缀表达式和前缀表达式，电脑可以很好的理解，因为可以直接遍历而不用考虑优先级

        做法是遇到数字存储在数字栈中，如果遇到符号，则将数字栈中的两个数字弹出，进行运算，要注意先弹出的数字在运算时在操作符右侧，而后弹出的在左侧

        计算完毕后将中间数字入栈存储，直到后面有需要的时弹出栈顶元素进行计算，遍历完成后栈顶元素即为最终结果

        #include
using namespace std;
int main()
{
    string s;
    getline(cin,s);
    stacknum;
    char topstr;int a=0;
    for(int i=0;i
        topstr=s[i];
        if(topstr=='+'||topstr=='-'||topstr=='*'||topstr=='/')
        {   
            int a1=num.top();num.pop();
            int a2=num.top();num.pop();
            if(topstr=='+')num.push(a1+a2);
            else if(topstr=='-')num.push(a2-a1);
            else if(topstr=='*')num.push(a2*a1);
            else if(topstr=='/')num.push(a2/a1);
        }
        if(topstr>='0'&&topstr<='9')
        {
            a=a*10+(topstr-'0');
        }if(topstr=='.'){num.push(a);a=0;}
    }
    cout< 

        单调栈
         

        什么是单调栈
         

        单调栈不是一种新的栈结构，它在结构上仍然是一个普通的栈，它是栈的一种使用方式。
         

        单调栈内的元素是单调递增或者单调递减的，有单调递增栈和单调递减栈。例如，单调递减栈从栈顶到栈底是从小到大的顺序。当一个数入栈时，与栈顶比较，若比栈顶小，则入栈；若比栈顶大，则出栈，直到这个数能入栈为止。注意，每个数都一定入栈。
         

        [USACO09MAR]
         

        Look Up S
         

        题目描述
         

        Farmer John’s N (1 <= N <= 100,000) cows, conveniently numbered 1…N, are once again standing in a row. Cow i has height H_i (1 <= H_i <= 1,000,000).
         

        Each cow is looking to her left toward those with higher index numbers. We say that cow i ‘looks up’ to cow j if i < j and H_i < H_j. For each cow i, FJ would like to know the index of the first cow in line looked up to by cow i.
         

        Note: about 50% of the test data will have N <= 1,000.
         

        约翰的  
     
      
       
       
         N 
        
       
         ( 
        
       
         1 
        
       
         ≤ 
        
       
         N 
        
       
         ≤ 
        
       
         1 
        
        
        
          0 
         
        
          5 
         
        
       
         ) 
        
       
      
        N(1\le N\le10^5) 
       
      
    N(1≤N≤105) 头奶牛站成一排，奶牛  
     
      
       
       
         i 
        
       
      
        i 
       
      
    i 的身高是  
     
      
       
        
        
          H 
         
        
          i 
         
        
       
         ( 
        
       
         1 
        
       
         ≤ 
        
        
        
          H 
         
        
          i 
         
        
       
         ≤ 
        
       
         1 
        
        
        
          0 
         
        
          6 
         
        
       
         ) 
        
       
      
        H_i(1\le H_i\le10^6) 
       
      
    Hi​(1≤Hi​≤106)。现在，每只奶牛都在向右看齐。对于奶牛  
     
      
       
       
         i 
        
       
      
        i 
       
      
    i，如果奶牛  
     
      
       
       
         j 
        
       
      
        j 
       
      
    j 满足  
     
      
       
       
         i 
        
       
         < 
        
       
         j 
        
       
      
        i 

        Input
         

        输入格式
         

        1. * Line 1: A single integer: N
         

        * Lines 2…N+1: Line i+1 contains the single integer: H_i
         

        第  
     
      
       
       
         1 
        
       
      
        1 
       
      
    1 行输入  
     
      
       
       
         N 
        
       
      
        N 
       
      
    N，之后每行输入一个身高  
     
      
       
        
        
          H 
         
        
          i 
         
        
       
      
        H_i 
       
      
    Hi​。
         

        输出格式
         

        * Lines 1…N: Line i contains a single integer representing the smallest index of a cow up to which cow i looks. If no such cow exists, print 0.
         

        共  
     
      
       
       
         N 
        
       
      
        N 
       
      
    N 行，按顺序每行输出一只奶牛的最近仰望对象，如果没有仰望对象，输出  
     
      
       
       
         0 
        
       
      
        0 
       
      
    0。
         

        样例 #1
         

        样例输入 #1
         

        6 
3 
2 
6 
1 
1 
2

         

        样例输出 #1
         

        3 
3 
0 
6 
6 
0

         

        提示
         

        FJ has six cows of heights 3, 2, 6, 1, 1, and 2.
         

        Cows 1 and 2 both look up to cow 3; cows 4 and 5 both look up to cow 6; and cows 3 and 6 do not look up to any cow.
         

        【输入说明】 
     
      
       
       
         6 
        
       
      
        6 
       
      
    6 头奶牛的身高分别为 3,2,6,1,1,2。
         

        【输出说明】奶牛 #1,#2 仰望奶牛 #3，奶牛 #4,#5 仰望奶牛 #6，奶牛 #3 和 #6 没有仰望对象。
         

        【数据规模】
         

        对于  
     
      
       
       
         20 
        
       
         % 
        
       
      
        20\% 
       
      
    20% 的数据： 
     
      
       
       
         1 
        
       
         ≤ 
        
       
         N 
        
       
         ≤ 
        
       
         10 
        
       
      
        1\le N\le10 
       
      
    1≤N≤10；
         

        对于  
     
      
       
       
         50 
        
       
         % 
        
       
      
        50\% 
       
      
    50% 的数据： 
     
      
       
       
         1 
        
       
         ≤ 
        
       
         N 
        
       
         ≤ 
        
       
         1 
        
        
        
          0 
         
        
          3 
         
        
       
      
        1\le N\le10^3 
       
      
    1≤N≤103；
         

        对于  
     
      
       
       
         100 
        
       
         % 
        
       
      
        100\% 
       
      
    100% 的数据： 
     
      
       
       
         1 
        
       
         ≤ 
        
       
         N 
        
       
         ≤ 
        
       
         1 
        
        
        
          0 
         
        
          5 
         
        
       
         , 
        
       
         1 
        
       
         ≤ 
        
        
        
          H 
         
        
          i 
         
        
       
         ≤ 
        
       
         1 
        
        
        
          0 
         
        
          6 
         
        
       
      
        1\le N\le10^5,1\le H_i\le10^6 
       
      
    1≤N≤105,1≤Hi​≤106。
         

        思路：
         

        使用两个栈，一个存储奶牛的编号，一个存储奶牛的身高，如果身高比栈顶的大，则两个栈的栈顶元素均弹出，直到为空或身高不比栈顶大为止。最后把所有身高都输入完后，如果栈内还有元素，则他们是没有仰望对象的，即为0.
         

        #include
using namespace std;
const int N=1e5+5;
int a[N];
int main()
{
    int n,x;cin>>n;
    stacks;stackt;
    for(int i=0;i<=n;)
    {
        scanf("%d",&x);i++;
        while(!s.empty()&&x>s.top()&&!t.empty())
        {
            s.pop();
            a[t.top()]=i;
            t.pop();
        }
        if(s.empty()&&t.empty()){s.push(x);t.push(i);}
        if(!s.empty()&&x<=s.top()&&!t.empty()){s.push(x);t.push(i);}
        
    }
    while(!s.empty()&&!t.empty())
    {
        s.pop();
        a[t.top()]=0;
        t.pop();
    }
    for(int i=1;i<=n;i++)cout<

转载请注明来自码农世界，本文标题：《【蓝桥杯2025备赛】栈和单调栈》

百度分享代码，如果开启HTTPS请参考李洋个人博客
37815篇文章 站点 微博
每一天，每一秒，你所做的决定都会改变你的人生！

发表评论

快捷回复：

评论列表 （暂无评论，77人围观）参与讨论

还没有评论，来说两句吧...

Top