P8430 [COI 2020] Zagrade
题目背景
本题为交互题。
众所周知，中央情报局的工作是收集，处理和分析国家安全信息。现在他们拥有了大量的计算机密码，并且正在开发一些相当复杂的工具，来破坏受密码保护的系统。
现在，您的任务是破坏中央情报局服务器的安全性。自然，他们很清楚人们在输入密码的时候通常会输入什么东西，因此尝试输入123456,1q2w3e4r或Welcome肯定是没有用的。幸运的是，我们发现了某些可能对您有用的信息。
题目描述
现在已知中央情报局服务器的主密码由n nn个字符（n nn为偶数）构成，其中一半是左括号，一半是右括号。一些记性不好的服务器管理员会忘记这个主密码，所以服务器提供了找回密码的工具。管理员最多可以使用Q QQ次这个工具，每次使用时都会询问这个密码l ll到r rr位的括号串是否合法。
对于一个括号串合法的定义：
()是一个合法的括号串。- 若
A是一个合法的括号串，那么(A)也是一个合法的括号串。 - 若
A与B都是合法的括号串，那么AB也是合法的括号串。
现在你需要写出一个程序来模拟管理员找回密码的过程。
在进行交互之前，您的程序应该从输入中读取偶数n nn和整数Q QQ，这两个数字的含义见题目描述。
之后，您的程序可以通过向标准输出输出来发送查询请求。每个查询必须在单独的行中打印，并采用? a b，其中1 ≤ a ≤ b ≤ n 1 \leq a \leq b \leq n1≤a≤b≤n。每个查询之后，您的程序应清空缓冲区并从标准输入中读取答案。
当你推理出密码时，请在标准输出中输出：! x1 x2 x3 …… xn的形式，之后你的程序应清空缓冲区并正常终止程序运行。
输入格式
第一行两个整数n , Q n,Qn,Q。
接下来若干行，每行对于每个查询给出答案。
输出格式
若干行，表示查询。
最后一行表示最后得出的答案。
输入输出样例 #1
输入 #1
6 9 1 0 0 1 1输出 #1
? 1 6 ? 1 2 ? 2 4 ? 2 5 ? 3 4 ! ((()))说明/提示
样例解释
? 1 6对应的是整个串，当然是合法的。? 1 2对应的是((不合法。? 2 4对应的是(()不合法。? 2 5对应的是(())合法。? 3 4对应的是()合法。
数据规模与约定
本题采用捆绑测试
- Subtask 1（14 pts）：1 ≤ n ≤ 1000 1\leq n\leq 10001≤n≤1000，Q = n 2 4 Q=\frac{n^2}{4}Q=4n2，保证整个括号序列合法。
- Subtask 2（7 pts）：1 ≤ n ≤ 1000 1\leq n\leq 10001≤n≤1000，Q = n 2 4 Q=\frac{n^2}{4}Q=4n2。
- Subtask 3（57 pts）：1 ≤ n ≤ 100000 1\leq n\leq 1000001≤n≤100000，Q = n − 1 Q=n-1Q=n−1，保证整个括号序列合法。
- Subtask 4（12 pts）：1 ≤ n ≤ 100000 1\leq n\leq 1000001≤n≤100000，Q = n − 1 Q=n-1Q=n−1。
对于100 % 100\%100%的数据，1 ≤ n ≤ 100000 1\leq n\leq 1000001≤n≤100000，n − 1 ≤ Q n-1\leq Qn−1≤Q。
说明
翻译自 Croatian Olympiad in Informatics 2020 D Zagrade。
C++实现
#include<cstdio>#include<iostream>usingnamespacestd;intn,f[100010],top,i,s;charans[100010];main(){cin>>n>>i;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;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
