2021 師大附中暑期資訊培訓模擬競賽 I 題解

# 模擬競賽 I 題解 ## 2021 師大附中暑期資訊培訓 joylintp / WiwiHo ---  直播循環 (Cycle) 來源: [Codeforces 1041C](https://codeforces.com/problemset/problem/1041/C) 測資: joylintp 題敘: joylintp ---- ### 直播循環 - Subtask 1 $r=0$ → 不用休息 → 所有遊戲都可以在第一個循環直播 → $k=1,x_i=1$ 3 / 100 ---- ### 直播循環 - Subtask 3 $n \le 10$ → 枚舉直播遊戲的順序 → 盡量讓遊戲可以在同一個循環內直播 → $O(n! \times n)$ 9 / 100 ---- ### 直播循環 - Subtask 2 $n = s$ → 每天都有一種遊戲要玩 → 第一個循環玩第 $1,1+r+1,1+2r+2,\dots$ 天的遊戲 → 第二個循環玩第 $2,2+r+1,2+2r+2,\dots$ 天的遊戲 → $O(n)$ 13 / 100 ---- ### 直播循環 - Subtask 2 #### 貪心法 ---- ### 直播循環 - Subtask 4 每次盡量選擇還沒玩過的遊戲中 $a_i$ 最小的 → $O(n)$ 迴圈尋找可玩的遊戲 → 總複雜度 $O(n^2)$ 18 / 100 ---- ### 直播循環 - Subtask 5 ~~→ $O(n)$ 迴圈尋找可玩的遊戲~~ → `set`、`priority_queue` $O(\log{n})$ 維護 → 總複雜度 $O(n\log{n})$ 100 / 100 ---- ```cpp= #include<bits/stdc++.h> using namespace std; #define MP make_pair #define F first #define S second signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m, d; cin >> n >> m >> d; vector<pair<int, int>> a(n); for (int i = 0; i < n; i++) cin >> a[i].F, a[i].S = i; sort(a.begin(), a.end()); vector<int> ans(n); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for (int i = 0; i < n; i++) if (pq.empty() || a[i].F - pq.top().F < d + 1) ans[a[i].S] = pq.size() + 1, pq.push(MP(a[i].F, pq.size() + 1)); else ans[a[i].S] = pq.top().S, pq.pop(), pq.push(MP(a[i].F, ans[a[i].S])); cout << pq.size() << '\n'; for (int i : ans) cout < 兔田彩券 (Lottery) 靈感來源: [JOI 2021 Final Round pC](https://oj.uz/problem/view/JOI21_ho_t3) 測資: WiwiHo 題敘: joylintp ---- ## 題目大意有 $m$ 個 pair $(a_i,b_i)$ 對於每筆詢問 $(l_i,r_i,s_i,t_i)$ 求有幾個 $j$ 滿足 $l_i \leq a_j \leq r_i \land s_i \leq b_j \leq t_i$ 或 $l_i \leq b_j \leq r_i \land s_i \leq a_j \leq t_i$ ---- ## Subtask 1 $n,m,q \leq 500$ 對於每一個詢問把所有 pair 檢查一次是否符合條件就好了 $O(mq)$ ---- ### 常見錯誤 1. 同一個算到兩次 2. 把「或」當成「且」 ---- ## Subtask 2 $n \leq 100$，$q \leq 10000$ $n$ 很小？ pair 只有 $O(n^2)$ 種而已數每一種 pair 出現了幾次詢問的時候，找符合條件的 pair $O(m + n^2q)$ ---- ## Subtask 3 $l_i \leq r_i < s_i \leq t_i$ 如果把每一種 pair 出現的數量存在一個表格上那詢問其實是在問一個矩形區域的和假設 $(i,j)$ 出現 $c[i][j]$ 次二維前綴和：$sum[i][j]= \sum_{i'=1}^i \sum_{j'=1}^j c[i'][j']$ ---- $\sum_{i=l}^{r} \sum_{j=s}^t c[i][j] = sum[r][t] \\ - sum[l-1][t] - sum[r][s-1] + sum[l-1][s-1]$ 預處理 $sum$，詢問只要 $O(1)$ 的時間 $O(m + n^2 + q)$ ---- ## Subtask 4 為什麼上一個 subtask 的 code 不能過這個？因為會算到重複的如果 $l_i \leq a_j \leq r_i \land s_i \leq b_j \leq t_i$ 和 $l_i \leq b_j \leq r_i \land s_i \leq a_j \leq t_i$ 同時滿足，$j$ 就會被算到兩次 ---- 誰會被算到兩次？ $\max(l_i,s_i) \leq a_j,b_j \leq \min(r_i,t_i)$ $j$ 就會被算到兩次把這個區域扣掉就好 ---- ```cpp= #include <bits/stdc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; int main(){ StarBurstStream int n, m; cin >> n >> m; vector<vector<int>> a(n + 1, vector<int>(n + 1)); for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; if(u > v) swap(u, v); a[u][v]++; a[v][u]++; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++) a[i][j] += a[i][j - 1]; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++) a[j][i] += a[j - 1][i]; } auto calc = [a](int x1, int y1, int x2, int y2){ return a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1]; }; int q; cin >> q; while(q--){ int l, r, s, t; cin >> l >> r >> s >> t; int tl = max(l, s); int tr = min(r, t); int ans = calc(l, s, r, t); if(tl <= tr) ans -= calc(tl, tl, tr, tr) / 2; cout << ans << "\n"; } return 0; } ``` ---  魔法師測驗 (Mage) 來源: [CF 1101D](https://codeforces.com/problemset/problem/1101/D) 測資: joylintp 題敘: joylintp ---- ### 魔法師測驗 - Subtask 1 $m_1=m_2=\ldots=m_n$ → 若 $m_1=1$ 則答案為 $0$（和諧度必為 $1$） → 若 $m_1 \ne 1$ 則答案為樹直徑（和諧度必不為 $1$） 8 / 100 ---- ### 魔法師測驗 - Subtask 2, 6 $n \le 1000$ → 枚舉起點 → $O(n)$ DFS 看能走多遠 → 總複雜度 $O(n^2)$ (6 + 14) / 100 ---- ### 魔法師測驗和諧度不為 $1$ → 最大公因數大於 $1$ → 所有數字至少有一個共同質因數 ---- ### 魔法師測驗 - Subtask 5 $m_i \le 100$ → 枚舉質數（至多 $25$ 個） → 對每個質數建出子圖 → 找所有子圖中最長的樹直徑 → 總複雜度 $O(n \times 25)$ 16 / 100 ---- ### 魔法師測驗 - Subtask 7 $m_i \le 2 \times 10^5$ → 質數有 $17984$ 個 → 對每個質數建出子圖 → TLE ---- ### 魔法師測驗 - Subtask 7 $m_i \le 2 \times 10^5$ → $2 \times 3 \times 5 \times 7 \times 11 \times 17 > 2 \times 10^5$ → 每個節點的相異質因數不會超過 $5$ 個 → 樹 DP ---- ### 魔法師測驗 - Subtask 7 #### 樹 DP 記錄 * 每個節點回傳各質因數可往下延伸多長轉移 * 繼續延伸子節點質因數的長度 * 將兩個子節點質因數的長度接起來總複雜度 $O(n\log^2{m})$ 100 / 100 ---- ```cpp= #include<bits/stdc++.h> using namespace std; #define F first #define S second int ans; vector<bool> pfac(200001, true), vis; vector<int> prime, a; vector<vector<int>> edge; map<int, int> dfs(int u) { vis[u] = true; map<int, int> sa; for (int i : prime) { if (i * i > a[u]) break; while (a[u] % i == 0) sa[i] = 1, a[u] /= i; } if (a[u] != 1) sa[a[u]] = 1; map<int, pair<int, int>> sb; for (int i : edge[u]) if (!vis[i]) { map<int, int> mp = dfs(i); for (auto p : mp) if (sa.count(p.F)) { sa[p.F] = max(sa[p.F], p.S + 1); if (p.S > sb[p.F].F) sb[p.F].S = sb[p.F].F, sb[p.F].F = p.S; else if (p.S > sb[p.F].S) sb[p.F].S = p.S; else; } } for (auto p : sa) ans = max(ans, p.S); for (auto p : sb) ans = max(ans, p.S.F + p.S.S + 1); return sa; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); for (int i = 2; i <= 200000; i++) { if (pfac[i]) prime.push_back(i); for (int j : prime) { if (i * j > 200000) break; pfac[i * j] = false; if (i % j == 0) break; } } int n; cin >> n, vis.resize(n + 1), a.resize(n + 1), edge.resize(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; int u, v; for (int i = 1; i < n; i++) cin >> u >> v, edge[u].push_back(v), edge[v].push_back(u); dfs(1); cout << ans << '\n'; return 0; } ``` ---  刷怪塔 (Monster) 來源: [Google Code Jam 2020 Round 2 pA](https://codingcompetitions.withgoogle.com/codejam/round/000000000019ffb9/00000000003384ea) 測資: joylintp 題敘: joylintp ---- ### 刷怪塔 - Subtask 3 $a,b \le 1000$ → 選擇刷怪塔的次數至多 $\sqrt{a+b}$ 次 → 模擬每次選擇刷怪塔 → 總時間複雜度 $O(T\sqrt{a+b})$ 12 / 100 ---- ### 刷怪塔 - Subtask 1 $a=0$ → 只會打第二座刷怪塔的怪物 → $b \ge \frac{l(l+1)}{2}$ → 解不等式或二分搜最大值 → 總時間複雜度 $O(T)$ 或 $O(T\log{b})$ 8 / 100 ---- ### 刷怪塔 - Subtask 2 $a=b$ → 觀察到在怪物數量足夠的情況下，奇數一定選擇第一座刷怪塔，偶數一定選擇第二座 → $a \ge 1+3+\ldots+(2k+1) = (k+1)^2$ $b \ge 2+4+\dots+(2k) = (k+1)^2 + k + 1$ → 解不等式或二分搜最大值 → 總時間複雜度 $O(T)$ 或 $O(T\log{b})$ 21 / 100 ---- ### 刷怪塔 - Subtask 4 將較多的那座擊殺到怪物數量不超過另一座接下來兩座刷怪塔必定會輪流使用 → 作法類似 Subtask 2 → 總時間複雜度 $O(T)$ 或 $O(T\log{b})$ 100 / 100 ---- ```cpp= #include<bits/stdc++.h> using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int T; cin >> T; for (int i = 1; i <= T; i++) { long long A, B; cin >> A >> B; bool swp = (A <= B); if (A < B) swap(A, B); long long l = 0, r = 2e9; while (l != r) { long long m = (l + r) / 2; if (m * (m + 1) / 2 > A - B) r = m; else l = m + 1; } A -= l * (l - 1) / 2; if (A > B || (A == B && !swp)) swap(A, B), swp = !swp; long long x = l - 1; if (B < x + 1) { if (swp) swap(A, B); cout << x << ' ' << A << ' ' << B << '\n'; } else if (A < x + 2) { B -= x + 1; if (swp) swap(A, B); cout << x + 1 << ' ' << A << ' ' << B << '\n'; } else { l = x + 2, r = 2e9; long long Aa = A, Ba = B; while (l != r) { long long m = (l + r) / 2; long long Al = m, Bl = m; if (Al % 2 == x % 2) Bl--; else Al--; long long At = (Al + x + 2) * (Al - x) / 4, Bt = (Bl + x + 1) * (Bl - x + 1) / 4; if (A < At || B < Bt) r = m; else l = m + 1, Aa = A - At, Ba = B - Bt; } if (swp) swap(Aa, Ba); cout << l - 1 << ' ' << Aa << ' ' << Ba << '\n'; } } return 0; } ``` ---  時空旅人之爭 (Time) 來源: 原創 測資: WiwiHo 題敘: joylintp ---- ## 題目大意給一棵樹，複製人大軍會從節點 1 開始擴散，每 2 秒擴散一個節點有 $Q$ 筆詢問，詢問求從入侵的時間點開始，從 $s_i$ 走到 $t_i$ 的路上至少要經過幾個有複製人大軍的節點 ---- 顯然就是走得越快越好，所以直接走 $s_i$ 到 $t_i$ 的簡單路徑 Kronii 到達 $v$ 的時間：$dis(s_i, v)$ 複製人大軍到達 $v$ 的時間： $2 \times dis(1, v)$ 答案要求有幾個 $v$ 滿足 $dis(s_i,v) \geq 2 \times dis(i,v)$ ---- ## Subtask 1 $n,q \leq 1000$ 暴力檢查 $O(nq)$ ---- ## Subtask 2 $\forall 1 \leq i < n, v_i = u_{i+1}$ 就是這個樹是一條鏈的意思如果 $s_i,t_i$ 都在 $1$ 的同一側那麼靠近 $1$ 的那邊可能會有一段連續的符合條件的節點也就是這條鏈上會有一邊符合條件、一邊不符合二分搜找交界點 ---- 如果 $s_i,t_i$ 在 $1$ 的兩側那麼符合條件的節點會是中間連續的一段如果把 $1$ 左右分開看就和上一種狀況一樣了 $O(n + q \log n)$ ---- ## Subtask 3 除了節點 1 以外，每個節點度數最多 2 也就是說這個樹是從 1 往外伸的一堆鏈只看 $s_i$ 和 $t_i$ 所在的鏈就跟 Subtask 2 一樣了 ---- ## Subtask 4 Subtask 2,3 都是「把 $s_i$ 到 $t_i$ 的路徑，以最靠近 $1$ 的節點為中心把這條路徑切成兩半」，而切出來的兩條路徑上，都是有一邊的點符合條件（靠近中心的那邊）、一邊不符合 $s_i$ 到 $t_i$ 的路徑上離 $1$ 最近的點就是他們的 LCA （以 $1$ 為根）然後就跟前面一樣了可以用倍增法二分搜 ---- ```cpp= #include <bits/stdc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define eb(a) emplace_back(a) using namespace std; vector<vector<int>> g; vector<int> in, out, dpt; int ts = 0; vector<vector<int>> anc; void dfs(int now, int p, int d){ in[now] = ts++; dpt[now] = d; anc[0][now] = p; for(int i : g[now]){ if(i == p) continue; dfs(i, now, d + 1); } out[now] = ts++; } bool isAnc(int a, int b){ return in[a] <= in[b] && out[a] >= out[b]; } int getLCA(int a, int b){ if(isAnc(a, b)) return a; if(isAnc(b, a)) return b; for(int i = 19; i >= 0; i--){ if(!isAnc(anc[i][a], b)) a = anc[i][a]; } return anc[0][a]; } int getDis(int a, int b){ int lca = getLCA(a, b); return dpt[a] + dpt[b] - 2 * dpt[lca]; } bool check(int s, int now){ return getDis(s, now) < dpt[now] * 2; } void solve(){ int s, t; cin >> s >> t; int lca = getLCA(s, t); if(check(s, lca)){ cout << "0\n"; return; } int ans = 0; int now = s; for(int i = 19; i >= 0; i--){ if(check(s, anc[i][now])) now = anc[i][now]; } ans += dpt[now] - dpt[lca] + !check(s, s); now = t; for(int i = 19; i >= 0; i--){ if(check(s, anc[i][now])) now = anc[i][now]; } ans += dpt[now] - dpt[lca] + !check(s, t); ans--; cout << ans << "\n"; } int main(){ StarBurstStream int n; cin >> n; g.resize(n + 1); in.resize(n + 1); out.resize(n + 1); dpt.resize(n + 1); anc.resize(20, vector<int>(n + 1)); for(int i = 0; i < n - 1; i++){ int u, v; cin >> u >> v; g[u].eb(v); g[v].eb(u); } int q; cin >> q; dfs(1, 1, 0); for(int i = 1; i < 20; i++){ for(int j = 1; j <= n; j++){ anc[i][j] = anc[i - 1][anc[i - 1][j]]; } } for(int i = 0; i < q; i++){ solve(); } return 0; } ```