A1051.md

A1051 Pop Sequence

1.题意理解

本题考查经典数据结构问题：出栈序列，即将1~n按顺序压入栈中，问哪些query是合法的出栈序列。

2.题目分析

最简单的方法是直接模拟，先把1~n按顺序进栈，每进栈一个数，都把当前栈顶元素与query当前元素进行比较，只要相等就一直pop（模拟出栈），最后计数出栈元素的个数是否为n即可。

3.参考代码

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

const int MAX = 1024;
int m, n, k;

int main()
{
    int num;
    scanf("%d %d %d", &m, &n, &k);
    for (int i = 0; i < k; i++)
    {
        bool flag = false;
        vector<int> seq;
        stack<int> s;
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &num);
            seq.push_back(num);
        }

        int cur = 0;
        for (int j = 1; j <= n; j++)
        {
            s.push(j);
            if (s.size() > m)
                break;
            while (!s.empty() && s.top() == seq[cur])
            {
                s.pop();
                cur++;
            }
        }
        if (cur == n)
            flag = true;
        if (flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    // system("pause");
    return 0;
}

此处可以积累一个重要结论： 出栈序列中，每个元素后面所有比它小的元素组成一个递减序列 根据这一性质，结合数学推导，可得到n个元素合法出栈序列计算公式（证明略去）： $$f(n)=\frac{C^n_{2n}}{n+1}$$