CF1117E Decypher the String

这是一个交互题。在与测试程序通信时，请记得刷新输出。你可以在 C++ 中使用 fflush(stdout)，在 Java 中使用 system.out.flush()，在 Python 中使用 stdout.flush()，在 Pascal 中使用 flush(output) 来刷新输出。如果你使用其他编程语言，请查阅其文档。你也可以参考关于交互题的指南：。 给定一个由 $n$ 个小写拉丁字母组成的字符串 $t$。该字符串是通过如下方式加密得到的：最初，评测系统有一个由 $n$ 个小写拉丁字母组成的字符串 $s$。然后，他们对 $s$ 进行了不超过 $n$ 次（可能为零次）操作。第 $i$ 次操作用两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$）表示，表示交换字符串中下标为 $a_i$ 和 $b_i$ 的两个字符。所有操作按顺序依次进行。例如，如果 $s$ 为 xyz，执行以下两次操作：$a_1 = 1, b_1 = 2$；$a_2 = 2, b_2 = 3$，那么第一次操作后当前字符串为 yxz，第二次操作后为 yzx，因此 $t$ 为 yzx。 你的任务是还原原始字符串 $s$。不幸的是，你无法获得关于操作序列的任何信息（你甚至不知道是否进行了操作）。但你可以对任意你想要的字符串（只要它只包含小写拉丁字母且长度为 $n$）执行同样的操作序列，并获得经过这些操作后的结果字符串。 你能否在不超过 $3$ 次询问的情况下，猜出原始字符串 $s$？ 对于每个测试，字符串 $s$ 和交换操作序列都是固定的；交互器不会根据你的解法调整测试数据。

最开始，测试系统会发送一个字符串 $t$，由小写拉丁字母组成（$1 \le |t| = n \le 10^4$）。

为了给出答案，你的程序应输出一行 $!$ $s$，并以换行符结尾。之后应刷新输出并正常结束程序。 交互说明 在给出答案前，你最多可以提交 $3$ 次询问。每次询问，输出一行格式为：$?$ $s'$，其中 $s'$ 是一个恰好 $n$ 个小写拉丁字母组成的字符串。该行应以换行符结尾。提交询问后，刷新输出并读取本次询问的答案——一个长度为 $n$ 的小写拉丁字母字符串 $t'$，表示对 $s'$ 执行同样的交换操作序列后的结果。该字符串会单独一行输出，以换行符结尾。 如果你提交了不合法的询问（或询问次数超过 $3$ 次），你将收到一个字符串 0 作为回应。收到该回应后，你的程序应立即终止——否则你可能会收到“运行时错误”、“超时”或其他非“答案错误”的判定。

在样例中，测试用例如题面所述。参赛者第一次询问字符串 baa，被变换为 aab。第二次询问字符串 aba，被变换为 baa。第三次询问字符串 aab，被变换为 aba。参赛者可以由此推断出原始字符串 $s$ 是 xyz。 Hack 阶段说明： 在 Hack 阶段提交测试数据时，格式如下： 第一行是你猜测的字符串 $s$，由 $n \in [1, 10000]$ 个小写拉丁字母组成。 第二行是 $k$（$0 \le k \le n$）——操作序列的交换次数。 接下来 $k$ 行，每行两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$），表示第 $i$ 次操作。 例如，样例测试数据如下： xyz 2 1 2 2 3 由 ChatGPT 4.1 翻译