模競 II 題解

# 模競 II 題解 ---  羽衣光線 (Beam) Source: JAG Practice Contest for ACM-ICPC Asia Regional 2017 pA Prepared by Joylintp ---- 子任務 1 所有發射器皆位於所有接收器的左側 ---- 考慮舞台位置 $i$（0-base）： - $i \le N$，如 `>>*>)))`：答案為 $i$ - $i > N$，如 `>>>)*))`：答案為 $2N-i$ ---- 子任務 2 $N \le 100$ ---- 枚舉 $(l,r)$，$O(N)$ 檢查區間內容時間複雜度 $O(N^3)$ ---- 子任務 3 $N \le 10000$ ---- 枚舉 $l$，在更新 $r$ 的同時檢查目前區間是否符合規則時間複雜度 $O(N^2)$ ---- 子任務 4 無額外限制 ---- 其實就是括號匹配然後檢查 `*` 被包在幾組 `>)` 裡面 ---- 輸入的字串合法 → `*` 左邊出現多了幾個 `>`，右邊就會多幾個 `)` → 答案為 `*` 左邊 `>` 的數量減掉 `)` 的數量 ---  逃離禁區 (Escape) Source: CS Academy Tree Node Distance Prepared by WiwiHo ---- 給你一棵樹有兩個人 A, B 在不同節點上你可以： - 叫某人往根節點走一個點 - 叫某人回去起點 - 詢問兩人是否在同一個點求他們的起點距離 ---- 其實只有起點到 LCA 的距離和 LCA 到根的距離是重要的假設分別是 $a,b,c$ ---- ## Subtask 1 走到根後可以知道深度是多少先把兩個人移到一樣的深度然後每次都讓兩人一起往上移並判斷是否在同一個點 ---- ## 滿分一樣先找到他們的深度差枚舉 $2^i$，讓 A 走到起點往上 $2^i$ 格接著讓 $B$ **從他的起點**往上走 $2^{i+1}$ 格並且每走一步（在起點也要）都檢查一次是不是在同個點 ---- 會相遇的時候要滿足 $2^i \geq a$ $2^{i+1} \geq b$ $a-2^i \geq b-2^{i+1}$ i.e. $2^i \geq b-a$ ---- $a,b,b-a \leq D$ $\implies D \leq 2^i$ ---- A 的移動次數：$2^i$ B 的移動次數：$2^1+2^2+\dots+2^{i+1}=2^{i+2}-2$ 總次數 $=2^i+2(2^{i+2}-2)+2i \approx 18D$ 最後找 LCA 要花 $\frac{2}{3}D$ ---- ```cpp= #include "Escape.h" #include <bits/stdc++.h> using namespace std; int find_distance(){ int a = 0, b = 0; for(int i = 1; ; i *= 2){ for(int j = 0; j b){ ans = a - b; for(int i = 0; i < a - b; i++) move_a(); } else if(b > a){ ans = b - a; for(int i = 0; i 電網規劃 (Grid) Source: Codeforces 1245D Prepared by Joylintp ---- 子任務 1 $x_i=1, d=1$ ---- 所有的地區都在一直線上，且各地設置電纜難度相同 → 若要設置電纜，只會與相鄰的城市連接 → 將所有城市依照 $y$ 座標排序 ---- 設 $dp_{i,0}$ 為第 $i$ 個地區沒有電但與後面地區連接的最小花費設 $dp_{i,1}$ 為第 $i$ 個地區有電的最小花費 ---- $dp_{i,0} = dp_{i-1,0}+w_{i,i+1}$ $dp_{i,1} = \min(dp_{i-1,1}+w_{i-1,i},p_{i})$ 答案為 $dp_{N,1}$ 時間複雜度為 $O(N)$ （其實跟滿分解沒什麼關連） ---- 子任務 2 $N \le 4$ ---- $N \le 4$ → 至多只會有 $\dfrac{N(N-1)}{2} = 6$ 條邊 → 枚舉要蓋的電纜，並選擇每個連通塊中最便宜的地方蓋發電廠時間複雜度 $O(2^{N^2}N^2)$ ---- 子任務 3 $N \le 1000, d_i \le 100$ 只有一個地區 $r$ 的 $p_r=1$，其他的 $p_i=10^9$ ---- 蓋發電廠很貴，所以在最便宜的地區蓋就好剩下地區用電纜連接 → 最小生成樹 Kruskal / Prim 時間複雜度 $O(N^2\log{N})$ ---- 子任務 4 $N \le 1000$ ---- 想像有一個已經蓋好的總發電廠在地區 $0$ ---- 若要蓋一個新的發電廠在 $i$，其實是設置成本為 $p_i$ 的電纜從 $0$ 到 $i$ → 只要 $N+1$ 個地區都連通即可 → 最小生成樹 Kruskal 時間複雜度 $O(N^2\log{N})$ ---- 子任務 5 無額外限制 ---- 在完全圖上作最小生成樹用 Prim 比較快時間複雜度 $O(N^2)$ ---  笑口常開 (Laugh) Source: NTU Preliminary 2022 pI Prepared by WiwiHo ---- ![](https://i.imgur.com/X8dbQ4B.png) ---- ## Subtask 1 $N \leq 2$ 不管怎麼選都是好的輸出 $2^N-1$ ---- ## Subtask 2 $N \leq 20$ 位元枚舉 $O(N2^N)$ ---- ## Subtask 3,4 $N \leq 500$ 震盪波可以以在中間的最大最小值為中心分成兩半我們把兩半分開算（中間同時屬於左半和右半） $dp[i][j]=$ 左半最後兩個是 $i,j$ 的數量（所以 $i$ 和 $j$ 一個是最大值一個是最小值） ---- 以下 $k s_j,\ dp[i][j]=\sum_{s_i>s_k>s_j} dp[k][i]\\] $O(N^3)$ ---- ## 滿分固定 $i$，枚舉 $j$ ---- 先考慮 $s_i<s_j$ 的 case $dp[i][j]$ 的轉移來源有 $dp[k][i]$ 的條件是 $k<i$、$s_i<s_k<s_j$ 如果按照 $s_j$ 遞增的順序枚舉我們就可以用一個變數 $sum$ 記錄目前看到的 $j<i$ 的 $dp[j][i]$ 和遇到 $i<j$ 就把 $dp[i][j]$ 加上 sum $s_i>s_j$ 的同理 $O(N^2)$ ---- ```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() using namespace std; typedef long long ll; const ll MOD = 1000000007; int main(){ StarBurstStream int n; cin >> n; vector<ll> s(n + 1); for(int i = 1; i <= n; i++) cin >> s[i]; vector<vector<ll>> dp1, dp2; auto solve = [&](vector<vector<ll>>& dp){ dp.resize(n + 1, vector<ll>(n + 1)); vector<int> pos(n + 1); for(int i = 1; i <= n; i++) pos[s[i]] = i; for(int i = 1; i <= n; i++){ ll sum = 1; for(int v = s[i] + 1; v <= n; v++){ int j = pos[v]; //cerr << "test " <= 1; v--){ int j = pos[v]; //cerr << "test " << i << " " << j << " " << sum << "\n"; if(j < i){ sum += dp[j][i]; sum %= MOD; } else{ dp[i][j] += sum; dp[i][j] %= MOD; } } } }; solve(dp1); reverse(s.begin() + 1, s.end()); solve(dp2); /*for(int i = 1; i <= n; i++) printv(dp1[i], cerr); for(int i = 1; i <= n; i++) printv(dp2[i], cerr);*/ ll ans = n; for(int i = 1; i <= n; i++){ for(int j = i + 1; j <= n; j++){ ans += dp1[i][j] * dp2[n - j + 1][n - i + 1] % MOD; ans %= MOD; } } cout << ans << "\n"; return 0; } ``` ---  密碼設置 (Password) Prepared by __shaun_0124 ---- [詳細文字版](https://hackmd.io/@IBuVwIraTIWJeB88sQHXpw/Hk7levjRc) ---- ## Subtask 1 $N,M \leq 4, C=1$ 暴搜？ $2^{16}=65536$ ---- ## Subtask 2 $N,M \leq 20$ 固定首項係數所在的位置可以隨便填之間任的位置數量就確定了 ---- $\begin{bmatrix} 1 & 0 & 0 & ? \\ 0 & 1 & 0 & ? \\ 0 & 0 & 1 & ? \end{bmatrix}$ $\begin{bmatrix} 1 & 0 & ? & 0 \\ 0 & 1 & ? & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$ $\begin{bmatrix} 1 & 0 & ? & ? \\ 0 & 1 & ? & ? \\ 0 & 0 & 0 & 0 \end{bmatrix}$ ---- 假設第 $i$ 列的首項在 $a_i$ 如果有 $k$ 列不是 0 那麼第 $i$ 列的問號數量是 $M-a_i-(k-i)$ ---- 枚舉哪些首項位置要用 $O(2^M \times M)$ ---- ## Subtask 3 $N=1$ 枚舉首項係數要放在哪裡 ---- ## Subtask 4 考慮 DP $dp[i][j]=$ 有 $i$ 列非 0 列，第一列的首項係數在**倒數**第 $j$ 行的方法數轉移時，考慮在**上面**加一列如果新列的首項在倒數第 $k$ 行那麼就有 $k-i$ 個問號 $O(N^3)$ ---- ## Subtask 5 $dp[i][j]=(\sum_{k=i-1}^{j-1} dp[i-1][k]) \times (C+1)^{j-i}$ 左邊可以前綴和右邊可以預處理滾動陣列 ---- ```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)) const int MOD = 1000000007; const int MAX = 5010; int n, m, c; int fpow[MAX]; int dp[2][MAX]; int res; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m>>c; fpow[0] = 1; FOR(i, 1, m, 1){ fpow[i] = (fpow[i-1] * (c+1)) % MOD; } dp[0][0] = 1; res = 1; FOR(i, 1, n, 1){ int cur = i % 2; int sum = 0; FOR(j, i, m, 1){ sum = (sum + dp[1-cur][j-1]) % MOD; dp[cur][j] = (sum * fpow[j-i]) % MOD; res = (res + dp[cur][j]) % MOD; } } cout<<res<<'\n'; return 0; } ```