题目描述

题目译自 European Girls' Olympiad in Informatics 2025 Day1 T2. Dark Ride

黑暗之旅有 $N$ 个房间（编号 $0$ 到 $N-1$）和 $N$ 个开关（编号 $0$ 到 $N-1$），开关 $s$ 控制房间 $p_s$（$p$ 是隐藏的排列，未知）。目标是找到两个开关 $A$ 和 $B$，使得它们分别控制房间 $0$ 和 $N-1$（顺序不限），规则与交互方式如下：

1. 初始状态：每次旅程前所有灯光关闭。
2. 开关设置：选择部分开关打开（输出由 0/1 组成的字符串，1 表示打开），启动旅程。
3. 尖叫次数：旅程按房间 $0 \to 1 \to \dots \to N-1$ 顺序进行，相邻房间明暗状态变化时产生 1 次尖叫，交互器返回尖叫次数 $\ell$。
4. 限制：最多发起 30 次旅程，最终输出正确的 $A$ 和 $B$。

交互方式

1. 输入初始信息：首先读取整数 $N$（房间与开关数量）。
2. 发起旅程：输出一行 ? S（$S$ 是长度为 $N$ 的 0/1 字符串），刷新输出后，读取交互器返回的尖叫次数 $\ell$。
3. 提交答案：确定结果后，输出一行 ! A B（$A$ 和 $B$ 是控制房间 $0$ 和 $N-1$ 的开关），刷新输出后程序退出。
4. 关键说明：交互器非自适应，隐藏排列 $p$ 在交互开始前固定。

样例解析

样例 1

交互流程

隐藏排列

$p = [2, 1, 0, 3, 4]$，首次旅程中亮灯房间为 $2、4$，旅程中状态变化为：暗→亮（房间 1→2）、亮→暗（2→3）、暗→亮（3→4），共 3 次尖叫。

样例 2

交互流程

核心解题思路

1. 关键观察：亮灯房间与尖叫次数的关系

• 设打开的开关对应控制的房间集合为 $L$（亮灯房间），将 $L$ 按房间编号排序为 $l_0 < l_1 < \dots < l_k$。
• 尖叫次数 $\ell$ 的计算规则：
  • 若 $l_0 > 0$：开头有 1 次（暗→亮，房间 $l_0-1 \to l_0$）；
  • 若 $l_k < N-1$：结尾有 1 次（亮→暗，房间 $l_k \to l_k+1$）；
  • 中间每两个相邻亮灯房间 $l_i$ 和 $l_{i+1}$（$l_{i+1} > l_i + 1$）：产生 1 次（亮→暗→亮，中间暗房间段导致 1 次变化）。
• 简化公式：$\ell = 2 \times \text{亮灯房间段数} - \text{首尾是否亮灯的修正值}$（例如，全亮时段数为 1，$\ell=0$；仅房间 0 和 $N-1$ 亮时，段数为 2，$\ell=2$）。

2. 核心策略：二分法定位目标开关

目标是找到控制房间 $0$ 的开关 $A$ 和控制房间 $N-1$ 的开关 $B$，利用“单次旅程可验证一组开关是否包含 $A$ 或 $B$”的特性，用二分法减少查询次数（30 次足够覆盖 $N \leq 2^{30}$ 的情况）。

步骤 1：定位控制房间 0 的开关 $A$

• 对开关编号 $0 \sim N-1$ 进行二分，每次选择一个区间 $[L, R]$ 的开关打开，发起旅程：
  • 若尖叫次数包含“开头亮灯”的特征（如段数变化），说明 $A$ 在 $[L, R]$ 内，缩小范围到左半区；
  • 否则 $A$ 在右半区，继续二分。
• 重复直至找到唯一的 $A$（仅打开 $A$ 时，尖叫次数为 1：暗→亮（房间 0）、亮→暗（房间 0→1））。

步骤 2：定位控制房间 $N-1$ 的开关 $B$

• 同理，二分开关编号，每次打开区间内的开关，结合已找到的 $A$（固定打开 $A$ 以辅助判断），通过尖叫次数是否包含“结尾亮灯”的特征，定位 $B$。
• 仅打开 $B$ 时，尖叫次数为 1：暗→亮（房间 $N-1$ 前的暗→亮）、亮→暗（无，因房间 $N-1$ 是最后一个，故仅 1 次变化）。

3. 优化：减少查询次数

• 每次二分查询可同时验证“是否包含 $A$”和“是否包含 $B$”（例如打开一组开关，根据尖叫次数判断是否同时包含两者、仅含其一或都不含），进一步减少查询次数（理论上 2 次二分共需约 $2 \times \log_2 N$ 次，$N \leq 3 \times 10^4$ 时仅需约 30 次）。

数据范围与子任务