P8430 [COI 2020] Zagrade

题目背景

本题为交互题。

众所周知，中央情报局的工作是收集，处理和分析国家安全信息。现在他们拥有了大量的计算机密码，并且正在开发一些相当复杂的工具，来破坏受密码保护的系统。

现在，您的任务是破坏中央情报局服务器的安全性。自然，他们很清楚人们在输入密码的时候通常会输入什么东西，因此尝试输入 123456 , 1q2w3e4r 或 Welcome 肯定是没有用的。幸运的是，我们发现了某些可能对您有用的信息。

题目描述

现在已知中央情报局服务器的主密码由 $n$ 个字符（$n$ 为偶数）构成，其中一半是左括号，一半是右括号。一些记性不好的服务器管理员会忘记这个主密码，所以服务器提供了找回密码的工具。管理员最多可以使用 $Q$ 次这个工具，每次使用时都会询问这个密码 $l$ 到 $r$ 位的括号串是否合法。

对于一个括号串合法的定义：

• () 是一个合法的括号串。
• 若 A 是一个合法的括号串，那么 (A) 也是一个合法的括号串。
• 若 A 与 B 都是合法的括号串，那么 AB 也是合法的括号串。

现在你需要写出一个程序来模拟管理员找回密码的过程。

在进行交互之前，您的程序应该从输入中读取偶数 $n$ 和整数 $Q$ ，这两个数字的含义见题目描述。

之后，您的程序可以通过向标准输出输出来发送查询请求。每个查询必须在单独的行中打印，并采用 ? a b，其中 $1\le a\le b\le n$。每个查询之后，您的程序应清空缓冲区并从标准输入中读取答案。

当你推理出密码时，请在标准输出中输出： ! x1 x2 x3 …… xn 的形式，之后你的程序应清空缓冲区并正常终止程序运行。

输入格式

第一行两个整数 $n,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\le n\le 1000$，$Q=\frac{n^2}{4}$，保证整个括号序列合法。
• Subtask 2（7 pts）：$1\le n\le 1000$，$Q=\frac{n^2}{4}$。
• Subtask 3（57 pts）：$1\le n\le 100000$，$Q=n-1$，保证整个括号序列合法。
• Subtask 4（12 pts）：$1\le n\le 100000$，$Q=n-1$。

对于 $100\%$ 的数据，$1\le n\le 100000$，$n-1\le Q$。

说明

翻译自 Croatian Olympiad in Informatics 2020 D Zagrade。

C++实现

#include<cstdio>
#include<iostream>
using namespace std;
int n,f[100010],top,i,s;
char ans[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考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容