自动搬运

查看原文

来自洛谷，原作者为

	2021CHD 这个家伙很懒，什么也没有留下？

搬运于2025-08-24 22:38:58，当前版本为作者最后更新于2023-03-31 08:59:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻第一篇题解。

自己不会做，看了官方题解才做出来的。

题义简述

• 这是一道交互题。
• 有一个长度为 $n$ 的括号序列，$n$ 为偶数，其中一半是左括号，一半是右括号。
• 你能进行 $Q$ 次询问，每次询问给出一个 $l$ 和 $r$，询问 $l$ 到 $r$ 间的括号序列是否合法。
• 目标是求出这个括号序列。
• $n\leqslant 10^{5}$，$n-1\leqslant Q$。

解题方法

拿到这样一道题，没什么头绪，于是可以反过来思考。

对于一个括号序列，我们可以用 $n-1$ 个什么来区别它和其他括号序列呢？

结合本题要求线性（或稍劣）的时间，我们想到了线性的数据结构。

再结合括号序列，我们想到了用栈判定括号序列的合法性。

那么，我们就考虑用栈来重现这个括号序列。

如果不会用栈判定括号序列的合法性，请移步至表达式括号匹配。

从左到右依次入栈，入栈后，当栈内至少有两个元素时，询问栈顶的两个是否合法。

合法即确定两个位置分别为(和)，弹出这对括号。

如果最后栈不为空（整个序列不合法），则左边一半为)，右边一半为(。

考虑这样做的正确性。

如果栈顶是(和)，那么它们其中的所有括号都被弹走了，也就是说，这是一对括号包含一个合法的括号序列（或者这是一对相邻的括号），显然合法。

如果栈顶不是(和)，显然不合法。

如果最后栈不为空，因为左括号和右括号一样多，而弹出的括号都是成对的，所以最后剩下的左括号和右括号也一样多，又因为它们都还在栈中（没有匹配的括号），则只能是左边一半为右括号，右边一半为左括号了。

除了第一个元素以外，每个元素入栈时至多询问 $1$ 次，所以至多只会询问 $n-1$ 次。

时间复杂度：$\Theta(n)$。

参考代码

#include<cstdio>
#include<iostream>
using namespace std;
int n,f[100010],top,i,s;\\f数组为栈
char ans[100010];
main()
{
	cin>>n>>i;\\不需要Q
	for(i=1;i<=n;i++)
	{
		top++;
		f[top]=i;
		if(top>1)
		{
			cout<<"? "<<f[top-1]<<" "<<f[top]<<endl;
			cin>>s;
			if(s==1)
			{
				ans[f[top-1]]='(';
				ans[f[top]]=')';
				top=top-2;
			}
		}
	}
	for(i=1;i*2<=top;i++)
	ans[f[i]]=')';
	for(;i<=top;i++)
	ans[f[i]]='(';
	cout<<"! "<<ans+1<<endl;
}