--- tags: 成大高階競技程式設計 2020 --- # 2020 高階競程 Contest #2 - 題解 ## [藍的競程之旅--藍的夢](https://judge.csie.ncku.edu.tw/problems/25) - Task Provider:ian - Task Setter:ian ### 首殺 team20_23 (00:04) ### 解法說明 因為記憶體很小所以不能開陣列儲存數字,只能用 counting sort 解 ### 標準程式 :::spoiler ```cpp #include <bits/stdc++.h> using namespace std; int n, tmp, i; int cnt[110]; int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n; for (i = 0; i < n; i++) { cin >> tmp; cnt[tmp]++; } for (i = 100; i > 0; i--) { while (cnt[i] --> 0) { cout << i << " "; } } cout << endl; return 0; } ``` ::: ## [數根](https://judge.csie.ncku.edu.tw/problems/26) - Task Provider:ian - Task Setter:ian ### 首殺 team20_49 (00:14) ### 解法說明 仔細看就會發現每九個就會重複一輪,所以就有以下的公式解 ### 標準程式 :::spoiler ```cpp #include <iostream> using namespace std; int main(void) { long long int n, a, b; cin >> n; while (n --) { cin >> a >> b; cout << b + 9 * (a - 1) << '\n'; } return 0; } ``` ::: ## [喵嗚朋友](https://judge.csie.ncku.edu.tw/problems/27) - Task Provider:Miohitokiri5474 - Task Setter:Miohitokiri5474 ### 首殺 -- (-:-) ### 解法說明 想法很簡單,先將陣列開兩倍 一個人有兩個點 $i, i + n$ ,一個是紀錄朋友用的,另外一個是敵人 所以: 1. 如果 $a, b$ 是朋友,則 $a, b$ 應該要屬於同一個集合( $a + n, b + n$ 也屬於同一個集合) 2. 如果 $a, b$ 是敵人,則 $a, b + n$ 應該要屬於同一個集合( $a + n, b$ 也屬於同一個集合) 換成 code 的話應該會變成這樣: - 如果 $a, b$ 是朋友 - Union ( a, b ), Union ( a + n, b + n ); - 如果 $a, b$ 是敵人 - Union ( a, b + n ), Union ( a + n, b ); 換個簡單的說法,只要關係線有跨過 $n$ 就算是敵人 ### 標準程式 #### 解法 1 :::spoiler ```cpp // by. MiohitoKiri5474 #include<bits/stdc++.h> using namespace std; #define maxN 200005 int dis[maxN], sz[maxN]; inline void init ( void ){ for ( int i = 0 ; i < maxN ; i++ ) dis[i] = i; } int find ( int a ){ return dis[a] == a ? a : dis[a] = find ( dis[a] ); } inline void Union ( int a, int b ){ dis[find ( a )] = find ( b ); } inline bool same ( int a, int b ){ return find ( a ) == find ( b ); } int main(){ ios::sync_with_stdio ( false ); cin.tie ( 0 ); int n, m, a, b, type, an, bn; cin >> n >> m; init(); while ( m-- ){ cin >> type >> a >> b; an = a + n, bn = b + n; if ( type == 1 ){ if ( same ( a, bn ) || same ( an, b ) ){ cout << "nani\n"; continue; } Union ( a, b ); Union ( an, bn ); } else if ( type == 2 ){ if ( same ( a, b ) || same ( an, bn ) ){ cout << "nani\n"; continue; } Union ( a, bn ); Union ( b, an ); } else if ( type == 3 ){ if ( same ( a, b ) || same ( an, bn ) ) cout << "friend\n"; else if ( same ( an, b ) || same ( a, bn ) ) cout << "enemy\n"; else cout << "none\n"; } } } ``` ::: #### 解法 2 :::spoiler 可以把 dsu 的值直接加負號如以下: ```cpp #include<bits/stdc++.h> // by 藍 using namespace std; int dsu[100005]; int findroot(int x){ if(x > 0){ if(dsu[x] == x) return x; return dsu[x] = findroot(dsu[x]); } else { if(dsu[-x] == -x) return x; dsu[-x] = findroot(dsu[-x]); return -dsu[-x]; } } int main() { int n,m; cin.tie(0); ios::sync_with_stdio(0); cin>>n>>m; for(int i=0;i<=n;i++) { dsu[i]=i; } int a,b,c; while(m--) { cin>>c>>a>>b; a++;b++; if(c==1){ if(findroot(a) == -findroot(b)){ cout<<"nani"<<'\n'; continue; } findroot(a); if(dsu[a]>0) dsu[findroot(a)] = findroot(b); if(dsu[a]<0) dsu[-findroot(a)] = -findroot(b); } if(c==2){ if(findroot(a) == findroot(b)){ cout<<"nani"<<'\n'; continue; } findroot(a); if(dsu[a]>0) dsu[findroot(a)] = -findroot(b); if(dsu[a]<0) dsu[-findroot(a)] = findroot(b); } if(c==3){ if(findroot(a) == findroot(b)){ cout<<"friend\n"; } else if(-findroot(a) == findroot(b)){ cout<<"enemy\n"; } else{ cout<<"none\n"; } } } return 0; } ``` ::: ## [都市滑翔](https://judge.csie.ncku.edu.tw/problems/28) - Task Provider:leo900807 - Task Setter:leo900807 ### 首殺 -- (-:-) ### 解法說明 本題要找出有幾組 $i,j,k$ 符合 $a_i>a_j>a_k$ ,也就是「三元逆序數對」。 #### Subtask 1 $\ \ \ O(N^3)$ 用迴圈尋找所有的 $i,j,k$ ,並判斷是否符合 $a_i>a_j>a_k$ 。 #### Subtask 2 $\ \ \ O(N^2)$ 每次 $O(N)$ 尋找有多少的 $i<j$ 且 $a_i>a_j$ 以及 $k>j$ 且 $a_j>a_k$ ,並將兩者相乘即是以 $a_j$ 為中間的三元逆序數對數量,只要枚舉所有的 $j$ 並加總即可。 #### Subtask 3 $\ \ \ O(N+N\ \log\ N)$ 有了 Subtask 2 的想法後,可以將其改良,利用 merge sort 計算對於每個數字有多少比自己大的數字在前面,多少比自己小的數字在後面,最後相乘加總即可。 <font color="red">註:因為 $a_i$ 到 $10^9$,所以需離散化。</font> ### 標準程式 :::spoiler ```cpp #include <iostream> #include <algorithm> #define F first #define S second using namespace std; pair<int, int> a[800000]; long long tmp[800000], comb[800000][2], n; void mergesort(int l, int r){ int i, j, k, mid; if(l == r) return; mid = (l + r) / 2; mergesort(l, mid); mergesort(mid + 1, r); for(i = k = l, j = mid + 1; i <= mid && j <= r;){ if(a[i] <= a[j]){ comb[a[i].F][1] += j - (mid + 1); tmp[k++] = a[i++].F; } else{ comb[a[j].F][0] += mid - i + 1; tmp[k++] = a[j++].F; } } while(i <= mid){ comb[a[i].F][1] += r - (mid + 1) + 1; tmp[k++] = a[i++].F; } while(j <= r) tmp[k++] = a[j++].F; for(i = l; i <= r; i++) a[i].F = tmp[i]; } inline bool restore(const pair<int, int> &a, const pair<int, int> &b){ return a.S < b.S; } int main() { ios::sync_with_stdio(0), cin.tie(0); long long count = 0; cin >> n; for(int i = 0; i < n; i++) cin >> a[i].F, a[i].S = i; sort(a, a + n); for(int i = 0; i < n; i++) a[i].F = i; sort(a, a + n, restore); mergesort(0, n - 1); for(int i = 0; i < n; i++) count += comb[i][0] * comb[i][1]; cout << count << "\n"; } ``` ::: ## [和諧的圖](https://judge.csie.ncku.edu.tw/problems/29) - Task Provider:ys - Task Setter:raiso ### 首殺 -- (-:-) ### 解法說明 #### 解法 1 假設有點 $l < r$,$l$ 和 $r$ 相連,但 $\forall m. l < m < r$ 都沒有和 $l, r$ 相連,那麼就得把這些 $m$ 給加進圖裡 (有 $l, r$ 的這個圖) 換句話說,所有含有這種 $l, r$ 的連通塊,要和其他連通塊相連形成和諧的連通塊 例如圖中有這 5 個連通塊: 1. $1, 5, 6$ 2. $2, 3$ 3. $4$ 4. $7, 8$ 5. $9$ 那麼 1 號連通塊滿足上述性質(不和諧),所以從小到大要把 $2, 3, 4$ 這幾個數字納入 1 號連通圖 接著圖就會變成: 1. $1, 2, 3, 4, 5, 6$ 2. 3. 4. $7, 8$ 5. $9$ 這樣整個圖就和諧了。 實作上會採用 Union-Find forest 作為**不同連通塊**之間的判斷 首先一個個數字 $l$ 去檢驗,含有 $l$ 的連通塊,是否和諧? ```cpp for(int l = 1; l <= n; l++) { : . } ``` 也就是對於當前 $l$ 到該連通塊中**最大的數** $r$ 中所有 $m$,判斷 $m$ 是否在連通塊中,不在的話就把 $m$ 加進去 (加 1 條邊) ```cpp for(int m = l+1; m <= mx[Find(l)]; m++) { if(Find(l) == Find(m)) continue; else Union(l, m); } ``` > `mx[Find(l)]` 為含有 $l$ 的連通塊中的最大數,也就是 $r$ > 如何維護連通塊中的最大數請參考標準程式 實作的概念大致上是這樣,可是複雜度還是*過高* 但可以觀察到: 1. $1, 2, 3, 4, 5, 6$ 4. $7, 8$ 5. $9$ 已經把 1 號連通塊和諧了,那麼下個數就挑 $7$ (1 號中最大數 $6$ 的下個數) 然後嘗試把含有 $7$ 的 2 號連通塊和諧 > 雖然它早已和諧 :+1: 也就是說若含 $l$ 的連通塊已和諧,則下個欲選擇的連通塊可挑含 $l$ 連通塊中最大數的下個數: ```cpp for(int l = 1, m; l <= n; l=m) { for(m = l+1; m <= mx[Find(l)]; m++) { if(Find(l) == Find(m)) continue; Union(l, m); } } ``` ### 標準程式 #### 解法 1 :::spoiler ```cpp #include<bits/stdc++.h> using namespace std; int const maxn = 2e5 + 10; int n, m, gp[maxn], mx[maxn]; // gp := group, mx := maximum of group int Find(int v) { if(v == gp[v]) return v; int rt = Find(gp[v]); // rt := root of the group mx[rt] = max(mx[rt], mx[v]); return gp[v] = rt; } void Union(int u, int v) { int a = Find(u), b = Find(v); gp[a] = b; mx[a] = mx[b] = max(mx[a], mx[b]); } int main() { scanf("%d%d", &n, &m); for(int v = 1; v <= n; v++) gp[v] = mx[v] = v; for(int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); Union(u, v); } int cnt = 0; for(int u = 1, v; u <= n; u=v) for(v = u+1; v <= mx[Find(u)]; v++) { if(Find(u) == Find(v)) continue; Union(u, v); cnt++; } printf("%d\n", cnt); return 0; } ``` ::: #### 解法 2 :::spoiler ```cpp #include <bits/stdc++.h> using namespace std; int n, m; vector<int> boss; vector< pair<int, int> > bound; //定義一個連通圖的上下界 int fboss(int a) { return boss[a] = (boss[a] == a)? a: fboss(boss[a]); } int main() { cin >> n >> m; boss.resize(n); bound.resize(n); for(int i = 0; i < n; i++) { boss[i] = i; bound[i] = make_pair(i, i); } for(int i = 0; i < m; i++) { int a, b; int ba, bb; cin >> a >> b; a--, b--; ba = fboss(a); bb = fboss(b); boss[bb] = ba; } for(int i = 0; i < n; i++) { int bs = fboss(i); if(bs != i) bound[i].first = bound[i].second = 2e9; bound[bs].first = min(bound[bs].first, i); bound[bs].second = max(bound[bs].second, i); } int ans = 0; sort(bound.begin(), bound.end()); for(int i = 0; i < n-1 && bound[i+1].first < 1e9; i++) { int j = i+1; int upperb = bound[i].second; while(upperb >= bound[j].first) { upperb = max(upperb, bound[j].second); ans++, j++; } i = j-1; } cout << ans << endl; return 0; } ``` ::: ## [母牛與農地](https://judge.csie.ncku.edu.tw/problems/30) - Task Provider:ys - Task Setter:raiso ### 首殺 team20_12 (02:05) ### 解法說明 #### 解法 1 明顯的,在加入一條邊之後或多或少會讓最短路更短 - 如果更短了,肯定是最短路徑用了新加的這條邊 - 如果沒有改善,那就是最短路徑沒有改走新加的邊 也就是說,只需關心**當最短路徑用了新加的邊**的狀況 那麼設此邊為 $(a, b)$ 則要讓 $1 \rightsquigarrow n$ 盡量長, 而路徑是 $1 \rightsquigarrow a \to b \rightsquigarrow n$ 或 $1 \rightsquigarrow b \to a \rightsquigarrow n$ > 這裡 $x \rightsquigarrow y$ 是 $x$ 到 $y$ 的最短路徑 設 $d_x(y)$ 為 $x \rightsquigarrow y$ 的長度 > 則 $1 \rightsquigarrow a \to b \rightsquigarrow n$ 的長度就是 $d_1(a) + 1 + d_n(b)$ 若最短路徑是 $1 \rightsquigarrow a \to b \rightsquigarrow n$ 則長度會有 $d_1(a) + 1 + d_n(b) \le d_1(b) + 1 + d_n(a)$ 而任意特殊點對(邊) $(a, b)$ 都得滿足此不等式,也就是例如有點對 $(a, b), (b, c), (c, a)$ 會有三個不等式要滿足,假設為 $d_1(a) + 1 + d_n(b) < d_1(b) + 1 + d_n(a)$ $d_1(b) + 1 + d_n(c) < d_1(c) + 1 + d_n(b)$ $d_1(c) + 1 + d_n(a) < d_1(a) + 1 + d_n(c)$ > 在特殊點為三個以上,就不會出現等於關係了 會發現這些不等式能化簡成 $d_1(a) - d_n(a) < d_1(b) - d_n(b)$ $d_1(b) - d_n(b) < d_1(c) - d_n(c)$ $d_1(c) - d_n(c) < d_1(a) - d_n(a)$ 再化簡 $\underline{d_1(a) - d_n(a)} < d_1(b) - d_n(b) < d_1(c) - d_n(c) < \underline{d_1(a) - d_n(a)}$ 會發現得得到矛盾的結論 所以須從確定的結論往前推,不失一般性的,設有 $d_1(a) - d_n(a) < d_1(b) - d_n(b) < d_1(c) - d_n(c)$ 則回推的不等式為 $d_1(a) + 1 + d_n(b) < d_1(b) + 1 + d_n(a)$ $d_1(b) + 1 + d_n(c) < d_1(c) + 1 + d_n(b)$ $d_1(a) + 1 + d_n(c) < d_1(c) + 1 + d_n(a)$ 所以要比較這三者的大小 $d_1(a) + 1 + d_n(b), d_1(b) + 1 + d_n(c), d_1(a) + 1 + d_n(c)$ 推廣至一般狀況,若是 $d_1(a_1)-d_n(a_1) < d_1(a_2)-d_n(a_2) < \cdots < d_1(a_k)-d_n(a_k)$ 則可只比較所有 $d_1(a_x) + 1 + d_n(a_y)$ 其中 $1 \le x < y \le k$ #### 解法 2 同樣只關心有加入新邊的情況 設特殊點 $a, b$ 滿足 $d_1(a) < d_1(b)$ 有雙向邊 $(a, b)$,則有三種情況需考慮﹔ - $d_1(n) < d_1(a) < d_1(b)$ 最短路徑不經過 $a, b$ - $d_1(a) < d_1(n) < d_1(b)$ 最短路徑不經過 $b$ - $d_1(a) < d_1(b) < d_1(n)$ $d_1(a) + 1 < d_1(b) + 1$,且 $d_n(b)$ 與 $d_n(a)$ 只相差 $1$ 若是 $x \in \{a, b\}. d_1(x) + d_n(x) > d_1(n)$,則最短路徑不經過 $x$。 由上推得 $d_1(a) + 1 + d_n(b) \le d_1(b) + 1 + d_n(a)$ 所以特殊點依照 BFS 的深度排列,比較所有 $d_1(a_x) + 1 + d_n(a_y)$ 其中 $1 \le x < y \le k$ 得解 ### 標準程式 #### 解法 1 :::spoiler ```cpp #include<bits/stdc++.h> using namespace std; int const maxn = 2e5 + 10; int n, m, k, x, y; vector<int> E[maxn], a; void bfs(int s, vector<int> &d) { queue<int> q; set<int> vis; q.push(s); vis.insert(s); d[s] = 0; while(q.size()) { int u = q.front(); q.pop(); for(int v: E[u]) { if(vis.count(v)) continue; vis.insert(v); d[v] = d[u] + 1; q.push(v); } } } int main() { scanf("%d%d%d", &n, &m, &k); a.resize(k); for(int i = 0; i < k; i++) scanf("%d", &a[i]); for(int i = 0; i < m; i++) { scanf("%d%d", &x, &y); E[x].push_back(y); E[y].push_back(x); } vector<int> d1(n+1), dn(n+1); bfs(1, d1); bfs(n, dn); sort(a.begin(), a.end(), [&](int x, int y) { return d1[x]-dn[x] < d1[y]-dn[y]; }); int ans = 0, d1_mx = 0; for(int i = 0; i+1 < k; i++) { d1_mx = max(d1_mx, d1[a[i]]); ans = max(ans, d1_mx + 1 + dn[a[i+1]]); } printf("%d\n", min(ans, d1[n])); return 0; } ``` ::: #### 解法 2 :::spoiler ```cpp #include<bits/stdc++.h> using namespace std; int const maxn = 2e5 + 10; int n, m, k, a, x, y; vector<int> E[maxn], ord; // ord := order vector<bool> sp; // sp := special void bfs(int s, vector<int> &d) { queue<int> q; q.push(s); d.assign(n+1, -1); d[s] = 0; while(q.size()) { int u = q.front(); q.pop(); if(s == 1 && sp[u]) ord.push_back(u); for(int v: E[u]) { if(d[v] != -1) continue; d[v] = d[u] + 1; q.push(v); } } } int main() { scanf("%d%d%d", &n, &m, &k); sp.assign(n+1, false); for(int i = 0; i < k; i++) scanf("%d", &a), sp[a] = true; for(int i = 0; i < m; i++) { scanf("%d%d", &x, &y); E[x].push_back(y); E[y].push_back(x); } vector<int> d1, dn; bfs(1, d1); bfs(n, dn); int ans = 0, d1_mx = 0; for(int i = 0; i+1 < ord.size(); i++) { d1_mx = max(d1_mx, d1[ord[i]]); ans = max(ans, d1_mx + 1 + dn[ord[i+1]]); } printf("%d\n", min(ans, d1[n])); return 0; } ``` :::