CF1687B Railway System

至于外界的科技，对于幻想乡来说实在是太过先进，连仰望都做不到。 ——八坂神奈子，《后神秘主义座谈会》 本题为交互题。 在神奈子和守矢神社的直接监督下，幻想乡的铁路系统终于建成了。GSKR（幻想乡铁路）由 $n$ 个车站和 $m$ 条双向铁轨组成，第 $i$ 条铁轨的长度为 $l_i$（$1 \leq l_i \leq 10^6$）。由于预算有限，铁路系统可能不是连通的，且两站之间可能有多条铁轨。 一个铁路系统的价值定义为所有铁轨长度之和。铁路系统的最大（或最小）容量定义为当前系统所有[全生成森林](https://en.wikipedia.org/wiki/Spanning_tree#Spanning_forests)中容量的最大（或最小）值。 简而言之，图的全生成森林是一个与原图连通性相同的生成森林。 神奈子有一个模拟器，最多只能处理 $2m$ 次查询。模拟器的输入是一个长度为 $m$ 的字符串 $s$，每个字符为 $0$ 或 $1$。若 $s_i=1$，则第 $i$ 条铁轨可用。设备会返回当前状态下系统的最大容量。 神奈子希望借助模拟器，求出所有铁轨都可用时系统的最小容量。 铁路系统的结构是预先固定的。换句话说，交互器不会自适应。

输入的第一行包含两个整数 $n,m$（$2 \leq n \leq 200$，$1 \leq m \leq 500$），表示车站数和铁轨数。

首先读入 $n,m$。 每次查询时，输出 "? $s$"（不含引号，$s$ 为长度为 $m$ 的仅包含 $0$ 和 $1$ 的字符串）。然后从标准输入读入我们的回复——当前系统的最大容量。 如果你的程序进行了非法查询或超出查询次数限制，交互器会立即终止，你的程序会收到 Wrong answer 判定。 最终给出答案时，输出 "! $L$"（不含引号，$L$ 为所有铁轨可用时系统的最小容量）。注意，输出最终答案不计入 $2m$ 次查询限制。 每次输出查询后不要忘记换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判定。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 数据格式： 输入的第一行包含两个整数 $n,m$（$2 \leq n \leq 200$，$1 \leq m \leq 500$），表示车站数和铁轨数。 接下来的 $m$ 行，每行包含 $3$ 个用空格分隔的整数 $u_i,v_i,l_i$（$1 \leq u_i,v_i \leq n$，$u_i \ne v_i$，$1 \leq l_i \leq 10^6$），表示第 $i$ 条铁轨的两个端点和长度。

下图为样例的结构，满足 $l_i=i$。  由 ChatGPT 4.1 翻译