CF1697D Guess The String

这是一个交互题。在与测试程序通信时，请记得刷新输出。你可以在 C++ 中使用 fflush(stdout)，在 Java 中使用 system.out.flush()，在 Python 中使用 stdout.flush()，在 Pascal 中使用 flush(output) 来刷新输出。如果你使用其他编程语言，请查阅相关文档。你也可以参考关于交互题的指南：。 评测程序已经选择了一个长度为 $n$ 的字符串 $s$，其中每个字符都是小写拉丁字母。你的任务是猜出这个字符串；最初你只知道它的长度。 你可以提出两种类型的询问： - $1$ $i$ —— 第一类询问，其中 $i$ 是 $1$ 到 $n$ 之间的整数。作为回应，评测程序会告诉你字符 $s_i$； - $2$ $l$ $r$ —— 第二类询问，其中 $l$ 和 $r$ 是满足 $1 \le l \le r \le n$ 的整数。作为回应，评测程序会告诉你 $s_l, s_{l+1}, \dots, s_r$ 中不同字符的个数。 你最多可以提出 $26$ 次第一类询问，最多可以提出 $6000$ 次第二类询问。你的任务是还原字符串 $s$。 对于本题的每个测试，字符串 $s$ 在评测前就已固定，并且每次提交都是同一个字符串。

最开始，评测程序会在单独一行发送一个整数 $n$，表示 $s$ 的长度（$1 \le n \le 1000$）。

为了给出答案，请输出一行 "! s"，其中 $s$ 是评测程序选择的字符串，末尾需换行。之后，你的程序应刷新输出并正常结束。 交互说明 要发起询问，你应输出一行，格式如下： - ? 1 i —— 表示第一类询问（$1 \le i \le n$）； - ? 2 l r —— 表示第二类询问（$1 \le l \le r \le n$）。 发送询问后不要忘记刷新输出。 每次询问的答案会在单独一行给出。对于第一类询问，答案是字符 $s_i$。对于第二类询问，答案是一个整数，表示 $s_l, s_{l+1}, \dots, s_r$ 中不同字符的个数。 你最多可以提出 $26$ 次第一类询问，最多可以提出 $6000$ 次第二类询问。 如果你提出了过多的询问，或者评测程序无法识别你的询问格式，评测程序会返回一个整数 $0$ 作为答案。在收到 $0$ 作为答案后，你的程序应立即终止——否则你可能会收到“运行时错误”、“超时”或其他非“答案错误”的判定。

让我们分析一下交互示例。 评测程序选择的字符串是 guess，因此最开始评测程序发送一个整数 $5$。 1. 第一次询问是 ? 2 1 5，表示“统计 $s_1, s_2, \dots, s_5$ 中不同字符的个数”。答案是 $4$。 2. 第二次询问是 ? 1 2，表示“告诉我 $s_2$ 是什么字符”。答案是 u。 3. 第三次询问是 ? 2 1 2，表示“统计 $s_1$ 和 $s_2$ 中不同字符的个数”。答案是 $2$。 4. 第四次询问是 ? 1 1，表示“告诉我 $s_1$ 是什么字符”。答案是 g。 5. 第五次询问是 ? 1 3，表示“告诉我 $s_3$ 是什么字符”。答案是 e。 6. 第六次询问是 ? 1 4，表示“告诉我 $s_4$ 是什么字符”。答案是 s。 7. 第七次询问是 ? 2 4 5，表示“统计 $s_4$ 和 $s_5$ 中不同字符的个数”。答案是 $1$，因此可以推断 $s_4$ 和 $s_5$ 是相同的字符。 最后，答案以 "! guess" 的形式提交，并且推断正确。 由 ChatGPT 4.1 翻译