[JOI Open 2023] 古代機器 2 / Ancient Machine 2 題解

傳送門：[JOI Open 2023] 古代機器 2 / Ancient Machine 2
完全不會做這種交互題。

形式化題意：交互庫有一個 01 串 \(s\)（下標從 \(0\) 開始），你需要通過若干次詢問求出 \(s\)，每次詢問，你可以構造一個大小為 \(m\) 的自動機（\(m\) 由你自己定），自動機上的狀態節點從 \(0\) 到 \(m-1\) 編號，每個狀態都有 \(0\) 和 \(1\) 兩種轉移（每個狀態的兩種轉移由你自己定），起始狀態為 \(0\)，交互庫會把 \(s\) 放到這個自動機上進行計算，并返回最終到達的狀態編號。要求詢問次數不超過 \(1000\)，同時最小化所有詢問 \(m\) 的最大值。

算法一：\(m\le 1002\)

考慮依次確定每一位，如果我現在要確定 \(s_i\)，則我們可以把狀態 \(0\) 到 \(i\) 串成一條鏈，然后 \(i\) 的 \(0\) 轉移指向 \(i+1\)，\(1\) 轉移指向 \(i+2\)，最后把 \(i+1,i+2\) 連成自環，如下圖：

最后只要看交互庫返回的是 \(i+1\) 還是 \(i+2\) 即可，\(m_{max}=n+2\)。
期望得分 \(10pts\)。

算法二：\(m\le 502\)

相當于折半了，我們先用算法一確定前 \(500\) 位，然后考慮怎么確定后 \(500\) 位。
假設我們已經確定了長度為 \(len-1\) 的后綴，現在我們要確定倒數第 \(len\) 位，我們不妨先假設他是 1，現在相當于?

OIer_Cyq

[JOI Open 2023] 古代機器 2 / Ancient Machine 2 題解

算法一：\(m\le 1002\)

算法二：\(m\le 502\)