P16361 [BalticOI 2026] Hamilton

考虑一个包含 $n$ 个节点的有向图，节点编号为 $1,2,\dots,n$。如果对于每一对不同的节点，两个方向中恰好存在一条有向边，则称该图为一张**竞赛图**。也就是说，对于任意两个不同节点 $u$ 和 $v$，要么存在从 $u$ 到 $v$ 的边，要么存在从 $v$ 到 $u$ 的边。 一条哈密顿回路是一个序列 $c_1, c_2, \dots, c_n$，它沿着图中的边访问所有节点并最终回到起点。对于所有 $1 \le i \le n-1$，必须存在从 $c_i$ 到 $c_{i+1}$ 的边；此外，还必须存在从 $c_n$ 到 $c_1$ 的边。 你可以自由构造一张 $n$ 个节点的竞赛图。随后，节点的编号会被随机打乱。通过针对打乱后图中的边的方向进行询问，你能否找到一条哈密顿回路？ ### 交互方式 本题为交互题。首先读入两个整数 $n$ 和 $t$：分别表示节点数与测试数据组数。 接下来，输出 $n$ 行来描述竞赛图。在第 $u$ 行中输出 $n$ 个字符 "`0`" 或 "`1`"。位置 $v$ 上的字符 "`1`" 表示存在一条从 $u$ 到 $v$ 的边。从节点到自身的边不应存在。 随后会进行 $t$ 组测试。每组测试均使用你提供的同一张图，但节点编号会被打乱并对你的程序保密。你可以进行若干次询问，之后需要给出一个哈密顿回路。 若要发起询问，请输出 "`?` $u$ $v$"，其中 $1 \le u,v \le n$ 是打乱后的图中的两个不同节点。交互库会回复 "`>`" 表示存在从 $u$ 到 $v$ 的边，或 "`

无

无

### 解释 在第一组测试数据中，打乱后的编号恰好与原编号一致，因此 $1,2,3,4,5$ 就是一条哈密顿回路。 在第二组测试数据中，节点编号 $1,2,3,4,5$ 依次被随机打乱为 $2,4,1,5,3$。序列 $1,5,4,3,2$ 确实是一条哈密顿回路，因为它在原图中对应于 $3,4,2,5,1$。 下图中，左图为原图，右图为第二组测试数据中打乱后的图。两条哈密顿回路以红色高亮标注。 :::align{center}  ::: ### 数据范围 - $4 \le n \le 500$ - $1 \le t \le 200$ ### 评分 每个子任务中仅有一个测试输入，包含 $t = 200$ 组测试数据。在每组测试数据中，图的节点编号会被均匀随机地打乱。在单组测试数据中发起超过 $10^4$ 次询问将导致判决为 WRONG ANSWER。 设 $Q$ 为你的程序在某一子任务所有测试数据中询问次数的平均值。若 $Q$ 不超过指定限制，你将获得该子任务的分数。 | 子任务 | 约束条件 | 分值 | | :---: | --- | :---: | | 1 | $n = 4, Q \le 12$ | $5$ | | 2 | $n = 50, Q \le 1225$ | $7$ | | 3 | $n = 50, Q \le 300$ | $12$ | | 4 | $n = 500, Q \le 1500$ | $1\sim 76$ | 在子任务 4 中，你的得分根据以下公式计算： $$ \left\lfloor \frac {25\,000} {\max(750, Q) - 500} - 24 \right\rfloor $$ 例如，如果你的程序平均询问次数为 $Q=1500$，你将从此子任务获得 1 分；若 $Q=1000$，获得 26 分；若 $Q=750$，获得 76 分。 翻译由 DeepSeek V4 Pro 完成