## 0x04 <br> 2021 TOI 初選 模擬賽 <br> 題解 --- ### 大綱 - pA - 格雷碼 (Decode) - pB - 黑白棋與監禁生活 (Reversi) - pC - 秋收萬顆子 (Polygon) - pD - 天使島大地主視察事件 (Traverse) - pE - 小軒小羽取石子 (Stone) --- ## pA - 格雷碼 (Decode) ---- - 給一個 $01$ 字串 $s$ $\small(1 \le |s| \le 10^5)$ - 求在某種格雷碼的構造方式中 $s$ 的編碼 - 有多筆測資 ---- ### Subtask - $[36]$ $|s| \le 15$ - $[32]$ $|s| \le 60$ - $[32]$ $|s| \le 10^5$ ---- ### Subtask 1 ($|s| \le 15$) - 字串的前導 $0$ 是多餘的 - 輸入總共有 $2^{15} = 32768$ 種 - 預處理！ ---- ### Solution 1 - 把字串全部丟進 `std::vector` 裡面做二分搜 - 或是直接塞進 `std::map` ---- ### Solution 2 - 把 $01$ 字串當成一個二進位數字直接存進陣列裡 - 預處理答案 ---- $\color{red}{WA}$ $(36/100)$ ---- ### AC Solution ($|s| \le 10^5$) - 觀察規律  ---- - 假設 $\mathcal{S}$ 的左子樹是 $\mathcal{L}$，右子樹是 $\mathcal{R}$ - 如果往 $0$ 走，那左子樹仍會是 $\mathcal{L}$，右子樹也仍是 $\mathcal{R}$ - 如果往 $1$ 走，那左子樹會變成 $\mathcal{R}$，右子樹會變成 $\mathcal{L}$ - 遞迴處理就好 - $2^k$ 可以預處理或是用快速冪 ---- $\color{lime}{AC}$ $(100/100)$ ---- ### 數學解 - 其實這種構造方法是有通式的，而且也很好看 - $G(n) = n \oplus \lfloor{\frac{n}{2}}\rfloor$ ---- - 要把 $G(n)$ 還原成 $n$ 也很簡單 ```cpp= for (int i = 1; i < s.size(); ++i) { s[i] = s[i] == s[i-1] ? '0' : '1'; } ``` ```cpp= int ans = 0; for (auto c : s) ans = (2 * ans + (c == '1')) % mod; cout << ans % mod << "\n"; ``` ---- $\color{lime}{AC}$ $(100/100)$ --- ## pB - 黑白棋與監禁生活 (Reversi) ---- - 給你 $N \times N$ $\small(N \le 2000)$ 的 $01$ 矩陣 - 每次在主對角線上選一個正方形，把全部 xor $1$ - 求數字都變成 $0$ 的最少次數 ---- ### Subtask - $[17]$ $N \le 5$，保證有解 - $[52]$ $N \le 80$ - $[31]$ $N \le 2000$ ---- ### 小性質 - 首先，矩陣一定要對稱（$A[i][j] = A[j][i]$） - 證明：每次對 $A[i][j]$ 修改的時候一定也會動到 $A[j][i]$ - 其餘情況必定有解 ---- ### Subtask 2 ($N \le 80$) - 先考慮右上角 $(1, N)$ 的格子 - 只有在選 $(1, 1) \sim (N, N)$ 的時候才會修改到他 - 接下來是在 $(1, N-1)$ 跟 $(2, N)$ 的格子 - 在確定是否要選 $(1, 1) \sim (N, N)$ 之後想改變這些格子的數字也都只有一種方法 ---- - 每次都暴力修改的複雜度是 $O(N^4)$ ---- - $\color{cyan}{TLE}$ $(69/100)$ ---- ### AC Solution 1 ($N \le 2000$) - 看起來只有修改的複雜度可以降低 - 每次的修改都是區間修改，查詢都是按照順序 - 是不是可以... ---- - 差分！ ---- ```cpp= for (int i = 0; i < n; ++i) { for (int j = n-1; j > i; --j) { int p = cnt[i][j]; if ((A[i][j] ^ p) == '1') { cnt[i+1][j-1] ^= 1, cnt[i+1][j] ^= 1, cnt[i][j-1] ^= 1, ++ans; } cnt[i+1][j-1] ^= p, cnt[i+1][j] ^= p, cnt[i][j-1] ^= p; } } ``` - 好好按照順序來修改就不會出事 ---- $\color{lime}{AC}$ $(100/100)$ ---- ### AC Solution 2 - 如果你討厭麻煩的實作... - 不要差分了！來砸毒瘤吧！ - 直接寫一個支援區間加值、單點求值的咚咚 - 二維 BIT！ ---- - $O(N^2 \lg^2{N})$ 可以過嗎？ ---- $\color{cyan}{TLE}$ $(69/100)$ 或 $\color{lime}{AC}$ $(100/100)$ - 依照你實作的常數而定（我要跑 980ms，賽中有人 480ms 過） - BIT 真的跑超快 QAQ --- ## pC - 秋收萬顆子 (Polygon) ---- - 平面上一開始有三個點，之後有 $Q$ $\small(Q \le 10^5)$ 次加點操作 - 每次加點後保證當前的凸包會經過所有點 - 求一開始及每次操作完的多邊形面積 ---- ### Subtask - $[10]$ $Q = 0$ - $[20]$ $Q = 1$，輸入是平行座標軸的矩形。 - $[29]$ $Q \le 1000$ - $[41]$ $Q \le 10^5$ ---- ### Subtask 1 ($Q = 0$) - 三角形面積會算吧 OAO $\frac{1}{2} \times abs\left(\left|\begin{matrix}x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3\end{matrix}\right|\right)$ $= \frac{1}{2} |x_1y_2 + x_2y_3 + x_3y_1 - y_1x_2 - y_2x_3 - y_3x_1|$ - 海龍公式會因為浮點數爆掉 ---- $\color{red}{WA}$ $(10/100)$ ---- ### Subtask 2 ($Q = 1$，輸入是矩形) - 會 Subtask 1 就會這個 - 面積 ${}\times 2$ 就好 - 矩形面積應該也會算吧 ---- $\color{red}{WA}$ $(30/100)$ - Subtask 1 + 2 ---- ### Subtask 3 ($Q \le 1000$) - Q：怎麼計算一個凸多邊形的面積？ - A：用上面說的那個行列式。 - Q：怎麼把點排序？ - A：找到一個在多邊形內部的點，再把所有點按照極角排序 ---- ```cpp= bool cmp(pair<int, int> p1, pair<int, int> p2) { auto [x1, y1] = p1; auto [x2, y2] = p2; if ((x1 > midX) ^ (x2 > midX)) return x1 > midX; double m1 = (y1 - midY) / (x1 - midX); double m2 = (y2 - midY) / (x2 - midX); return m1 < m2; } ``` - `midX` 跟 `midY` 是一開始三角形的中心 ---- $\color{cyan}{TLE}$ $(59/100)$ - 那個值域小其實沒有什麼特性，只是有些人會寫出有可能 overflow 的 code - 不過貌似賽中這個條件完全不重要 (? ---- ### AC Solution ($Q \le 10^5$) - 每次都重新算凸包面積很耗時間 - 觀察到新的凸包只會比原本的多一個三角形  ---- - 加點不好找要加在哪裡嗎？ - 可以用對極座標二分搜來做到 - 不過這邊給一個比較好實作的寫法 ---- ### 加點不好加，那你試過刪點嗎？ - 如果先把凸包建完，題目就變成「給一個凸包，接下來有 $Q$ 次操作，每次刪掉上面的一個點，求每次操作後的面積。」 - 會做了嗎？ ---- - 假設刪掉的是點 $i$ - 那扣掉的三角形面積就是點 $i$、點 $prev[i]$、點 $next[i]$ 所構成的三角形 - 維護 `prev` 跟 `next` 就用 linked-list 實做 ---- ### 整理 - 選一個多邊形內的點，按照極角排序 - 處理每個點的上一個跟下一個點 - 求多邊形面積 - 依序刪回來，每次扣掉一個三角形 - 完成！ ---- $\color{lime}{AC}$ $(100/100)$ ---- ### 細節 - 所有點的座標都是偶數，不用判斷面積會不會有 $.5$ 出現 - 請仔細閱讀題敘，有不少人沒注意到所有點都會出現在凸包上 <!-- - 其實用行列式計算總面積的時候很多人的寫法都會讓答案爆 long long，但是因為會自然 overflow 跟 underflow，所以也卡不了 --> <!-- - 有方法可以避免 --> --- ## pD - 天使島大地主視察事件 (Traverse) ---- - 給你一棵 $N$ $\small(N \le 2000)$ 個點的樹，點有點權 - 找到一條前序走訪路徑使其字典序最小 ---- ### Subtask - $[18]$ $g_i = i$ - $[19]$ 只有 $g_1 = 1$ - $[16]$ $N \le 300$ - $[47]$ $N \le 2000$ ---- ### Subtask 1 ($g_i = i$) - 這個子題應該沒什麼問題吧w - 直接對每個點的邊 sort 再 dfs 就可以ㄌ ---- $\color{red}{WA}$ $(18/100)$ ---- #### Subtask 2 (只有 $g_1 = 1$) - 起點顯然是 $1$ 號 - 接下來呢？ ---- - 處理出每個節點的子樹 dfs 出去的最小字典序路徑 - base case 就是葉節點 - 要怎麼合併？ ----  - 比較字典序？ - `[2,3] < [2,3,4]`，所以先放 `[2,3]` 再放 `[2,3,4]`？ ----  - `[2,3] < [2,3,2]`，但是先走 `[2,3,2]` 會比較好 ---- - 如果先走某個子樹 $\mathcal{S}$ 會比 $\mathcal{T}$ 好 - 那一定有 $\mathcal{ST} < \mathcal{TS}$（比較字典序） - 應該是經典題 (?，不知道怎麼只有很少人拿到這筆分數 ---- $\color{cyan}{TLE}$ $(37/100)$ ---- ### 練習題 - [洛谷 P1012](https://www.luogu.com.cn/problem/P1012) ---- ```cpp= sort(ALL(ch), [](auto vi1, auto vi2) { /// vi1 跟 vi2 的型態都是 pair<vector<int>, int> /// ch 是 vector<pair<vector<int>, int>> auto [v1, id1] = vi1; auto [v2, id2] = vi2; int sz1 = v1.size(), sz2 = v2.size(); for (int i = 0; i < sz1 + sz2; ++i) { int a = i < sz1 ? v1[i] : v2[i-sz1]; int b = i < sz2 ? v2[i] : v1[i-sz2]; if (a != b) return a < b; } return false; }); ``` ---- ### Subtask 3 ($N \le 300$) - 就 Subtask 2 做 $N$ 遍 ---- $\color{cyan}{TLE}$ $(53/100)$ ---- ### AC Solution ($N \le 2000$) - 全方位木 DP (Re-rooting DP) 聽過沒？ - 對，就是這樣 ---- $\color{lime}{AC}$ $(100/100)$ ---- - 基本上是 dfs 兩次 - 第一次求出每個點的子樹的資訊 - 第二次把父節點的資訊帶下來 ---- - 紀錄 ... （WIP） <!-- May 15, 2022: 喔不，我忘記怎麼做了 --> --- ## pE - 小軒小羽取石子 (Stone) ---- - 有 $N$ $\small(N \le 2 \times 10^5)$ 顆石頭排成一列，兩個人在輪流取石頭 - 每次需要取 $K$ $\small(\frac{N}{100} \le K \le N)$ 顆，只能從頭尾取（可以一邊取 $X$ 顆一邊取 $K-X$ 顆） - 石頭上有權重 $a_i$ $\small(|a_i| \le 10^4)$，玩家會想最大化自己的權重和 - 求先手跟後手的分數 ---- ### Subtask - $[12]$ $N \le 100，K = 1$ - $[21]$ $N \le 3000，N \equiv 0 \pmod{K}$ - $[38]$ $N \le 2 \times 10^4$ - $[29]$ $N \le 2 \times 10^5$ ---- ### Subtask 1 ($N \le 100，K = 1$) - 經典到不能再經典了 - 學 DP 都會做過的題目 - [AtCoder Educational DP Contest pL](https://atcoder.jp/contests/dp/tasks/dp_l) ---- - $dp[L][R]$ 代表「剩下編號在 $[L, R)$ 區間的石頭時， 先手減掉後手分數的值」 - $\small dp[L][R] = \max\left\{\begin{matrix}-dp[L+1][R] + v[L], \\ -dp[L][R-1] + v[R-1]\end{matrix}\right\}$ - 最後可以透過 $dp[0][N]$ 跟 $\sum v[i]$ 得到先手跟後手分數 ---- $\color{red}{WA}$ $(12/100)$ ---- ### Subtask 2 ($\small N \le 3000，N \equiv 0 \pmod{K}$) - 跟剛剛類似，只是轉移的來源變成 $\small dp[L+K][R], dp[L+K-1][R-1], \dots, dp[L][R-K]$ 總共 $K+1$ 個 - 區間和的部分當然就是用前綴和 - 直接轉移的話複雜度是 $O(N^2 K) \approx 9 \times 10^9$ - 當然，實際上不會跑那麼久，不過還是會讓你吃 $\color{cyan}{TLE}$ ---- ### 優化 1 - 注意到在求 $dp[0][N]$ 的過程中，其實只會需要知道長度 $K, 2K, 3K, \dots, N$ 的區間答案 - 只考慮長度是 $K$ 的倍數的區間就好 - 時間複雜度 $O(\frac{N^2 K}{K}) = O(N^2) \approx 6 \times 10^6$ ---- $\color{cyan}{TLE}$ 或 $\color{red}{WA}$ $(33/100)$ ---- ### Subtask 3 ($N \le 2 \times 10^4$) - $N \not\equiv 0 \pmod{K}$？ - 實際上需要考慮的是所有長度模 $K$ 跟 $N$ 同餘的狀態 - 上一個子題 $O(N^2)$ 的複雜度看起來也能通過這筆 - 但是空間開太大 cache 變很爛？ - 甚至開不起來，$4 \times 10^8$ 個 `int` 佔 1.6GB 空間 ---- ### 優化 1-1 - 注意到 dp 式總是由長度小的轉移到長度大的，而且都是從長度 $L$ 轉移到長度 $L+K$ - 於是滾動的條件齊全了 - 滾一滾就可以過了～ ---- $\color{cyan}{TLE}$ $(71/100)$ ---- ### 優化 2 - dp 式只有用到 $O(\frac{N^2}{K})$ 的空間，但是卻開了 $O(N^2)$ 給他 - 考慮優化狀態：$dp[L][x]$ 代表「剩下編號在 $[L, L+Kx+(N \bmod K))$ 區間的石頭時， 先手減掉後手分數的最大值」 - 這樣空間就變成 $O(\frac{N^2}{K})$ 了！ ---- $\color{cyan}{TLE}$ $(71/100)$ ---- ### 偷懶 - 如果偷懶直接使用 `std::map<pair<int, int>, int>` 來當 dp 陣列 - 那你會多一個 $O(\lg N)$ 拿到 $\color{cyan}{TLE}$ $(33/100)$ ---- ### AC Solution ($\scriptsize N \le 2 \times 10^5，\frac{N}{100} \le K \le N$) - 回顧一下轉移式： - $\tiny \displaystyle dp[L][x] = \max_{0 \le i \le K}\left\{-dp[L+i][x-1] + \sum_{p=L}^{L+i-1}{a_p} + \sum_{p=L+i+K(x-1)+(N \bmod K)}^{L+Kx+(N \bmod K)-1}{a_p}\right\}$ - $\tiny \displaystyle {} = \max_{0 \le i \le K}\left\{-dp[L+i][x-1] + \sum_{p=L}^{L+Kx+(N \bmod K)-1}{a_p} - \sum_{p=L+i}^{L+i+K(x-1)+(N \bmod K)-1}{a_p}\right\}$ - $\tiny \displaystyle {} = \max_{0 \le i \le K}\left\{-dp[L+i][x-1] - \sum_{p=L+i}^{L+i+K(x-1)+(N \bmod K)-1}{a_p}\right\} + \sum_{p=L}^{L+Kx+(N \bmod K)-1}{a_p}$ - 讓 $\scriptsize \displaystyle dp2[i][x] = -dp[i][x] - \sum_{p=i}^{i+Kx+(N \bmod K)-1}{a_p}$ ---- - 讓 $\scriptsize \displaystyle dp2[i][x] = -dp[i][x] - \sum_{p=i}^{i+Kx+(N \bmod K)-1}{a_p}$ - 轉移式就變成 $\displaystyle dp[L][x] = \max_{0 \le i \le K}\{dp2[L+i][x-1]\}$ - 所有長度為 $K+1$ 的區間最大值！ ---- ### Sliding Windows 實作 - Sparse Table - 線段樹 - **單調隊列** ---- $\color{cyan}{TLE}$ $(71/100)$ 或 $\color{lime}{AC}$ $(100/100)$ - 本來第三筆子題是給用前兩個方法實作的人 - 或是 dp 式用 `std::map` 開 - 沒想到 $O(N^2)$ 優化一下就能過 OwO --- ## 總覽 - pA - 實作數學水題 - pB - Greedy + (差分 / 2D BIT) - pC - 極角排序 + (時光倒流 + linked list / 二分搜) + 高中數學 - pD - 樹 dp + 字串拼接最小字典序 + 換根 - pE - 單調隊列優化 dp --- ## 謝謝收看 peko [計分板](https://sorahisa-rank.github.io/0x00/0x04/ranking)以外的東西都在[這裡](https://drive.google.com/drive/folders/1M9b5ppgllP5Rv3rI3pGm1RaM8EOkuSNR)了！ <!-- <p style="font-size:18px">（3/2 04:00 之前會把標程、測資等等的東西都放上去）</p> --> 各位下週的露營烤加油喵 >////< 希望大家都可以拿 500 分回家 >////< （不過搞不好今年又出更多題）