CSP-S 2021 T3 Palin 題解

CSP-S 2021 T3 回文 palin 題解

給定一個 \(2*n\) 個數字的序列，每個數字都在 \(\{1,2,3,...,n\}\) 内，并且出現且僅出現兩次。

求一個操作序列，使得其滿足按序取出的數字序列為回文序列。操作分為兩種：

<code>L</code>：将原序列左端點處的數取出加入新序列尾部，并将原序列左端點處的數删除。

<code>R</code>：将原序列右端點處的數取出加入新序列尾部，并将原序列右端點處的數删除。

多測，資料組數 \(T\leq 100\)，\(1\leq n,\sum n \leq 2\times 10^5\)。

首先必然考慮第一次操作。無論如何操作，我們都能找到與第一次取出的數 \(x\)（\(x\) 必然在左端點和右端點中取一個） 相同的數。我們不妨假設我們在下标 \(i\) 出找到了另外一個 \(x\)。

手玩下樣例：

這裡我們第一次取出的是左端點，那麼我們找到與左端點相同的那個數 \(4\)，它的下标正好也在第 \(4\) 位。

并且，正因為我們第一次取出的是 \(4\)，是以我們顯然必須将内部第 \(i\) 位的那個 \(4\) 放在最後一位取出。

與此同時，我們得到了把這兩個 \(4\) 給搞定的操作：

由于從左端點取出了一個 \(4\)，那麼第一步操作為 <code>L</code>。

由于最終的這個 \(4\) 無論如何都是在隻有一個元素的序列中取出的，那麼答案無論怎麼變都是 <code>L</code>。

搞定了這兩個 \(4\) 我們接着來看剩下的序列。

由于每次隻能取剩下的左端點和右端點，是以這裡隻能取 \(1\) 和 \(5\) 中間的一個。

我們發現這裡另外 \(1\) 根本不在中間那個 \(4\) 的左右，而如果這一步取 \(1\)，那麼倒數第二步必然得取 \(1\)，那麼最後幾步将無法操作。

考慮取一下 \(5\)，我們發現 \(5\) 在 \(4\) 旁邊，那麼這一步取 \(5\) 就是非常合法的，（至少對于現在已經處理的前兩步和倒數兩步而言）。

這裡我們來思考一下這兩個 \(5\) 是由什麼樣的操作得到的：

由于從右端點取出了一個 \(5\)，那麼第二步操作為 <code>R</code>。

由于從 \(4\) 的右邊取出了另外一個 \(5\)，考慮最終剩下來應該長成什麼樣，大概是：<code>4 5</code> 這樣，那麼倒數第二步也應該是 <code>R</code>。

這時候應該找到一些規律了。但我們接着把這個樣例講完，剩下：

發現右端有一個 \(3\)，\(5\) 右邊有一個 \(3\)，那麼把這兩個 \(3\) 給取出來。這兩步應該都是 <code>R</code>。

左端點和 \(3\) 的右邊都是 \(1\)，是以都取出來，這兩步應該一個是 <code>L</code>，一個是 <code>R</code>。

這個時候取兩個 <code>L</code> 就行。

觀察上面的手模過程，我們發現：

每一步可以确定兩個位置及其操作。

從第二步開始，每個數必然隻能從内部已經取過的數的兩邊來擴充。

形象地來說，内部已經取過的數字可以構成一根“線段”。

由于第一步無法确定從左開始取還是從右開始取，分類讨論即可。

這兩個性質無論對于第一步為 <code>L</code> 還是對于第一步為 <code>R</code> 都是成立的。通過這兩個性質我們可以 \(O(1)\) 的計算出一個序列下一步的操作。

另外，如果一個序列在經過若幹次擴充後無法繼續擴充，那麼無解，因為優先擴充左邊和右邊對于其餘部分無影響，如果能夠擴充就一定會在某一時刻進行擴充。

具體實作呢？

首先，對于第一步分類讨論，找到左端點或右端點所對應的内部點（最後一個被取出來的位置），打上标記。我們不妨稱其為 \(\operatorname{inner}\)。

接下來我們同時維護四根指針：

\(\operatorname{outl}\) 和 \(\operatorname{outr}\)，負責維護在執行完前繼操作後兩端端點在原序列中的位置。

\(\operatorname{inl}\) 和 \(\operatorname{inr}\)，負責維護在執行完前繼操作後内部已操作線段的兩端端點在原序列中的位置。

在執行完每一步操作後對這四根指針進行更新。我們優先進行 \(\operatorname{outl}\) 對于 \(\operatorname{inl}\) 和 \(\operatorname{inr}\) 的比對，原因是輸出字典序最小的。

注意如果在某一時刻 \(\operatorname{inl}\leq\operatorname{outl}\)，那麼不能繼續擴充，否則會将已經擴充過的部分再反向擴充一遍。