2025 ICPC Asia Pacific Championship

$∣ V_{T} ∣$ 不能超過 $∣ V_{S} ∣$ ，因為每個 $T$ 的 $0$ 至少要吃掉一個 $S$ 的 $0$ 。
$V_{T} [0] \leq V_{S} [0]$ 且 $V_{T} [- 1] \leq V_{S} [- 1]$ ，因為 $T$ 中第一段的 $V_{T} [0]$ 個 $1$ 只能對上 $S$ 的前面 $V_{S} [0]$ 個 $1$ （ $1$ 吃不掉 $0$ ），最後一段同理。

接著就可以貪心的對 $i = 1, 2, \dots, ∣ V_{T} ∣ - 2$ 找 $V_{S}$ 中 $\geq V_{T} [i]$ 的第一個位置。

可以 greedy 匹配的原因是 $T$ 中連續的 $1$ 只會匹配到 $S$ 中連續的 $1$ ，且對 $i < j$ ， $T_{i}$ 匹配到的位置一定在 $T_{j}$ 匹配到的位置之前。
也就是說要找到任意 $1 \leq i_{1} < i_{2} < \dots < i_{∣ V_{T} ∣ - 2} \leq ∣ V_{S} ∣ - 2$ 滿足 $\forall k . V_{T} [k] \leq V_{S} [i_{k}]$ ，是經典的 greedy 問題。

H. Secret Lilies and Roses

Tags: `interactive`, `binary search`

有一個隱藏的長度 $n$ 的字串 $S$ ，其中只包含 $L$ 跟 $R$ 兩種字元。請在 $Q$ 次詢問以內找到一個位置 $p \in [0, n]$ 滿足：

在 $S_{1}, S_{2}, \dots, S_{p}$ 中的 $L$ 數量（ $= ℓ_{p}$ ）等於在 $S_{p + 1}, S_{p + 2}, \dots, S_{n}$ 中的 $R$ 數量（ $= r_{p}$ ）。

你有兩種詢問操作可以做，分別是：

給定 $p \in [1, n]$ ，詢問 $S_{p}$ 。

給定 $p \in [0, n]$ ，詢問 $m_{p} =_{def} ℓ_{p} \times r_{p}$ 。

多筆測資、 $n \leq 100$ 、 $Q = 10$

先觀察到 $c_{p} =_{def} r_{p} - ℓ_{p}$ 在 $p = 0$ 時會是 $S$ 中 $R$ 的數量，且 $c_{p + 1} = c_{p} - 1$ （因為一定是多一個 $L$ 或少一個 $R$ ）。目標 $c_{p} = 0$ 的位置就剛好是 $p = # R$ 。

如果能戳到第一個 $L$ 或最後一個 $R$ 得到他的 multi，就能直接知道某個 $p$ 的 $c_{p}$ 。

觀察 $m_{p}$ 的性質：他會有一個前綴後綴是 $0$ 、中間（可能為空）都是非 $0$ 。

為了得到 $0$ 跟非 $0$ 的交界，我們可以嘗試搜出一個 $RL$ substring，令 $R$ 的位置為 $p^{*}$ ，則

$ℓ_{p^{*} + 1}$ 戳在 $L$ 右邊所以是 $ℓ_{p^{*}} + 1$ ， $m_{p^{*} + 1} = m_{p^{*}} + r_{p^{*}}$ ；
$r_{p^{*} - 1}$ 戳在 $R$ 左邊所以是 $r_{p^{*}} + 1$ ， $m_{p^{*} - 1} = m_{p^{*}} + ℓ_{p^{*}}$ 。