## 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$)
- 觀察規律
![](https://i.imgur.com/IyT7dRy.png)
----
- 假設 $\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$)
- 每次都重新算凸包面積很耗時間
- 觀察到新的凸包只會比原本的多一個三角形
![](https://i.imgur.com/byjYnU6.png)
----
- 加點不好找要加在哪裡嗎?
- 可以用對極座標二分搜來做到
- 不過這邊給一個比較好實作的寫法
----
### 加點不好加,那你試過刪點嗎?
- 如果先把凸包建完,題目就變成「給一個凸包,接下來有 $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 就是葉節點
- 要怎麼合併?
----
![](https://i.imgur.com/AGiRrJG.png)
- 比較字典序?
- `[2,3] < [2,3,4]`,所以先放 `[2,3]` 再放 `[2,3,4]`?
----
![](https://i.imgur.com/stGMVZp.png)
- `[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 分回家 >////<
(不過搞不好今年又出更多題)
{"metaMigratedAt":"2023-06-15T19:36:41.422Z","metaMigratedFrom":"YAML","title":"0x04 2021 TOI 初選模擬賽 題解","breaks":true,"contributors":"[{\"id\":\"e573a1ba-d69b-44a7-a0d5-9d817fb786cc\",\"add\":11096,\"del\":1471}]"}