模競 I 題解

# 模競 I 題解 ---  麵團分割 (Dough) Source: LeetCode 2366 Prepared by Joylintp ---- 子任務 1 $a_N = 1$ ---- 滿足麵團長度遞增且最後一塊長度是 $1$ → 所有的麵團長度都要是 $1$ → 分割次數為 $(a_1-1) + (a_2-1) + \ldots + (a_N-1)$ ---- 子任務 2 $N = 2$ ---- 考慮兩種可能：$a_1 \le a_2$ 和 $a_1 > a_2$ ---- $a_1 \le a_2$：已滿足遞增條件，答案為 $0$ ---- $a_1 > a_2$：必須第一塊麵團分為每塊長度不超過 $a_2$ → 必須將 $a_1$ 分成 $\lceil \dfrac{a_2}{a_1} \rceil$ 塊 → 答案為 $\lceil \dfrac{a_2}{a_1} \rceil - 1$ ---- 子任務 3 $N \le 100, a_i \le 100$ 或許可以作奇怪 DP（但是不重要） ---- 子任務 4 無額外限制 ---- 對於每個 $1 < i \le N$ 設分割完第 $i$ 塊麵團後，最小的那段長度為 $x$ 則第 $i-1$ 塊麵團的每一塊長度都不能超過 $x$ → 至少要把第 $i-1$ 塊麵團分成 $\lceil \dfrac{a_{i-1}}{x} \rceil$ 段 ---- 為了下一塊麵團分盡量少段你希望讓每一塊麵團最短的那段長度盡量大 → 盡量平均地將麵團分為 $\lceil \dfrac{a_{i-1}}{x} \rceil$ 段 → 最小的那段麵團長度會是 $\lfloor a_{i-1} / \lceil \dfrac{a_{i-1}}{x} \rceil \rfloor$ ---- 注意： - 若麵團長度小於 $\lceil \dfrac{a_{i-1}}{x} \rceil$ 則不需進行分割，但須更新前一段麵團最小的長度 - $\lfloor \dfrac{a}{b} \rfloor$：`a / b` - $\lceil \dfrac{a}{b} \rceil$：`(a-1) / b + 1` ---  蜂巢清理 (Hive) Source: LeetCode 2290 Prepared by WiwiHo ---- 子任務 1 $R_u = 0, R_v = 0$ ---- 所有堆積灰塵的房間都在 $w$ 軸上 ---- - 若 $M < 2N+1$ 則中間一定有縫隙可以通過 → 答案為 $0$ - 若 $M = 2N+1$ 則需判斷 $S$ 跟 $T$ 是否在同一側 → 同一側答案為 $0$，不同側答案為 $1$ ---- 判斷在 $w$ 軸的哪側： $u$ 與 $v$ 方向皆為遠離 $w$ 軸 → $u+v > 0$ 與 $u+v < 0$ 分別代表 $w$ 軸兩側 ---- 處理六邊形座標：$w = -u + v$ → 將座標簡化成只剩下 $u$ 和 $v$ 軸 → $x = u-w, y = v+w$ ---- 子任務 2 $M=3N^2+3N-1$ ---- 所有 $S$ 和 $T$ 以外的房間皆堆積灰塵 → 答案為 $S$ 和 $T$ 之間的最短路徑長度 ---- 設原點座標為 $(0,0)$ $x$ 座標上下界為 $[-N, N]$ $y$ 座標上下界： - 若 $x \ge 0$，$y \in [-N, N-x]$ - 若 $x \le 0$，$y \in [-x-N, N]$ → 轉換為類似在二維長方形表格上問題 ---- 子任務 3 $N \le 10, M \le 10$ ---- 枚舉要打掃哪些房間，從 $S$ 進行 BFS 檢查是否能走到 $T$ 時間複雜度 $O(2^MN^2)$ （$|V| = 3N^2+3N+1, |E| < 6|V|$） ---- 子任務 4 $N \le 250$ 轉換成圖後進行 Dijkstra 尋找最短路時間複雜度 $O(N^2\log{N})$ ---- 子任務 5 無額外限制 ---- Dijkstra 利用 `priority_queue` 維護距離最小的節點每次更新時間複雜度 $O(\log{N})$ ---- 轉換成圖後，邊權只會是 $0$ 或 $1$ → `priority_queue` 中節點可能的距離只會是 $d$ 或 $d+1$ → 改用 `deque` 維護： - 若邊權為 $0$，則將節點加入 `deque` 前端 - 若邊權為 $1$，則將節點加入 `deque` 尾端每次更新時間複雜度 $O(1)$ 總時間複雜度 $O(N^2)$ ---  維度裂縫 (Rift) Prepared by WiwiHo ---- 在一張圖上找一條 $K$ 個點的路徑使邊權總和最大 ---- 這是一個 NP-Complete 問題 ---- 不過你亂做總是會有分數的 (?) ---- ## 測資 1 $K=3$ 枚舉中間那個點，找兩個它最大權重的鄰邊然後你就有 5 分了 ---- ## DAG 在一張 DAG 上找 $K$ 點的最長路徑只需要 $O(NK)$ 的時間 ---- random 拓樸排序，然後把邊定向假設最佳解是唯一的那麼你會有 $2/k!$ 的機率拿到最佳解 ---- $2/8! \approx 0.005\%$ $2/10! \approx 0.00005\%$ ---- ![](https://i.imgur.com/TJvsczH.png) ---- ```cpp= #include <bits/stdc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define iter(a) a.begin(), a.end() #define lsort(a) sort(iter(a)) #define eb(a) emplace_back(a) #define mp(a, b) make_pair(a, b) #define F first #define S second #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " "; pvaspace=true;\ b << pva;\ }\ b << "\n";} using namespace std; typedef long long ll; using pii = pair<int, int>; const ll MAX = 1000000000; int main(){ StarBurstStream int n, m, K; cin >> n >> m >> K; vector<vector<pii>> g(n + 1); for(int i = 0; i < m; i++){ int u, v, w; cin >> u >> v >> w; g[u].eb(mp(v, w)); g[v].eb(mp(u, w)); } mt19937 rnd(4235); int ans = 0; vector<int> arr; for(int tt = 0; tt <= 100000; tt++){ vector<int> tmp(n); iota(iter(tmp), 1); shuffle(iter(tmp), rnd); vector<vector<int>> dp(n + 1, vector<int>(K + 1, -MAX)); vector<vector<int>> f(n + 1, vector<int>(K + 1, -1)); vector<bool> vst(n + 1); int ansp = -1; for(int i : tmp){ vst[i] = true; dp[i][1] = 0; for(int j = 1; j < K; j++){ for(auto [v, w] : g[i]){ if(vst[v]) continue; if(dp[i][j] + w <= dp[v][j + 1]) continue; dp[v][j + 1] = dp[i][j] + w; f[v][j + 1] = i; } } if(dp[i][K] > ans){ ans = dp[i][K]; ansp = i; } } if(ansp == -1) continue; arr.clear(); int t = K; while(ansp != -1){ arr.eb(ansp); ansp = f[ansp][t]; t--; } } printv(arr, cout); return 0; } ``` ---- ## Color Coding 假設每個點都是 $K$ 種顏色的其中一種答案的路徑必須滿足 $K$ 個點顏色不同那你可以在 $O(N^22^K)$ 找到最佳解 ---- 假設最佳解唯一你會有 $K!/K^K$ 的機率拿到最佳解 ---- $8!/8^8 \approx 0.24\%$ $10!/10^{10} \approx 0.04\%$ ---- ```cpp= #include <bits/stdc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define iter(a) a.begin(), a.end() #define lsort(a) sort(iter(a)) #define eb(a) emplace_back(a) #define mp(a, b) make_pair(a, b) #define F first #define S second #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " "; pvaspace=true;\ b << pva;\ }\ b << "\n";} using namespace std; typedef long long ll; using pii = pair<int, int>; const ll MAX = 1000000000; int main(){ StarBurstStream int n, m, K; cin >> n >> m >> K; vector<vector<pii>> g(n + 1); for(int i = 0; i < m; i++){ int u, v, w; cin >> u >> v >> w; g[u].eb(mp(v, w)); g[v].eb(mp(u, w)); } mt19937 rnd(123123); uniform_int_distribution<int> ud(0, K - 1); int ans = 0; vector<int> arr; for(int tt = 0; tt <= 10000; tt++){ vector<int> clr(n + 1); for(int i = 1; i <= n; i++){ clr[i] = ud(rnd); } vector<vector<int>> dp(n + 1, vector<int>(1 << K, -MAX)); vector<vector<int>> f(n + 1, vector<int>(1 << K, -1)); for(int i = 1; i <= n; i++){ dp[i][1 << clr[i]] = 0; } for(int i = 0; i < (1 << K); i++){ for(int j = 1; j <= n; j++){ if(dp[j][i] == -MAX) continue; for(auto [v, w] : g[j]){ if(1 << clr[v] & i) continue; int nxt = 1 << clr[v] | i; if(dp[j][i] + w <= dp[v][nxt]) continue; dp[v][nxt] = dp[j][i] + w; f[v][nxt] = j; } } } int ansp = -1; for(int i = 1; i <= n; i++){ if(dp[i][(1 << K) - 1] > ans){ ans = dp[i][(1 << K) - 1]; ansp = i; } } if(ansp == -1) continue; int msk = (1 << K) - 1; arr.clear(); while(ansp != -1){ arr.eb(ansp); int nmsk = msk ^ (1 << clr[ansp]); ansp = f[ansp][msk]; msk = nmsk; } } printv(arr, cout); return 0; } ``` ---  赤紅薔薇 (Rose) Source: Codeforces 1535E Prepared by __shaun_0124 ---- ## Subtask 1 $Q \leq 5000$ 記錄每個節點的父節點每次發生第二種事件的時候找出 $v_i$ 到根節點的路徑然後暴力即可 ---- ## Subtask 2 $p_i=0$ 所有節點到根節點的路徑長度只有 2 ---- ## Subtask 3 $p_i \neq p_j$ 每個人的父節點都相異就是樹是一條鏈的意思 ---- 每次第二種事件都是從父節點開始往下拿令 $l$ 為父節點往下走第一個數量不是 0 的節點第二種事件其實就是在移動 $l$ $O(Q)$ ---- ## Subtask 4 所有的第一種事件都發生在所有的第二種事件前如果我們可以花 $O(P)$ 的時間找到根節點到 $v_i$ 的路徑上第一個數量不是 0 的節點那我們就只要花 $O(PQ)$ 的時間 ---- 蓋倍增表，二分搜 $O(Q \log Q)$ ---- ## Subtask 5 跟前一個子題不一樣的地方是這題會不斷加點 ---- 加點的時候也可以蓋倍增表！ ---- ```cpp= #include <bits/stdc++.h> using namespace std; #define int long long #define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d)) #define vi vector<int> #define pii pair<int,int> #define F first #define S second #define mkp make_pair const int MAX = 300001; const int lgMAX = 20; int q; int pa[MAX]; int anc[MAX][lgMAX]; int cnt[MAX], cost[MAX]; int dep[MAX]; int find_anc(int v){ /// find first anc. of v that still has gold if(cnt[v] == 0){ return -1; } int ret = v; for(int i=19; i>=0; i--){ if(cnt[ anc[ret][i] ] > 0){ ret = anc[ret][i]; } } return ret; } pii buy(int v, int buy_cnt){ /// try to buy buy_cnt units of gold from find_anc(v) /// return : <units bought, money spent> int Anc = find_anc(v); if(Anc==-1){ return mkp(0, 0); } int bought, spent; if(cnt[Anc] < buy_cnt){ bought = cnt[Anc]; cnt[Anc] = 0; } else{ bought = buy_cnt; cnt[Anc] -= bought; } spent = bought * cost[Anc]; return mkp(bought, spent); } signed main(signed argc, char* argv[]){ int pv_ans = 0; /// init cin>>q; pa[0] = 0; FOR(i, 0, 19, 1){ anc[0][i] = 0; } cin>>cnt[0]; cin>>cost[0]; FOR(i, 1, q, 1){ int type; int v, w; cin>>type; if(type==1){ cin>>pa[i]>>cnt[i]>>cost[i]; pa[i] ^= pv_ans; cnt[i] ^= pv_ans; cost[i] ^= pv_ans; anc[i][0] = pa[i]; FOR(j, 1, 19, 1){ anc[i][j] = anc[ anc[i][j-1] ][j-1]; } } else if(type==2){ cin>>v>>w; v ^= pv_ans; w ^= pv_ans; int bought = 0; int spent = 0; while(w > 0){ pii ret = buy(v, w); bought += ret.F; spent += ret.S; w -= ret.F; if(ret.F==0){ break; } } cout<<spent<<'\n'; pv_ans = spent % (1<<20); } } return 0; } ``` ---  夢幻之塔 (Tower) Source: 2022 宜蘭高中校內賽 pF Prepared by Ccucumber12 ---- 選擇一些高塔使得它們的高度是高低交錯且權重和最大 ---- ## Subtask 1 $h_i \leq 2$ 高度只有 1 和 2 1 一定是低，2 一定是高 $dp[i]=$ 以第 $i$ 個塔為選到的最右邊的塔的答案記錄目前 $h_i=1$ 和 $2$ 的最大 $dp[i]$ ---- ## Subtask 3 枚舉 $O(N2^N)$ ---- ## Subtask 4 $N \leq 1000$ $dp[0/1][i]=$ 以第 $i$ 個塔為選到的最右邊的塔且第 $i$ 個塔是低/高點的答案 $dp[0][i]=\max_{j h_i}\{ dp[1][j] \} + v_i$ $dp[1][i]=\max_{j < i \land h_j < h_i}\{ dp[0][j] \} + v_i$ $O(N^2)$ ---- ## Subtask 2 $h \leq 2 \times 10^5$ $mx[0/1][v]=$ 目前為止找到的最大 $dp[0/1][i]$ 滿足 $v_i=v$ 用 BIT / 線段樹維護，可以做到 $O(\log N)$ 轉移 $O(N \log N)$ ---- ## Subtask 5 離散化 AC ---- ```cpp= #include <iostream> #include <vector> #include <algorithm> using namespace std ; using ll = long long ; void discrete(vector<int> &v) { vector<int> tmp = v ; sort(tmp.begin(), tmp.end()) ; tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin()) ; for(auto &i:v) i = (lower_bound(tmp.begin(), tmp.end(), i) - tmp.begin() + 1) ; } const int N = 200010 ; int mxn = 1 ; ll dp0[4*N], dp1[4*N] ; void modify(ll arr[], int idx, ll val) { idx += mxn - 1 ; arr[idx] = max(arr[idx], val) ; while(idx > 1) { idx >>= 1 ; arr[idx] = max(arr[idx*2], arr[idx*2+1]) ; } } ll query(ll arr[], int l, int r, int lb, int rb, int idx) { if(l > r) return 0 ; if(l <= lb && rb <= r) return arr[idx] ; int mid = (lb + rb) >> 1 ; ll ans = 0 ; if(l <= mid) ans = max(ans, query(arr, l, r, lb, mid, idx*2)) ; if(mid < r) ans = max(ans, query(arr, l, r, mid+1, rb, idx*2+1)) ; return ans ; } int main() { ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ; int n ; cin >> n ; vector<int> h(n), v(n) ; for(int i=0; i<n; ++i) cin >> h[i] >> v[i] ; discrete(h) ; while(mxn < n) mxn <<= 1 ; for(int i=0; i<n; ++i) { modify(dp0, h[i], query(dp1, h[i]+1, mxn, 1, mxn, 1) + v[i]) ; modify(dp1, h[i], query(dp0, 1, h[i]-1, 1, mxn, 1) + v[i]) ; } cout << max(dp0[1], dp1[1]) << '\n' ; } ```