非常好玩的一道题！
首先不难想到首先要找到一对括号，然后再次基础上询问其它的。简单拆分一下询问次数，$550 = 2 \times 20 + 500 + \text{eps}$，发现在找到括号后需要询问一次处理两个括号。至于为什么是 $2 \times 20$，原因便是在 $[l,r]$ 中即使有左右括号，它可能以 $\texttt{()}$ 或 $\texttt{)(}$ 的形式出现，因此需要正反各询问一次。
接下来考虑如何一次询问处理两个括号。其实方法很多，适合手玩，用上 substring 这个条件，尽量构造不对称括号序列即可。我构造的是 $\texttt{()??()}$，有以下几种情况：
设 $L,R$ 为二分找到的左/右括号位置，以第一个为例子，查询的写法为 query ({L,L,x,y,L,R}。注意，如果剩下未确定的数量是奇数，需要特殊考虑。
询问次数变为 $200$ 以内，需要一次至少测 $6$ 个。
如果接着从上一节的询问出发，直接赋值询问序列，会发现情况并不会显著增长，原因就是受到相互影响。所以进一步思考如何才能独立考虑。
尝试构造 $\texttt{(?((?((?(…}$ 的序列。具体来说，用二进制数的思想，第 $i$ 个待检测位置出现 $2^{i - 1}$ 次，即 $\texttt{(x((y((y((z((z((z((z(…}$。得到答案后，从低往高第 $i$ 位为 $1$，则说明第 $i$ 个待检测的位置为 $\texttt{)}$，否则为 $\texttt{(}$。当然，若剩余待检测位置的数量不足，直接用 $L$ 补齐即可，处理的时候特判。
最后检验一下合法性。若一次检测 $x$ 个，询问的长度为 $3(2^0 + 2^1 + \cdots + 2^{x - 1}) = 3(2^x - 1)$。由于长度不能超过 $1000$，因此 $x_{\max} = 8$，可以通过此题。
询问次数变为 $100$ 以内，需要一次至少测 $13$ 个。
接着上一节的想法，尝试构造互不影响的序列。尝试构造序列 $\texttt{(x((y(y((…}$，组内用 $\texttt{(}$ 分隔，组间用 $\texttt{((}$ 分隔。设第 $i$ 个待检测的位置出现 $dig_i$ 次，则对答案的贡献为 $sum_i = \frac{(dig_i + 1)dig_i}{2}$。进一步来说，只要满足下式条件即可：
其中 $I = \{1,2,\cdots,|sum|\}$，$J \subseteq I \setminus \{i\}$，且满足 $\forall j,k \in J, j \neq k$。
容易发现，当 $2sum_{i - 1} \le sum_i$ 时可以满足条件，通过暴力打表发现，最大的符合题目限制的 $dig$ 集合为 $\{1,2,4,6,9,13,19,28,40,57,81,115\}$。但是此时 $|dig| = 12$，按照原来的二分方式会超过限制。仔细思考可以发现原来的二分每一次的 check 需要花费 $2$ 次询问，但是我们只想要知道序列中是否存在左右括号以及括号的方向。因此，当方向未确定时，我们将询问的序列正反拼接，得到有无左右括号的信息。一旦在某次询问中得知存在左右括号，直接花费额外的一次询问定方向。在得知方向后，每次二分只需要一次询问去缩小范围。二分的询问次数的上确界为 $\lceil{\log (10^3)} + 1 \rceil = 11$ 次，总询问次数的上确界为 $11 + \lceil \frac{10^3}{12} \rceil = 11 + 84 = 95$ 次，同时单次询问长度不会超过 $1000$，已经可以通过此题。
但能否进一步优化呢？按照之前的互不影响的条件去构造基，可以尝试写一个 $O(k^2 2^k)$ 的状压构造并手动调整，在此不过多赘述，直接给出一组长度为 $13$ 的可行构造：$\{1,2,4,5,8,11,16,23,33,57,74,105,150\}$，可以证明不存在比 $13$ 更大且满足条件限制的基。此时总询问次数的上确界可以降为 $11 + \lceil \frac{10^3}{13} \rceil = 11 + 77 = 88$ 次，理论上应该已经达到最优解了。
完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| #include <bits/stdc++.h>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define pii pair <int,int>
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
const int UP = 13;
inline int read ();
int dig[] = {1,2,4,5,8,11,16,23,33,57,74,105,150};
int query (vector <int> lst)
{
printf ("? %d ",(int)lst.size ());
for (auto v : lst) printf ("%d ",v);
puts ("");fflush (stdout);
return read ();
}
void solve ()
{
int n = read ();
int l = 1,r = n,L = -1,R = -1,sure = -1;
vector <char> ans (n + 1);
auto check = [&] (int l,int r) -> bool
{
vector <int> lst;
for (int i = l;i <= r;++i) lst.push_back (i);
if (sure == 0) return query (lst);
else if (sure == 1)
{
reverse (lst.begin (),lst.end ());
return query (lst);
}
for (int i = r;i >= l;--i) lst.push_back (i);
if (!query (lst)) return false;
for (int i = l;i <= r;++i) lst.pop_back ();
if (query (lst)) sure = 0;
else sure = 1;
return true;
};
while (1)
{
if (l + 1 == r)
{
if (sure == -1)
{
if (query ({l,r})) L = l,R = r;
else L = r,R = l;
}
else if (sure == 0) L = l,R = r;
else L = r,R = l;
break;
}
int mid = (l + r) >> 1;
if (check (l,mid)) r = mid;
else l = mid;
}
ans[L] = '(';ans[R] = ')';
vector <int> p;
for (int i = 1;i <= n;++i)
if (i != L && i != R) p.push_back (i);
int pos = 0,sz = p.size ();
while (pos < sz)
{
vector <int> nw (UP,L);
for (int i = 0;i < UP;++i)
if (pos + i < sz) nw[i] = p[pos + i];
vector <int> lst;
for (int i = 0;i < UP;++i)
{
for (int j = 0;j < dig[i];++j) lst.push_back (L),lst.push_back (nw[i]);
lst.push_back (L);
}
int res = query (lst);
for (int i = UP - 1;~i;--i)
{
if (nw[i] == L) continue;
if (res >= (1 + dig[i]) * dig[i] / 2) ans[nw[i]] = ')',res -= (1 + dig[i]) * dig[i] / 2;
else ans[nw[i]] = '(';
}
pos += UP;
}
printf ("! ");
for (int i = 1;i <= n;++i) printf ("%c",ans[i]);
puts ("");fflush (stdout);
}
int main ()
{
int t = read ();
while (t--) solve ();
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
