• 給一個 \(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\) 也很簡單

for (int i = 1; i < s.size(); ++i) {
    s[i] = s[i] == s[i-1] ? '0' : '1';
}

int ans = 0;
for (auto c : s) ans = (2 * ans + (c == '1')) % mod;
cout << ans % mod << "\n";

\(\color{lime}{AC}\) \((100/100)\)

• 給你 \(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\))

• 看起來只有修改的複雜度可以降低
• 每次的修改都是區間修改，查詢都是按照順序
• 是不是可以…

• 差分！

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

• 平面上一開始有三個點，之後有 \(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：找到一個在多邊形內部的點，再把所有點按照極角排序

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\) 出現
• 請仔細閱讀題敘，有不少人沒注意到所有點都會出現在凸包上

• 給你一棵 \(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

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）

• 有 \(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

• \(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