P8430 题解

前言

题目传送门！

更好的阅读体验？

比较妙的交互题。

思路

题意就是每次可以询问 \([l, r]\) 的括号子序列是否为合法，\((n-1)\) 次询问后，需要求出整个括号序列。

括号序列，自然想到栈。考虑每次进行一个 \([\text{top}, i]\) 的询问。如果是合法，那么 \(a_{\text{top}}=\text{LEFT}, a_i = \text{RIGHT}\)。

考虑将不确定的位置组成一个新的括号序列。这个序列有一个很强的特性：任意区间都不能组成合法匹配。

进行一个反证。

假设序列形如 \(\text{(S)}\) 的样子。若 \(\text{S}\) 的首位是右括号，必然可以和左边那个组成合法匹配，所以 \( \text{S}\) 的首位是左括号。同理 \(\text{S}\) 的末位是右括号。
\(\\\)
所以序列会进一步被固定成 \(\text{((S-2))}\)，\(\text{(((S-4)))}\)，以此类推，最后会组合成 \(\text{((((}\cdots\text{))))}\) 的形式，而这整个序列就是合法的，与我们强大的特性矛盾。寄！

综上，序列一定是形如 \(\text{)S(}\) 的形式的，类似于上方分析，整个序列可以被逐步扩大成 \(\text{))))}\cdots\text{((((}\) 的形式。

按照这个形式填充回原序列即可拿下。

代码

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int n, q; char a[N];
namespace Mutual {
	int ask(int l, int r)
	{
		cout << "? " << l << ' ' << r << endl;
		int tmp; cin >> tmp; return tmp;
	}
	void answer()
	{
		cout << "! ";
		for (int i = 1; i <= n; i++) cout << a[i];
		cout << endl;
	}
}; using namespace Mutual;
int stk[N], top;
int solve()
{
	int cnt = n;
	stk[++top] = 1; //现在是寻找合法子串 
	for (int i = 2; i <= n; i++)
	{
		if (top && ask(stk[top], i))
			a[stk[top]] = '(', a[i] = ')', cnt -= 2,
			top--; //匹配成功 
		else stk[++top] = i;
	}
	return cnt;
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> q;
	
	for (int i = 1; i <= n; i++) a[i] = '%';
	int cnt = solve();
	for (int i = 1, cur = 0; i <= n; i++)
		if (a[i] == '%')
		{
			cur++;
			if (cur <= cnt / 2) a[i] = ')'; else a[i] = '(';
		}
	answer();
	return 0;
}

希望能帮助到大家！