← 返回题目列表

Codeforces · 2210/E

E. 二进制字符串很简单?

中文机器翻译题面 查看原题

这是一个交互问题。

给你一个未知的二进制字符串$$$s$$$$$$^{\text{*}}$$$,长度为$$$n$$$。函数 $$$f(l, r)$$$ 定义为通过以下操作形成的数组 $$$a$$$ 中不同元素的数量:

  • 设 $$$S$$$ 为子串 $$$s_l s_{l+1} \ldots s_r$$$。设 $$$m$$$ 为子字符串的长度。
  • 我们从一个空数组 $$$a$$$ 开始。
  • 对于$$$S$$$的第$$$i$$$第$$$(0 \le i \lt m)$$$左循环旋转$$$^{\text{†}}$$$,我们将反转次数$$$^{\text{‡}}$$$表示为$$$x_{i}$$$。
  • 对于每个$$$i$$$,使得$$$0 \le i \lt m$$$,将$$$x_{i} \mbox{ mod } m$$$附加到数组$$$a$$$,其中$$$u \mbox{ mod } v$$$表示$$$u$$$除以$$$v$$$的余数。

要确定 $$$s$$$,您可以提出一些问题。在每个问题中,您可以选择 $$$2$$$ 整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) 并获取 $$$f(l, r)$$$ 的值。每个查询都会产生 $$$\dfrac{n}{r-l+1}$$$ 的成本。请注意,成本不一定必须是整数。

您必须确定隐藏的二进制字符串,同时将查询的总成本保持在 $$$\mathbf{max(30,3\cdot n)}$$$ 以内。您最多可以进行 $$$\mathbf{2}$$$ 猜测。

$$$^{\text{*}}$$$二进制字符串仅包含字符 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$。

$$$^{\text{†}}$$$设一个二进制字符串$$$s \; = \; s_{1}s_{2}\cdots s_{n}$$$。 $$$s$$$ 的第 $$$k$$$ 左循环定义为 $$$t_{k} \; = \; s_{k+1}s_{k+2}\cdots s_{n}s_{1}s_{2}\cdots s_{k}$$$。

$$$^{\text{‡}}$$$设字符串$$$s \; = \; s_{1}s_{2}\cdots s_{n}$$$。 $$$s$$$ 的反转次数定义为索引对的数量 $$$i,j \; (1 \le i \lt j \le n)$$$,使得 $$$s_{i} \gt s_{j}$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3000$$$) — 未知字符串 $$$s$$$ 的长度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。

互动

要提出问题,请按以下格式输出一行(不带引号)

  • "$$$\texttt{? l r}$$$" ($$$1 \leq l \leq r \leq n$$$)
陪审团将返回一个整数$$$f(l, r)$$$。

猜测字符串$$$s$$$($$$s$$$的长度必须为$$$n$$$),按以下格式输出单行(不带引号)

  • “$$$\texttt{!s}$$$”
评审团将返回 1 如果猜测正确或 0 如果猜测不正确。

猜测字符串不算作查询。

之后,如果您的字符串正确,则继续下一个测试用例,或者如果它是最后一个测试用例则终止程序。

交互器是 不 自适应,意味着答案在参与者提出问题之前就已知,并且不依赖于参与者提出的问题。

打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。

如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。

黑客

要进行破解,请使用以下格式。

第一行应包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。

每个测试用例的第一行应包含$$$n$$$ ($$$2 \le n \le 3000$$$),$$$s$$$ 的长度。

每个测试用例的第二行应包含 $$$s$$$,一个长度为 $$$n$$$ 的二进制字符串。

所有测试用例的 $$$n$$$ 总和不应超过 $$$3000$$$。

$$$^{\text{*}}$$$要刷新,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • sys.stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

示例

输入
复制

3
5

1

1

1

1
3

3

0

1
8

0

1

输出
复制


? 1 5

? 2 5

? 3 5

! 00000


? 1 3

! 100

! 001


! 00000000

! 10101010

注意

在示例交互中,输入和输出包含空行,以使交互者响应与查询保持一致。这些空行不会出现在实际的输入和输出中。

在第一个测试用例中,隐藏字符串是 $$$s =$$$ 00000。在这里,自从 0 无法创建任何反转,数组 $$$a$$$ 对于所有子字符串将始终为 $$$[0]$$$。因此,$$$f(l, r)$$$ 对于所有查询都会返回 $$$1$$$。

这里我们进行了 $$$3$$$ 查询。

第一个查询是 $$$f(1,5)$$$ 返回 1 — 此查询的成本为 $$$\dfrac{5}{5-1+1} = 1$$$。

第二个查询是 $$$f(2,5)$$$,它返回 1 — 此查询的成本为 $$$\dfrac{5}{5-2+1} = \dfrac{5}{4}$$$。

第三个查询是 $$$f(3,5)$$$,它返回 1 — 此查询的成本为 $$$\dfrac{5}{5-3+1} = \dfrac{5}{3}$$$。

所有这些查询后的总成本 $$$= 1 + \dfrac{5}{4} + \dfrac{5}{3} = \dfrac{47}{12}$$$ 小于 $$$\max(30, 3\cdot n) = 30$$$。

在此之后,我们猜测 $$$s =$$$ 00000,交互器返回 $$$1$$$,表明猜测正确。然后我们转向下一个测试用例。

在第二个测试用例中,隐藏字符串是 $$$s =$$$ 001.

我们进行查询 $$$f(1,3)$$$,它返回 3。此查询的成本为 $$$\dfrac{3}{3-1+1} = 1$$$。

查询的总成本为 $$$1$$$,小于 $$$\max(30, 3\cdot n) = 30$$$。

然后我们猜测 100,交互器返回 0,表明它不正确。

我们猜测 001,交互器返回 1,说明我们的猜测是正确的。然后我们转向下一个测试用例。

对于第三个测试用例,隐藏字符串是 $$$s =$$$ 10101010.