Comet OJ 热身赛-principal

这题的话，我们分析一下，入栈的操作是：

栈空
栈顶元素和当前操作元素不属于同一类括号
栈顶元素和当前操作元素属于同一类括号，但是并不是左括号在前，右括号在后

上面三个条件有任意一个满足都应该入栈，如果三个都不满足，那就弹出栈顶元素，因为这时肯定是匹配的括号。

我们不必考虑栈内究竟是什么情况，我们要考虑的是，每个对应的元素，进行操作之后，栈顶的元素是谁，我们用序号入栈，代替原本的元素。

我们可以知道如果第l个和第r个是合法的，那么第l+1到第r-1也一定是合法的，所以他们就可以相互抵消，那么此时我们之前访问到l的时候，它的栈顶元素和我们抵消之后的栈顶元素师相同的。

因为中间的都消消乐了，所以如果ans[l-1]=ans[r]，就输出也yes。它们两个表示的都是，对下标元素进行操作之后的栈顶元素。我们不能对比l，因为如果l入栈，这时ans[l]里面存的是其它值。

#include <stdio.h>

#include <string.h>

const int maxn=1e6+10;

int a[maxn],stack[maxn],ans[maxn];

int main()

{

	int top=0,l,r,n,m,q;

	memset(ans,0,sizeof(ans));

	memset(stack,0,sizeof(stack));

	scanf("%d%d%d",&n,&m,&q);

	for (int i=1;i<=n;i++)

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

	for (int i=1;i<=n;i++) {

		if (!top||a[stack[top]]/2!=a[i]/2||a[stack[top]]+1!=a[i])

			stack[++top]=i;

		else

			--top;

		ans[i]=stack[top];

	}

	while (q--) {

		scanf("%d%d",&l,&r);

		if (ans[l-1]==ans[r])

			printf("Yes\n");

		else

			printf("No\n");

	}

	return 0;

}

巴特西

Comet OJ 热身赛-principal

最新文章

热门文章