The basic characteristics of stack will not be repeated here. Focus on stack related applications and related exercises.

Stack and Cartland sequence

I will introduce the catteland sequence in detail in section 0x36.

[example] in and out stack sequence problem (AcWing130)

Title Link
Idea: after careful observation, we will find that the in and out stack sequence conforms to the characteristics of Cartland sequence, which can be calculated by using the general term formula (which will be deduced in detail in section 0x36). The general term formula is N N The number of cartlands in item N is: C 2 N N N + 1 \frac{C_{2N}^N}{N + 1} N+1C2NN​​. The core of this problem is to calculate the Cartland number, which is solved by qualitative factor decomposition and high-precision multiplication.

AC Code:

#include<bits/stdc++.h>
#define N 120005 

using namespace std;

int n;
int p[N],vis[N];
int power[N];

void prime(){
    for(int i = 2;i <= 2 * n;i ++){
        if(!vis[i]) 
            p[++p[0]] = i;
        for(int j = 1;j <= p[0] && p[j] * i <= 2 * n;j ++){
            vis[i * p[j]] = 1;
            if(i % p[j] == 0) break;
        }
    }
}

int getP(int x,int pp){
    int res = 0;
    while(x){
        res += x / pp;
        x /= pp;
    }
    return res;
}

void mul(vector<int>& a,int b){
    int c = 0;
    for(int i = 0;i < a.size();i ++){
        a[i] = a[i] * b + c;
        c = a[i] / 10000;
        a[i] %= 10000;
    }
    while(c){
        a.push_back(c % 10000);
        c /= 10000;
    }
}

void out(vector<int>& ans){
    printf("%d",ans.back());
    for(int i = ans.size() - 2;i >= 0;i --){
        printf("%04d",ans[i]);
    }
}

void solve(){
    cin >> n;
    prime();
    
    for(int i = 1;i <= p[0];i ++){
        power[p[i]] = getP(2 * n,p[i]) - 2 * getP(n,p[i]);
    }
    
    int tmp = n + 1;
    for(int i = 1;i <= p[0] && p[i] <= n + 1;i ++){
        while(tmp % p[i] == 0){
            power[p[i]] --;
            tmp /= p[i];
        }
    }
    
    vector<int> ans;
    ans.push_back(1);
    
    for(int i = 1;i <= p[0];i ++){
        for(int h = 0;h < power[p[i]];h ++){
            mul(ans,p[i]);
        }
    }
    
    out(ans);
    
    cout << endl; 
}

int main(){
    solve();
    return 0;
}

Expression calculation

Expressions generally have prefix, infix and suffix expressions. Here we mainly discuss the calculation method of infix expressions.
We can use two stacks, a number stack and an operator stack. The steps are as follows:
Scan each character in the expression one by one:
(1) If you encounter a number, press it into the number stack
(2) If you encounter an open bracket, press the open bracket into the operator stack
(3) If you encounter a right bracket, keep taking out one operator at the top of the operation stack and two operators at the top of the digital stack for operation, and press the operation result into the digital stack until the top of the operator stack is an left bracket. Finally, put the left bracket out of the stack.
(4) If you encounter an operator, as long as the priority of the top of the operator stack is not lower than the currently scanned operator, you will constantly take out the top of the stack operator and two numbers at the top of the digital stack for operation, and press the operation result into the digital stack. Finally, push the currently scanned operator into the operator stack.
Tip: we can add a pair of parentheses to the solved expression, so that the element in the final number stack is the result of the expression.

[exercise] expression calculation 4 (AcWing151)

Idea: the above steps have been very detailed. It should be noted that there may be redundant left and right parentheses here. We only need to add left parentheses with the same length as the expression to the left of the expression. Think about why?

AC Code:

#include<bits/stdc++.h>

using namespace std;


stack<int> nums;
stack<char> ops;

void calc(){
    char op = ops.top();ops.pop();
    int b = nums.top();nums.pop();
    int a = nums.top();nums.pop();

    if(op == '+') nums.push(a + b);
    else if(op == '-') nums.push(a - b);
    else if(op == '*') nums.push(a * b);
    else if(op == '/') nums.push(a / b);
    else if(op == '^'){
        int res = 1;
        for(int i = 1;i <= b;i ++)
            res *= a;
        nums.push(res);
    }
}

void solve(){
    string s;
    cin >> s;
    string left;
    for(int i = 0;i <= s.size();i ++) left += '(';
    s = left + s + ')';

    for(int i = 0;i < s.size();i ++){
        if(s[i] >= '0' && s[i] <= '9'){
            int num = 0;
            int j = i;
            while(s[j] >= '0' && s[j] <= '9'){
                num = num * 10 + s[j] - '0';
                j ++;
            }
            nums.push(num);
            i = j - 1;
        }
        else{
            char c = s[i];
            if(c == '-' || c == '+'){
                if(c == '-' && i && !(s[i - 1] >= '0' && s[i - 1] <= '9' || s[i - 1] == ')')){
                    nums.push(0);
                }
                while(ops.top() != '(') calc();
                ops.push(c);
            }
            else if(c == '*' || c == '/'){
                while(ops.top() != '(' && ops.top() != '+' && ops.top() != '-') calc();
                ops.push(c);
            }
            else if(c == '^'){
                while(ops.top() == '^') calc();
                ops.push(c);
            }
            else if(c == '(') ops.push(c);
            else{
                while(ops.top() != '(') calc();
                ops.pop();
            }
        }
    }

    cout << nums.top() << endl;
}

int main(){
    solve();
    return 0;
}

Monotone stack

Monotone stack is very useful in dealing with some problems. We use two topics to experience the application of a single stack adjustment.

[example] the largest rectangle in the histogram (AcWing131)

Title Link
Idea: This is a classic example of monotonous stack. Let's first think about such a problem. If the height of a rectangle increases strictly monotonically, how should we calculate the maximum rectangular area? (as shown below)

We just need to consider taking the height of each rectangle as the height of the final rectangle, and then extend it to the right (because the left cannot be extended) to update the answer.

If the height of the next rectangle is less than the height of the current rectangle, since the height of the largest rectangle composed of the next rectangle and the previous rectangle must not exceed the height of the next rectangle itself, after considering the rectangular area of the above four cases, the partial rectangles shown in the figure below are no longer useful for updating the answer.

Then we can delete this part of the rectangle and replace it with a rectangle with the same height as the last rectangle.

When deleting, we need to update the answer with the rectangle to be deleted.
Tip: at the end of the rectangle height sequence, we add a virtual rectangle with a height less than the height of all rectangles, so that we don't need to empty the stack again!

AC Code:

#include<bits/stdc++.h>
#define N 100005
#define LL long long 
using namespace std;

int h[N];
int top,stk[N];
int w[N];
int n;

void solve(){
    for(int i = 1;i <= n;i ++)
        cin >> h[i];
    
    LL ans = 0;
    h[n + 1] = 0;
    for(int i = 1;i <= n + 1;i ++){
        if(h[i] >= stk[top]){
            stk[++ top] = h[i];
            w[top] = 1;
        }   
        else{
            int width = 0;
            while(top && stk[top] >= h[i]){
                width += w[top];
                ans = max(ans,1LL * width * stk[top]);
                top --;
            }
            stk[++ top] = h[i];
            w[top] = width + 1;
        }
    }
    
    cout << ans << endl;
}

int main(){
    while(cin >> n && n){
        solve();
    }
    return 0;
}

[practice] city game (AcWing152)

Title Link
Idea: we can preprocess the continuous columns ending at each position F F The length of F, and then for each line, it is transformed into the problem of the previous question. Each line can be done once using the monotone stack!

AC Code:

#include<bits/stdc++.h>

using namespace std;

const int N = 1005;

char a[N][N];
int n,m;
int s[N][N];
int stk[N],w[N];
int top;

void solve(){
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            cin >> a[i][j];
    
    for(int j = 1;j <= m;j ++){
        for(int i = 1;i <= n;i ++)
            if(a[i][j] == 'R')
                s[i][j] = 0;
            else s[i][j] = s[i - 1][j] + 1;
    }
    
    int ans = 0;
    for(int i = 1;i <= n;i ++){
        top = 0;
        s[i][m + 1] = 0;
        for(int j = 1;j <= m + 1;j ++){
            if(s[i][j] > stk[top]){
                stk[++ top] = s[i][j],w[top] = 1;
            }
            else{
                int width = 0;
                while(top && s[i][j] <= stk[top]){
                    width += w[top];
                    ans = max(ans,width * stk[top]);
                    top --;
                }
                stk[++ top] = s[i][j],w[top] = width + 1;
            }
        }
    }
    
    cout << ans * 3 << endl;
}

int main(){
    solve();
    return 0;
}