CF1081F Tricky Interactor

这是一个交互题。 Chouti 学习累了，于是打开电脑开始玩一个解谜游戏。 很久很久以前，这个男孩发现了一个长度为 $n$ 的序列 $s_1, s_2, \ldots, s_n$，由一个狡猾的交互器保管。该序列只包含 $0$ 和 $1$，其中 $1$ 的个数为 $t$。男孩除了知道 $n$ 和 $t$ 外，对这个序列一无所知，但他可以通过与交互器进行一些查询来尝试找出这个序列。 我们定义一种操作叫做翻转。翻转 $[l,r]$（$1 \leq l \leq r \leq n$）表示对每个 $x \in [l,r]$，将 $s_x$ 变为 $1-s_x$。 在每次查询中，男孩可以给交互器两个整数 $l, r$，满足 $1 \leq l \leq r \leq n$，然后交互器会以相同的概率选择翻转 $[1,r]$ 或 $[l,n]$（所有决策均独立，详见提示部分）。每次操作后，交互器会告知当前序列中 $1$ 的个数。注意，序列在每次操作后不会恢复。 请帮助男孩在不超过 $10000$ 次交互内找出原始序列。 “奇怪的传说，愚蠢的游戏。”他这样想着。然而，尝试了几次后，他依然卡在了这里。你能帮他通关吗？

交互以一行两个整数 $n$ 和 $t$ 开始（$1 \leq n \leq 300$，$0 \leq t \leq n$），分别表示序列的长度和其中 $1$ 的个数。 之后，你可以进行查询。 每次查询时，输出一行 "? l r"（$1 \leq l \leq r \leq n$），然后刷新输出。 每次查询后，读取一个整数 $t$（$-1 \leq t \leq n$）。 - 如果 $t=-1$，表示你已用尽查询次数，程序应立即终止，否则会因为与已关闭的流交互而导致评测结果不可预期，并判为 Wrong Answer。 - 如果 $t \geq 0$，表示当前序列中 $1$ 的个数。 当你确定了原始序列后，输出一行 "! s"，刷新输出并终止程序。$s_1, s_2, \ldots, s_n$ 作为一个二进制字符串输出，中间不加空格。 如果你没有输出任何内容或忘记刷新输出，将会被判为 Idleness Limit Exceeded。 刷新输出的方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hacks 对于 hack 数据，使用如下格式： 第一行输出一个非空二进制字符串。其长度为 $n$，将被视为 $s_1, s_2, \ldots, s_n$。 例如，样例对应的测试数据为一行 "0011"。

见输入格式。

对于第一次查询 $1,1$，交互器会选择翻转 $[1,1]$ 或 $[1,4]$。假设它选择了翻转 $[1,4]$，则序列变为 1100。 第二次查询 $1,1$，交互器会再次选择翻转 $[1,1]$ 或 $[1,4]$。假设它又选择了翻转 $[1,4]$，则序列变为 0011。 第三次查询 $3,4$，交互器会选择翻转 $[1,4]$ 或 $[3,4]$。假设它选择了翻转 $[3,4]$，则序列变为 0000。 问：交互器是如何在 $[1,r]$ 和 $[l,n]$ 之间选择的？真的随机吗？ 答：交互器会使用一个秘密的[伪随机数生成器](https://en.wikipedia.org/wiki/Pseudorandom_number_generator)。只有 $s$ 和你的查询会被哈希并用作种子。因此，如果你对同一个秘密字符串给出相同的查询序列，将会得到相同的结果。除此之外，你可以认为选择是完全随机的，就像抛硬币一样。你不需要（也不应该）利用具体的生成器来通过本题。 由 ChatGPT 4.1 翻译