牛客国庆集训派对Day1：J：Princess Principal（栈模拟求括号匹配）

题目描述

阿尔比恩王国（the Albion Kingdom）潜伏着一群代号“白鸽队（Team White Pigeon）”的间谍。在没有任务的时候，她们会进行各种各样的训练，比如快速判断一个文档有没有语法错误，这有助于她们鉴别写文档的人受教育程度。
这次用于训练的是一个含有n个括号的文档。括号一共有m种，每种括号都有左括号和右括号两种形式。我们定义用如下的方式定义一个合法的文档:
1.一个空的字符串是一个合法的文档。
2.如果A,B都是合法的文档，那么AB也是合法的文档。
3.如果S是合法的文档，那么aSb也是合法的文档，其中a,b是同一种括号，并且a是左括号，b是右括号。
现在给出q个询问，每次询问只考虑文档第l至r个字符的情况下，文档是不是合法的。

输入描述:

第一行两个整数n,m,q(1 ≤ n,m,q ≤ 10

⁶

)。
第二行有n个空格隔开的整数x，第i个整数x

(0 ≤ x

 < m*2)代表文档中的第i个字符是第

$\lfloor \frac{x}{2} \rfloor$

种括号。另外，如果x

是偶数，它代表一个左括号，否则它代表一个右括号。
接下来q行，每行两个空格隔开的整数l,r(1 ≤ l ≤ r ≤ n)，代表询问第l至r个字符构成的字符串是否是一个合法的文档。

输出描述:

输出共q行，如果询问的字符串是一个合法的文档，输出"Yes",否则输出"No"。

输入例子:

6 4 3

0 2 3 1 4 7

1 4

1 5

5 6

输出例子:

Yes

No

No

-->

示例1

输入

复制

6 4 3

0 2 3 1 4 7

1 4

1 5

5 6

输出

复制

Yes

No

No

题意：就是多次问区间，询问这个区间是否是一个合法的括号序列。

思路：应该做法是蛮多的，我是用栈来模拟的。模拟栈是常规操作，新加入的括号x如果能匹配栈顶y，则弹出栈顶y，是否加入栈x。然后记录每个x加入后的栈顶编号L，那么如果一个区间[l,r]是合法的，当且当L[l-1]==L[r]，因为这种情况说明了两点：

1，[l,r]这些括号没有去匹配[1,l-1]的任何括号，即从l开始，模拟栈的过程，没有弹出原来的部分；

2，加入栈的全被弹出了；

这说明[l,r]的括号自己和自己匹配完全了。所以这个算法是ok的。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

int a[maxn],q[maxn],L[maxn],top,N,M,Q;

int main(){

    scanf("%d%d%d",&N,&M,&Q);

    rep(i,,N) scanf("%d",&a[i]);

    rep(i,,N) {

        if(!top) q[++top]=i;

        else {

            if(a[i]/==a[q[top]]/&&a[i]==a[q[top]]+) top--;

            else q[++top]=i;

        }

        L[i]=q[top];

    }

    rep(i,,Q){

        int x,y;

        scanf("%d%d",&x,&y);

        if((y-x)&){

            if(L[y]==L[x-]) puts("Yes");

            else puts("No");

        }

        else puts("No");

    }

    return ;

}

巴特西

牛客国庆集训派对Day1：J：Princess Principal（栈模拟求括号匹配）

输入描述:

输出描述:

输入例子:

输出例子:

输入

输出

最新文章

热门文章