---
# System prepended metadata

title: 0x04 2021 TOI 初選模擬賽 題解
tags: [Editorial]

---

---
title: 0x04 2021 TOI 初選模擬賽 題解
tags: Editorial
---

## 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 分回家 >////<
（不過搞不好今年又出更多題）