CEOI 2016 Day 1
今天來整理 CEOI 的題目吧～
太空人 Astro 要在國際航空站 (ISS) 執行他的實習任務：觀察 Terrans 的文明發展過程。在稱之為 Mar Sara 的行星上頭有 $N$ 個 Terran 聚落（編號為 $1$ 到 $N$），而且一開始聚落之間並沒有任何的（雙向的）道路被建造。但漸漸地，有 $N-1$ 條道路被逐漸建造了，Terrans 相當地有效率，他們每一次會建造一條道路連接兩個聚落，而兩個聚落在道路還沒有建成之前是無法經由蓋好的道路往來的。
Astro 的目標，是要在每一次 Terrans 蓋好一條道路的時候，精確地推敲出這條道路連接的兩個聚落編號，並回報給 ISS。他有一個航太望遠鏡 SETI，每一次下 ${\mathtt{query}}(A, B)$ 的指令，輸入兩個陣列的聚落編號 $A, B \subseteq \{1, 2, \ldots, n\}$。SETI 會回傳一個 true 或 false：告訴你是否存在一條道路直接地連結 $A$ 中的一個聚落和 $B$ 裡頭的一個聚落。
請你實作一個函式 void run(int N);，並且利用 query() 和 setRoad() 兩個函式使用 SETI 望遠鏡，或是回報被建造的道路。
評分方式
query() 使用的總次數有限制如下：
| 子任務 | $N$ | $M=$ 詢問的最大次數 | 子任務分數 |
|---|---|---|---|
| 1 | 15 | 1500 | 7 |
| 2 | 50 | 2500 | 11 |
| 3 | 100 | 2250 | 22 |
| 4 | 100 | 2000 | 21 |
| 5 | 100 | 1775 | 29 |
| 6 | 100 | 1625 | 10 |
感覺上就是個實作每次 $2\log n$ 最小二分圖覆蓋的題目哈哈，不曉得有沒有輕巧的寫法就是。
一個花園裡頭有一整排連續的 $N$ 個格子，編號從左到右分別為 $1, 2, \ldots, N$。一隻袋鼠從外面跳進了編號為 $cs$ 的格子，他想要把所有格子裡面的植物通通吃掉，然後結束在編號為 $cf$ 的格子上。 袋鼠為了不被抓到，他必須要左右跳──也就是說若前一跳往編號小的地方跳、那下一次就必須要往編號大的地方跳，此外，袋鼠也不能重複跳到任一個之前跳到的格子上。請問跳遍所有格子有幾種可能的方案呢？請輸出可能的方案數除以 $10^9+7$ 的餘數。
測資範圍
- $2\le N\le 2000$
- $1\le cs \le N$
- $1\le cf \le N$
- $cs\neq cf$
這題是很趣味的組合計數 DP。對於所有的 $i < j$，定義：
- $A(n, i, j)= $ 從 $i$ 開始、從 $j$ 結束而且第一步往右走的交錯排列總數。
- $D(n, i, j)= $ 從 $i$ 開始、從 $j$ 結束而且第一步往左走的交錯排列總數。
因為 $i < j$，所以我們可以得出以下遞迴式：
- $A(n, i, j) = A(n, i-1, j) - D(n-1, i-1, j-1)$
- $D(n, i, j) = D(n, i-1, j) + A(n-1, i-1, j-1)$
由對稱性，我們可以假設 $cs < cf$。 我們的所求是 $X(N, cs, cf) = A(N, cs, cf) + D(N, cs, cf)$。
經過一陣展開與推敲之後，我們可以得出：
這題厲害的地方在於，在上述遞迴式的計算中，$n-j$ 的值恆為常數（$=N-cf$），於是我們可以在 $O(N^2)$ 時間內解決這個問題。邊界條件 $i\le 2$ 的部份需要手動求一下，基本上可以利用遞迴的定義展開。
魔術師帶了兩位助手，想要打敗邪惡多端的吸血鬼德古拉。魔術師準備了編號為 $0, 1, \ldots, 2N$ 總共 $2N+1$ 張牌，他要德古拉把其中一張拿在手上。接著，魔術師要德古拉把剩下的 $2N$ 張牌任意地（邪惡地？）平分成兩堆，其中的 $N$ 張交給第一位助手、另外的 $N$ 張交給第二位助手。這兩位助手從手上的 $N$ 張牌當中，挑出兩張並且依照挑出來的順序出示給魔術師看。魔術師要從僅有的四張牌資訊，猜出德古拉拿走的那張牌編號是多少。
在魔術開始之後，魔術師與助手們就不能再以任何形式溝通了。所以請你幫幫魔術師與助手們，模擬他們的操作，準確地猜出德古拉手上的牌。同一筆測試資料會被執行三次：一次要你執行助手 A 的操作（你會拿到某 $N$ 張牌，並且回傳兩張牌）、第二次會要你執行助手 B 的操作（你會拿到另外的 $N$ 張牌，並且回傳兩張牌）、第三次會要你執行魔術師的操作（收到按照順序的四張牌，並回傳真正被德古拉拿走的牌）。$N\le 1234567$。
通常這種掛一漏萬的題目，不是用 XOR 就是用總和 $\bmod M$ 想辦法找出缺少的值。
這題的官方解法用的是總和 $\bmod (2N+1)$，顯然所有數字的和 $=N(2N+1)$，於是除以 $M=(2N+1)$ 的餘數恰好是 $0$。若我們能從兩個子集合 $S_1, S_2$ 之中分別輸出 $(a, b)\to s_1$ 對應到 $S_1$ 所有元素和、$(c, d)\to s_2$ 對應到 $S_2$ 所有元素和，那麼缺少的那個數就必定是 $(0-s_1-s_2)\bmod M$。
找出對應函數
現在我們把所有數字想像成在模 $(2N+1)$ 的世界裡頭：也就是所有加減運算都在 $\mathbb{Z}_{2N+1}$ 裡面進行。首先，注意到所有的 $(a, b)$ 配對總共有 $(2N+1)\times (2N)$ 這麼多種，而因為 $a\neq b$，我們知道 $a-b\in\{1, 2, \ldots, 2N\}$ 恰好有 $2N$ 種選擇。
於是，一個可行的對應方案是，對於每一個 $s$，我們構造出一些「對應的數對」：
這些數對構成了 $3$ 個三角形、以及 $N-4$ 對匹配。總共有 $2N+1$ 個數字全部都在上面了。厲害的是，如果我們從這 $2N+1$ 個數字當中任取 $N$ 個，由鴿籠原理可以得知「至少有兩個數字落在某個三角形裡頭、或是兩個數字落在同一個匹配裡面」，這代表什麼呢？
假設我們今天獲得一個總和是 $s (\bmod 2N+1)$ 的 $N$ 張牌，我們把上圖所有數字都加上 $s$，仍然可以找到某兩張牌是在圖上共用一條邊（相鄰）的！這代表魔術師的助手總是可以挑出兩個數字 $X, Y$，而魔術師從這兩個數字的差 $X-Y$，可以唯一確定它對應到圖上的哪一條邊，從而得知 $s$ 的值！酷吧！