本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
Problem - E1 - Codeforces
题目类型
#二分 #构造 #交互题
解题思路
二分定位右括号元素位置，构造查询字符串，按题意使用不超过 550 个查询找出序列 s，由于序列长度小于 1000，每次查询长度至少为 2 的序列子段
txt
t = s1)s1)s2)
f(t) = 6 => s1 = s2 = (
f(t) = 3 => s1 = (, s2 = )
f(t) = 1 => s1 = ), s2 = (
f(t) = 0 => s1 = s2 = )参考：Codeforces Round 1040 (Div. 1, Div. 2) Editorial - Codeforces
示例代码
python
def query(li):
print("?", len(li), *li, flush=True)
return II()
def helltractor():
for _ in range(II()):
n = II()
ans = [-1] * (n + 1)
p = 1
l, r = 2, n
while l <= r:
m = (l + r) >> 1
x = query(list(range(1, m + 1)))
if x > 0:
p = m
r = m - 1
else:
l = m + 1
for i in range(1, n + 1, 2):
if i + 1 > n:
break
res = query([i, p, i, p, i + 1, p])
if res == 6:
ans[i], ans[i + 1] = 0, 0
elif res == 3:
ans[i], ans[i + 1] = 0, 1
elif res == 1:
ans[i], ans[i + 1] = 1, 0
else:
ans[i], ans[i + 1] = 1, 1
i += 2
if n % 2:
ans[n] = 1 - query([n, p])
ans = ["(" if ans[i] == 0 else ")" for i in range(1, n + 1)]
print("! " + "".join(ans), flush=True)Problem - E2 - Codeforces
题目类型
#二分 #构造 #交互题
解题思路
二分定位右括号元素位置，构造查询字符串，按题意使用不超过 200 个查询找出序列 s，由于序列长度小于 1000，每次查询长度至少为 5 的序列子段
txt
为区分ti的贡献
t1 = s1))
假设s1 = (
f(t1) = 1 << 1
t2 = s2))s2))
同理假设s2 = (
f(t2) = 1 << 2
t8 = s8)) * (1 << 8)
同理假设s8 = (
f(t8) = 1 << 8
t = t1 + t2 + ... + t8
f(t) = f(t1) + f(t2) + ... + f(t8)参考：Codeforces Round 1040 (Div. 1, Div. 2) Editorial - Codeforces
示例代码
python
def query(li):
print("?", len(li), *li, flush=True)
return II()
def helltractor():
for _ in range(II()):
n = II()
ans = [''] * (n + 1)
p = 1
l, r = 2, n
while l <= r:
m = (l + r) >> 1
x = query(list(range(1, m + 1)))
if x > 0:
p = m
r = m - 1
else:
l = m + 1
for i in range(1, n + 1, 8):
q = []
for j in range(min(8, n - i + 1)):
for _ in range(1 << j):
q.extend([i + j, p, p])
x = query(q)
for j in range(min(8, n - i + 1)):
if x & (1 << j):
ans[i + j] = "("
else:
ans[i + j] = ")"
print("!", "".join(ans[1:]), flush=True)Problem - E3 - Codeforces
题目类型
#二分 #构造 #交互题
解题思路
二分定位右括号元素位置，构造查询字符串，按题意使用不超过 100 个查询找出序列 s，由于序列长度小于 1000，每次查询长度至少为 10 的序列子段
txt
t1 = s1))
假设s1 = (
f(t1) = count(s1) * (count(s1) + 1) // 2
t2 = s2)s2))
同理，假设s2 = (
f(t2) = count(s2) * (count(s2) + 1) // 2
为了区分t1和t2的贡献
f(tj) > sum(f(ti) for i in range(j))参考：Codeforces Round 1040 (Div. 1, Div. 2) Editorial - Codeforces
示例代码
python
def cal(n):
base = 1
ans = []
s = 0
while len(ans) < n:
if base * (base + 1) // 2 > s:
s += base * (base + 1) // 2
ans.append(base)
base += 1
return ans
def query(li):
print("?", len(li), *li, flush=True)
return II()
def helltractor():
for _ in range(II()):
n = II()
ans = [""] * (n + 1)
p = 1
l, r = 2, n
while l <= r:
m = (l + r) >> 1
x = query(list(range(1, m + 1)))
if x > 0:
p = m
r = m - 1
else:
l = m + 1
# s = cal(12)
s = [1, 2, 3, 5, 7, 10, 15, 21, 30, 43, 61, 87] # 每个位置用多少次
t = [x * (x + 1) // 2 for x in s] # 每个位置最多贡献多少有效匹配
for i in range(1, n + 1, 12):
q = []
for j in range(min(12, n - i + 1)):
for _ in range(s[j]):
q.extend([i + j, p])
q.append(p)
x = query(q)
for j in range(min(12, n - i + 1) - 1, -1, -1):
if x >= t[j]:
ans[i + j] = "("
x -= t[j]
else:
ans[i + j] = ")"
print("!", "".join(ans[1:]), flush=True)