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

# 模擬競賽 II 題解 ## 2021 師大附中暑期資訊培訓 emanlaicepsa / joylintp / WiwiHo ---  機器鴨 (Duck) 來源: 原創 測資: WiwiHo 題敘: joylintp ---- ## 題目大意有兩個序列 $a$、$b$ 從起點開始，你要走 $n$ 步第 $i$ 步會直線移動 $(a_i,b_i)$ 的距離把它們重新排列，滿足你走的路線不自交 ---- 如果 $a_i$ 總和或 $b_i$ 總和不是 0 就無解 ---- ## Subtask 1 $n=3$ 如果你隨便弄出 3 個向量如果這 3 個向量拼不出三角形唯一的可能就是它們互相平行否則，這 3 個向量可以以任意順序排列枚舉所有 $a$ 的排列檢查每個向量 $(a_i,b_i)$ 是否平行 ---- ## Subtask 2 $n \leq 6$ 枚舉 $a$ 的排列和 $b$ 的排列的搭配然後檢查能不能當答案 $O(n! \times n! \times n^2)$ ---- ## Subtask 3 $\forall 1 \leq i < n,\ b_i=1$ 如果把 $a$ 由小到大排序那麼前 $n-1$ 步會走出一個下凸包的形狀最後一步會直接走回原點所以這樣走出來的一定是一個凸多邊形 $O(n \log n)$ ---- ## Subtask 4 在 Subtask 1 中我們用「是不是全部平行」來判斷能不能當解事實上，只要有 $n$ 個向量至少有一對不平行那就可以用它們做出一個合法路線 ---- 在 Subtask 3 中我們做出了一個凸多邊形只要把這 $n$ 個向量極角排序就可以得到凸多邊形了 ---- 剩下的問題就是怎麼找這 $n$ 個向量配出 $n$ 個全部平行的向量的方法數遠低於總方案數 random 會是好的 ---- 可不可以不要 random？官解作法：把 $a$ 按絕對值由小到大排序 $b$ 按絕對值由大到小排序 ---- 對於 $|a_i| < |a_j|$ 肯定有 $\frac{|a_i|}{|b_i|} \neq \frac{|a_j|}{|b_j|}$ 因為 $|b_i| \geq |b_j|$ 得出 $\left\lvert\frac{a_i}{b_i}\right\rvert \neq \left\lvert\frac{a_j}{b_j}\right\rvert$ 至於 $|a_i| = |a_j|$ 因為 $a_i$ 皆相異，這最多只有兩個而已而 $n \geq 3$ 所以肯定有解 $O(n \log n)$ ---- 一些會錯的解： - 照輸入順序原封不動輸出 - 純 random 輸出 - 把 $a$、$b$ 由小排到大湊向量 - 把 $a$ 由小排到大、$b$ 由大排到小湊向量 ---- 為什麼 $n$ 那麼小？因為我不會寫 checker ---- ```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 mp(a, b) make_pair(a, b) #define F first #define S second using namespace std; typedef long long ll; using pll = pair<ll, ll>; int main(){ StarBurstStream int n; cin >> n; vector<ll> a(n), b(n); ll asum = 0, bsum = 0; for(int i = 0; i < n; i++) cin >> a[i], asum += a[i]; for(int i = 0; i < n; i++) cin >> b[i], bsum += b[i]; if(asum != 0 || bsum != 0){ cout << "No\n"; return 0; } sort(iter(a), [](ll a, ll b){ return abs(a) < abs(b); }); sort(iter(b), [](ll a, ll b){ return abs(a) > abs(b); }); vector<pll> v(n); for(int i = 0; i < n; i++) v[i] = mp(a[i], b[i]); auto comp = [](pll a, pll b){ return atan2(a.S, a.F) < atan2(b.S, b.F); }; sort(iter(v), comp); cout << "Yes\n"; for(int i = 0; i < n; i++){ cout << v[i].F << " " << v[i].S << "\n"; } return 0; } ``` ---  惡地之路 (Highway) 來源: [109 學年度資訊學科能力競賽臺南一中校內複選 pC](https://toj.tfcis.org/oj/pro/568/) 測資: emanlaicepsa 題敘: joylintp ---- ## 題目大意給一張圖令 $s$ 到節點 $i$ 走 $k$ 步的最短距離是 $d(i,k)$ 對於每個 $i$ 求 $\min \{ d(i,k) \times k \}$ ---- ## Subtask 1,2,3,4 暴力走所有可能路徑 - Subtask 1：最多 $O(n!)$ 條路徑 - Subtask 2：圖是鏈狀，只有 $O(n)$ 條路徑 - Subtask 3：圖是樹，只有 $O(n)$ 條路徑 - Subtask 4：圖是環，只有 $O(n)$ 條路徑 ---- ## Subtask 5,6 把每個節點都複製 $n$ 份如果本來有一條邊是 $(u,v)$ 那就對所有 $1 \leq i < n$ 蓋一條邊是 $u$ 的第 $i$ 個點到 $v$ 的第 $i+1$ 個點（有向）還有 $v$ 的第 $i$ 到 $u$ 的第 $i+1$ 這樣走到某個節點的第 $i$ 個點的路徑長度一定是 $i-1$ $n^2$ 個點、$2nm$ 個邊做最短路徑 $O((n^2+m) \log n)$ ---- ## Subtask 7 $dp[i][j]=$ 走 $i$ 步到 $j$ 的最短路 \\[dp[i][j]=\min_{(k,j) \in E} \{ dp[i-1][k] + dis(k,j) \}\\] $O(n(n+m))$ DP ---- ```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) #define mp(a, b) make_pair(a, b) #define F first #define S second using namespace std; typedef long long ll; using pll = pair<ll, ll>; int main(){ StarBurstStream int n, m, s; cin >> n >> m >> s; vector<vector<pll>> g(n + 1); for(int i = 0; i < m; i++){ int u, v, p; cin >> u >> v >> p; g[u].eb(mp(v, p)); g[v].eb(mp(u, p)); } vector<ll> dp(n + 1, 1LL << 60); dp[s] = 0; vector<ll> ans(n + 1, 1LL << 60); ans[s] = 0; for(int i = 1; i <= n; i++){ vector<ll> dp2(n + 1, 1LL << 60); for(int j = 1; j <= n; j++){ for(auto e : g[j]){ dp2[e.F] = min(dp2[e.F], dp[j] + e.S); } } dp = dp2; for(int j = 1; j <= n; j++){ if(dp[j] < (1LL << 60)) ans[j] = min(ans[j], dp[j] * i); } } for(int i = 1; i <= n; i++) cout << ans[i] << " "; cout << "\n"; return 0; } ``` ---  調色盤 (Palette) 來源: [2020 全國模擬賽公開組 pD](https://codeforces.com/gym/102891/problem/D) 測資: WiwiHo 題敘: joylintp ---- ## 題目大意給你一個序列 $c$ 有 $q$ 筆詢問，每筆詢問給 $l, r$ 求有幾個在 $[l,r]$ 裡的區間 $[L,R]$ 滿足 $[L,R]$ 裡的數字全距不超過 $k$ ---- ## Subtask 1 $k=10^6$ 所有區間的全距都不會超過 $k$ 詢問是 $l,r$ 令 $len=r-l+1$ 答案是 $\frac{len(len+1)}{2}$ ---- ## Subtask 2 $n,q \leq 50$ 對每個詢問枚舉 $O(n^2)$ 個區間暴力掃一遍計算全距 $O(n^3q)$ ---- ## Subtask 3 $n,q \leq 500$ 對每個詢問枚舉區間的左端點然後枚舉右端點的時候可以一邊算區間內的最大最小值 $O(n^2q)$ ---- ## Subtask 4 $n,q \leq 10^4$ 先找到以每個位置為右界時區間的左界最遠可以到哪對每個詢問，枚舉右界可以知道能取的左界有幾個 $O(nq)$ ---- ## Subtask 5,6 把詢問照右界排序從左邊掃到右邊計錄「每個位置當左界時，有幾個目前已經掃過的位置可以當右界」令這個數字是 $r(i)$ ---- 如果目前掃到的這個位置是 $i$ 它當右界時，最遠的左界在 $l(i)$ 那麼就把 $r(l(i)..i)$ 都加上 1 處理右界在目前位置的詢問直接詢問 $r(l..r)$ 的和即可 ---- $r(i)$ 維護可以用 BIT $l(i)$ 計算可以用單調隊列或是二分搜配 Sparse Table 求最大最小值複雜度是 $O((n+q) \log n)$ 如果你在二分搜的時候是配線段樹複雜度會是 $O(n \log^2 n + q \log n)$ 可能 TLE，只能過 Subtask 5 ---- ```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) #define pob pop_back() #define pof pop_front() #define mp(a, b) make_pair(a, b) #define F first #define S second using namespace std; typedef long long ll; using pii = pair<int, int>; int lowbit(int x){ return x & -x; } struct BIT{ vector<ll> bit; void modify(int x, ll v){ for(; x < bit.size(); x += lowbit(x)){ bit[x] += v; } } ll query(int x){ ll ans = 0; for(; x > 0; x -= lowbit(x)){ ans += bit[x]; } return ans; } }; struct SUMBIT{ BIT bit1, bit2; void modify(int l, int r, ll v){ if(l > r) return; bit1.modify(l, v); bit1.modify(r + 1, -v); bit2.modify(l, l * v); bit2.modify(r + 1, (r + 1) * (-v)); } ll query(int x){ return (x + 1) * bit1.query(x) - bit2.query(x); } ll query(int l, int r){ return query(r) - query(l - 1); } }; int main(){ StarBurstStream int n, k; cin >> n >> k; SUMBIT bit; bit.bit1.bit.resize(n + 1); bit.bit2.bit.resize(n + 1); vector<int> h(n + 1); for(int i = 1; i <= n; i++) cin >> h[i]; vector<vector<pii>> qry(n + 1); int q; cin >> q; for(int i = 0; i < q; i++){ int l, r; cin >> l >> r; qry[r].eb(mp(l, i)); } deque<int> mx, mn; vector<ll> ans(q); int lp = 1; for(int i = 1; i <= n; i++){ while(!mx.empty() && h[mx.back()] <= h[i]) mx.pob; while(!mn.empty() && h[mn.back()] >= h[i]) mn.pob; mx.eb(i); mn.eb(i); while(h[mx.front()] - h[mn.front()] > k){ lp++; while(mx.front() < lp) mx.pof; while(mn.front() < lp) mn.pof; } bit.modify(lp, i, 1); for(auto p : qry[i]){ int id = p.S, l = p.F; ans[id] = bit.query(l, i); } } for(ll i : ans) cout < 告示牌 (Sign) 來源: [CF 803D](https://codeforces.com/problemset/problem/803/D) 測資: joylintp 題敘: joylintp ---- ### 告示牌 #### 只有在空格出現時才能換行 ---- ### 告示牌 - Subtask 1 $s$ 沒有空格 → 不能換行 → 答案為 $|s|$ 2 / 100 ---- ### 告示牌 - Subtask 2 $|s| \le 20$ → 枚舉換行的位置 → 複雜度 $O(2^{|s|} \times |s|)$ 9 / 100 ---- ### 告示牌 - Subtask 3 $|s| \le 1000$ → 枚舉告示牌寬度 → 找到最小的 $w$ 能塞得下 → 複雜度 $O(|s|^2)$ (9 + 16) / 100 ---- ### 告示牌 - Subtask 4 $|s| \le 2 \times 10^5$ ~~→ 枚舉告示牌寬度~~ → 對告示牌寬度二分搜 → 找到最小的 $w$ 能塞得下 → 複雜度 $O(|s|\log{|s|})$ 100 / 100 ---- ```cpp= #include<bits/stdc++.h> using namespace std; int k; vector<int> v; bool chk(int w) { int now = 0, cnt = 1; for (int i : v) if (now + i > w) now = i, cnt++; else now += i; return (cnt <= k); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> k, cin.ignore(100, '\n'); string s; getline(cin, s); int mx = 0, sum = s.size(); v.clear(); for (int i = 0; i < s.size(); i++) { int tl = 0; while (i < s.size() && s[i] != ' ') tl++, i++; if (i < s.size()) tl++; v.push_back(tl), mx = max(mx, tl); } int l = mx - 1, r = sum; while (l + 1 != r) { int m = (l + r) / 2; if (chk(m)) r = m; else l = m; } cout << r << '\n'; return 0; } ``` ---  變色蠑螈 (UPRP) 來源: [CF 939D](https://codeforces.com/problemset/problem/939/D) 測資: joylintp 題敘: joylintp ---- ### 變色蠑螈 - Subtask 1 $c_1 = c_2 = \ldots = c_n$ → 需要的魔法只會有 $c_1$ 到 $d_i$ → 答案是 $d_i$ 的相異數字數量 (？ ---- ### 變色蠑螈 - Subtask 1 $c_1 = c_2 = \ldots = c_n$ → 需要的魔法只會有 $c_1$ 到 $d_i$ → 答案是 $d_i$ 的相異數字數量 → 如果存在 $c_1 = d_i$ 記得要減一 `set` 維護，總複雜度 $O(n\log{n})$ 6 / 100 ---- ### 變色蠑螈 - Subtask 2 $a_i,b_i \le 2$ → 只會需要 $1$ 變成 $2$ 的魔法 → 如果存在 $c_i \ne d_i$ 答案為 $1$；否則為 $0$ 複雜度 $O(n)$ 4 / 100 ---- ### 變色蠑螈蠑螈顏色 → 點魔法 → 邊 → 判斷需要多少邊才能讓每組 $c_i,d_i$ 連通 ---- ### 變色蠑螈 - Subtask 3 $a_i,b_i \le 4$ → 魔法數量只有 $C^4_2 = 6$ 種 → 枚舉需要哪些魔法 9 / 100 ---- ### 變色蠑螈 - Subtask 4 $n,c_i \le 1000$ → 每次 DFS 判斷目前的 $c_i,d_i$ 是否已連通 → 不連通就加邊總複雜度 $O(n^2)$ 17 / 100 ---- ### 變色蠑螈 - Subtask 5 $c_i \le 2 \times 10^5$ ~~→ 每次 DFS 判斷目前的 $c_i,d_i$ 是否已連通~~ → 並查集判斷目前的 $c_i,d_i$ 是否已連通 → 不連通就加邊總複雜度 $O(n \times \alpha(n))$ (17+31) / 100 ---- ### 變色蠑螈 - Subtask 6 顏色最多 $2n$ 種 → 先將顏色編號離散化 → 剩下跟 Subtask 5 一樣總複雜度 $O(n \log{n} + n \times \alpha(n))$ 100 / 100 ---- ```cpp= #include<bits/stdc++.h> using namespace std; #define MP make_pair #define F first #define S second vector<int> rt; int fnd(int a) { if (a == rt[a]) return a; else return rt[a] = fnd(rt[a]); } void uni(int a, int b) { int x = fnd(a), y = fnd(b); rt[x] = y; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> c(n), d(n), v; for (int &i : c) cin >> i, v.push_back(i); for (int &i : d) cin >> i, v.push_back(i); sort(v.begin(), v.end()), v.resize(unique(v.begin(), v.end()) - v.begin()); rt.resize(v.size()); for (int i = 0; i < rt.size(); i++) rt[i] = i; vector<int> nc(n), nd(n); for (int i = 0; i < n; i++) nc[i] = lower_bound(v.begin(), v.end(), c[i]) - v.begin(); for (int i = 0; i < n; i++) nd[i] = lower_bound(v.begin(), v.end(), d[i]) - v.begin(); vector<pair<int, int>> ans; for (int i = 0; i < n; i++) if (fnd(nc[i]) != fnd(nd[i])) ans.push_back(MP(v[nc[i]], v[nd[i]])), uni(nc[i], nd[i]); cout << ans.size() << '\n'; for (auto p : ans) cout << p.F << ' ' << p.S << '\n'; return 0; } ```