题解：P10649 [ROI 2017] 四轴飞行器编程 (Day 1)

· · 题解

非常简单的交互题。题目允许两倍的询问次数纯属多余。接下来介绍一下怎么只询问至多 n-1 次得出答案。

首先，观察到序列开始的第一个字符肯定是 (，不然就不合法了。

那第二个字符是什么呢？我们发现如果第二个是 ( 的话，查询 [1,2] 就会返回 No，否则就是 Yes。

以此类推，第三、第四或第 i 个呢？此时，若 [1,i-1] 本身是一个合法的串，那么直接就知道他是 ( 了，继续处理下一位即可。

否则，我们使用判断第二个字符同样的方法。只是此时查询区间的左端点变成了最右边尚未匹配的 (，查询这个区间是否合法。若合法则为 )，否则就是 (。

接下来只需要思考如何维护最右边的未匹配的 ( 了。很明显可以考虑使用栈，每次配对后弹出栈顶，新加了 ( 就推入栈。若栈没有任何元素，则代表此时左边的已经全部配对了。

接下来就能轻松的写出代码了！

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

char ans[50005];
bool query(int l,int r){
    cout<<"? "<<l<<" "<<r<<endl;
    string s;
    cin>>s;
    return s=="Yes";
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    stack<int> s;
    int n;
    cin>>n;
    for (int i=1;i<=n;i++){
        if (s.size()==0){
            ans[i]='(';
            s.push(i);
        }
        else{
            int st=s.top();
            if (query(st,i)){
                ans[i]=')';
                s.pop();
            }
            else{
                s.push(i);
                ans[i]='(';
            }
        }
    }
    cout<<"! ";
    for (int i=1;i<=n;i++) cout<<ans[i];
}