AT_s8pc_4_h Huge Kingdom: Atcoder
题目描述
[problemUrl]: https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_h
本题为马拉松题。出题者的解法并不一定能获得满分，请尽量取得更高的得分。
配分：$1500$ 分。
Atcoder 王国由 $N$ 个城市和 $N-1$ 条道路组成。
此外，该王国是连通的。也就是说，是一棵树。
你需要猜出王国的结构。
这里的结构指的是每条道路连接了编号为哪两个城市。
你可以按照如下方式进行询问以推断该结构：
- 输出一个长度为 $N$ 的字符串 $S$。当 $S_i=1$ 时，第 $i$ 个城市被涂黑；当 $S_i=0$ 时，第 $i$ 个城市被涂白。
- 考虑 $N$ 个顶点的图 $G$。
- 如果某条道路两端的城市都被涂黑，则在图 $G$ 中添加该边。
- 返回 $G$ 的每个连通分量的「树的直径」的平方的总和。
例如，若结构如图所示，且 $S=\text{"11001111"}$，则返回的值如下图所示。
在尽量少的询问次数下，推断出王国的结构。
输入格式
本题为交互题。
最开始，会输入如下内容：
> $N$
- 一行，给出 Atcoder 王国的城市数 $N$。
接下来，你可以按如下格式进行询问：
> ? $S$
$S$ 为你要查询的字符串（即城市涂色方案），长度必须为 $N$。
每次询问后，会返回如下内容：
> $d$
按照题目描述的方法构建图 $G$，返回 $G$ 的每个连通分量的「树的直径」的平方的总和。
最后，你需按如下格式输出答案：
> ! $(a_1,b_1)$ $(a_2,b_2)$ $(a_3,b_3)$ … $(a_{N-1},b_{N-1})$
表示你已推断出 Atcoder 王国的结构。
$(a_i, b_i)$ 表示城市 $a_i$ 与城市 $b_i$ 直接相连。
注意，道路的输出顺序、每条道路 $(a_i, b_i)$ 或 $(b_i, a_i)$ 的顺序均可任选。
输出格式
无
说明/提示
## 限制
- $N = 200$
- Atcoder 王国有 $N-1$ 条道路，且是连通的
- 城市编号为 $0$ 到 $N-1$（从 $0$ 开始编号）
- 测试用例为随机生成
## 测试用例生成方法
重复以下操作，直到所有城市都连通（只有一个连通分量）为止：
- 随机选择城市编号 $u$ 和 $v$。
- 如果当前状态下，城市 $u$ 和 $v$ 不能通过一些道路相互到达，则在 $u$ 和 $v$ 之间连一条道路。
- 否则，不做任何操作，重新开始。
## 得分
假设你总共询问了 $L$ 次，理论得分如下：
- 当 $L > 20000$ 时，得分为 $0$
- $L = 18000$ 时，得分为 $500$
- $L = 4000$ 时，得分为 $2000$
- $L = 1200$ 时，得分为 $700$
- 当 $L \leq 700$ 时，得分为 $1500$
共 $5$ 个测试用例，总分为理论值除以 $5$。
## 样例说明 1
本例中，$N=4$。实际用例中不会出现如此规模（因为不满足限制）。以下为一次互动过程示例。
程序输入
程序输出
4
? 1111
4
? 1101
4
? 1001
0
? 1100
1
? 1011
0
! (0,1) (1,2) (1,3)
王国结构如下图。
注意，未必每次询问都有意义。
此外，未必每次询问都能确认盘面，也可以“猜”答案。
由 ChatGPT 5 翻译