P8430

2021CHD · 2023-03-31 08:59:02 · 题解

蒟蒻第一篇题解。

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

题义简述

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

解题方法

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

对于一个括号序列，我们可以用 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;
}