QOJ.ac

QOJ

Límite de tiempo: 2.0 s Límite de memoria: 256 MB Puntuación total: 100 Interactivo

#11743. 压缩生成子树

Estadísticas

这是一个交互式问题。请确保在每次询问后输出不会被缓存。例如,在 C++ 中使用 fflush(stdout),在 Java 中使用 System.out.flush(),或在 Python 中使用 sys.stdout.flush()

对于一棵包含 $n$ 个顶点(编号为 $1$ 到 $n$)的树 $T$,顶点集合 $X$ 的压缩生成子树 $S(X)$(不在 $X$ 中的顶点称为未被覆盖的顶点)可以通过以下算法定义:

  1. 令 $S(X) \leftarrow T$;
  2. 如果存在任何未被覆盖的顶点,且其恰好有一条边与之相连,则将其连同该边一起移除;
  3. 重复步骤 2,直到条件不再满足;
  4. 如果存在任何未被覆盖的顶点,且其恰好有两条边与之相连,则将其连同这两条边一起移除,并添加一条连接原先两条边剩余端点的新边;
  5. 重复步骤 4,直到条件不再满足。

形式上,$S(X)$ 是 $T$ 的最小子图,它包含 $X$ 中的所有顶点,并将所有其他度数为 2 或更小的顶点平滑处理。

测试 1 中的树,以及 $X = \{3, 4, 6\}$ 和 $X = \{2, 5, 6\}$ 对应的压缩生成子树。

你并不知道树 $T$ 的结构。你的任务是找到它。你可以进行如下形式的询问:“压缩生成子树 $S(X)$ 包含多少个顶点?”。由于如果不加限制,通过此类询问找到树是不可能的,因此在 $T$ 中不存在度数恰好为 2 的顶点。

交互

输入的第一行包含一个整数 $n$ ($2 \le n \le 100$)。

你的程序可以通过打印一行格式为 ? k x1 x2 ... xk 的内容来进行询问,其中整数 $k$ ($1 \le k \le n$) 等于集合 $X$ 中顶点的数量,不同的整数 $x_i$ ($1 \le x_i \le n$) 以任意顺序表示这些顶点。你最多可以进行 2550 次询问。

该询问的回答是一个整数,在单独的一行中给出:即所询问的压缩生成子树中包含的顶点数。

在进行足够的询问后,你的程序必须通过打印一行格式为 ! p2 p3 ... pn 的内容来给出答案。这里,将 $T$ 视为以顶点 1 为根的树,$p_i$ 必须是顶点 $i$ 的父节点。给出答案后,程序必须立即正常终止。

样例

输入 1

6
3
4
4

输出 1

? 3 4 3 6
? 4 1 2 3 6
? 3 2 5 6
! 1 2 2 3 3

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#208EditorialOpen题解jiangly2025-12-13 00:13:05View

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.