--- tags: 成大高階競技程式設計 2021 image: https://i.imgur.com/IIj9BcL.png --- # 2021 高階競程 Contest #8 - 題解 ## [意義不明的糖果](https://judge.csie.ncku.edu.tw/problems/132) - Task Provider: ys - Task Setter: ys ### 首殺 team21_24 (00:04) ### 解法說明 根據題意: - 番茄糖可以給真姬、千歌、璃奈 - 柑橘糖可以給千歌、璃奈 - 咖啡糖可以給璃奈 #### 解法 1 明顯的 $t$ 必須大於等於 $m$ > 因為真姬只吃番茄糖 而當真姬拿完糖果後剩下的 $(t-m)+o$ 也要大於等於 $k$ > 因為可以給千歌番茄糖和柑橘糖 若最後剩下的 $((t-m)+o-k)+c$ 大於等於 $r$ 則能滿足所有人的期待 > 因為這三種糖果璃奈都吃 #### 解法 2 可將問題轉換為 flow network,使用現成演算法進行求解 ### 標準程式 :::spoiler 解法 1 ```cpp #include<cstdio> int m, k, r, t, o, c; int main() { scanf("%d%d%d%d%d%d", &m, &k, &r, &t, &o, &c); puts(t < m || t+o-m < k || t+o+c-m-k < r? "NO" : "YES"); return 0; } ``` ::: :::spoiler 解法 2 ```cpp #include<bits/stdc++.h> using namespace std; int constexpr MAXN = 8; int constexpr INF = INT_MAX; int m, k, r, t, o, c; struct MaxFlow{ struct edge{ int to, cap, flow, rev; }; vector<edge> v[MAXN]; int s, t, dis[MAXN], cur[MAXN]; int dfs(int u, int cap){ if(u == t || !cap) return cap; for(int &i = cur[u]; i < v[u].size(); i++){ edge &e = v[u][i]; if(dis[e.to] == dis[u] + 1 && e.flow != e.cap){ int df = dfs(e.to, min(e.cap - e.flow, cap)); if(df){ e.flow += df; v[e.to][e.rev].flow -= df; return df; } } } dis[u] = -1; return 0; } bool bfs(){ memset(dis, -1, sizeof(dis)); queue<int> q; q.push(s), dis[s] = 0; while(!q.empty()){ int tmp = q.front(); q.pop(); for(auto &u : v[tmp]){ if(!~dis[u.to] && u.flow != u.cap){ q.push(u.to); dis[u.to] = dis[tmp] + 1; } } } return dis[t] != -1; } int maxflow(int _s, int _t){ s = _s, t = _t; int flow = 0, df; while(bfs()){ memset(cur, 0, sizeof(cur)); while(df = dfs(s, INF)) flow += df; } return flow; } void addedge(int st, int ed, int cap){ v[st].push_back(edge{ed, cap, 0, v[ed].size()}); v[ed].push_back(edge{st, 0, 0, v[st].size() - 1}); } }; int main() { cin >> m >> k >> r >> t >> o >> c; MaxFlow fn; int S = 0, T = 7; //source and sink fn.addedge(S, 1, t); fn.addedge(S, 2, o); fn.addedge(S, 3, c); fn.addedge(1, 4, INF); fn.addedge(1, 5, INF); fn.addedge(1, 6, INF); fn.addedge(2, 5, INF); fn.addedge(2, 6, INF); fn.addedge(3, 6, INF); fn.addedge(4, T, m); fn.addedge(5, T, k); fn.addedge(6, T, r); cout << (fn.maxflow(S, T) >= m+k+r? "YES" : "NO") << endl; return 0; } ``` ::: ## [鎮長小嵐](https://judge.csie.ncku.edu.tw/problems/133) - Task Provider: D4nnyLee - Task Setter: D4nnyLee ### 首殺 team21_24 (00:26) ### 解法說明 令 $a_i$ 為門牌號碼為 $i$ 的住戶的收入。 定義 $f(i) = \left\{ \begin{matrix} 0, & \text{if } a_i > y \\ 1, & \text{otherwise}\end{matrix} \right.$ 可以發現陣列 $a$ 透過 $f$ 映射之後會有單調性, 因此我們只要在映射之後的陣列上面做二分搜即可。 ### 標準程式 :::spoiler ```cpp #include "lib0133.h" int main() { int n, y; Init(&n, &y); long long l = -1, r = n; while (r - l > 1) { long long mid = (l + r) / 2; if (Query(mid) > y) l = mid; else r = mid; } Ans(r); return 0; } ``` ::: ## [今天的塔矢亮 不開心](https://judge.csie.ncku.edu.tw/problems/134) - Task Provider: [CF 1622 C](https://codeforces.com/contest/1622/problem/C) - Task Setter: raiso ### 首殺 team21_23 (00:51) ### 解法說明 - 思考 $A$ 矩陣的順序是否影響最終結果?否 - 思考「減法」在「同化」之前是否只有好處沒有壞處?是 - 本題枚舉同化人數$t$,從 $0$ 到 $N-1$,找出不同 $t$ 所需要的操作數量。 - 同化的對象為 $A$ 矩陣中的較大值,目標為 $A$ 矩陣中最小值,所以先將 $A$ 從小到大排序 - $\Sigma$ IQ = $A_1+..+A_{N-t} + t * A_1$ - 操作數量 = $A_1$的減法次數$+t$ - 針對每個 $t$ 計算 $A_1$ 所需要的減法次數。 - 補充說明:範例code中的 $(X+t) / (t+1)$ 為除法取頂的實作方案。 ### 標準程式 :::spoiler ```cpp #include <bits/stdc++.h> #define Int long long #define pb push_back using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); Int n, k; cin >> n >> k; vector<Int> A(n); for(auto &it: A) cin >> it; sort(A.begin(), A.end()); vector<Int> pre{0}; for(auto it: A) pre.pb(pre.back()+it); Int ans = LLONG_MAX; for(int t = 0; t < n; t++) { Int sum = pre[n-t] + A[0] * t; Int cnt = t; if(sum > k) { Int diff = sum - k; cnt += (diff+t) / (t+1); } ans = min(ans, cnt); } cout << ans << endl; return 0; } ``` ::: ## [產業鏈](https://judge.csie.ncku.edu.tw/problems/135) - Task Provider: leo - Task Setter: leo ### 首殺 -- (-:-) ### 解法說明 題目的要求是你要將一張無向圖的點分成兩個點集, 其中某些點要在點集 $X$,另一些點要在點集 $Y$。 而且要使得不跨點集的那些邊的權重和最大。 可以假設一開始可以獲得所有的經濟效益, 且把一個點分配在點集 $X$,則該點屬於源點這一邊; 如果分配在點集 $Y$ 則在匯點這邊。 題目的要求變成是要使得跨越點集那些邊的權重和最小, 則這道題目就變成最小割問題。 再考慮那些必定在點集 $X$ 的那些點, 因為那些點不可以被分配到匯點的那一側, 所以從源點連接一條流量無限大的邊到那些點, 同理,必定在點集 $Y$ 的那些點, 則連接一條流量無限大的邊到匯點。 就可以跑一次從源點到匯點的最小割, 再用總經濟效益減掉最小割的值即為答案。 <font color="red"><B>請注意:本題所有的邊都需要建雙向邊。</B></font> 題外話: 如果題目沒有限制某些企業需要在某個廠區, 則此題會變成全域最小割問題, 有興趣的人可以自己上網搜尋解法。 ### 標準程式 :::spoiler ```cpp #include <iostream> #include <cstring> #include <vector> #include <queue> using namespace std; const int MAXN = 305, S = 301, T = 302, INF = 1000000000; struct MaxFlow{ struct edge{ int to, cap, flow, rev; }; vector<edge> v[MAXN]; int s, t, dis[MAXN], cur[MAXN]; int dfs(int u, int cap){ if(u == t || !cap) return cap; for(int &i = cur[u]; i < v[u].size(); i++){ edge &e = v[u][i]; if(dis[e.to] == dis[u] + 1 && e.flow != e.cap){ int df = dfs(e.to, min(e.cap - e.flow, cap)); if(df){ e.flow += df; v[e.to][e.rev].flow -= df; return df; } } } dis[u] = -1; return 0; } bool bfs(){ memset(dis, -1, sizeof(dis)); queue<int> q; q.push(s), dis[s] = 0; while(!q.empty()){ int tmp = q.front(); q.pop(); for(auto &u : v[tmp]){ if(!~dis[u.to] && u.flow != u.cap){ q.push(u.to); dis[u.to] = dis[tmp] + 1; } } } return dis[t] != -1; } int maxflow(int _s, int _t){ s = _s, t = _t; int flow = 0, df; while(bfs()){ memset(cur, 0, sizeof(cur)); while(df = dfs(s, INF)){ flow += df; } } return flow; } void addedge(int st, int ed, int cap){ v[st].push_back(edge{ed, cap, 0, v[ed].size()}); v[ed].push_back(edge{st, 0, 0, v[st].size() - 1}); } } dinic; int main() { int n, m, k, x, a, b, r, sum = 0; cin >> n >> m >> k; while(k--){ cin >> x; dinic.addedge(S, x, INF); } cin >> k; while(k--){ cin >> x; dinic.addedge(x, T, INF); } while(m--){ cin >> a >> b >> r; sum += r; dinic.addedge(a, b, r); dinic.addedge(b, a, r); } cout << sum - dinic.maxflow(S, T) << "\n"; } ``` ::: ## [時空旅人小嵐](https://judge.csie.ncku.edu.tw/problems/136) - Task Provider: arashi87 - Task Setter: arashi87 ### 首殺 -- (-:-) ### 解法說明 這題就是很單純的最短路而已,並沒卡特別的東西,唯一的難點就在於怎麼建邊而已,因為按照題目的規則在樓層間最多可以建到 $445^{445}$ 條邊,因此樓層間的邊不能用常規的方法建。 所以在這題我們對於樓層間邊的建法需要用到一點小技巧,對於每層樓我們都多開一個虛點代表,兩層樓間需要相連的教室通通都連到這個虛點就行,這樣邊數就會從 $N^2$ 退化到 $2N$,但這樣還會有個問題是題目要求同樓層的教室不能相連,因此對於第 $L_i$ 層樓連到 $L_{i+1}$ 層的邊通通是單向邊,連到 $L_{i-1}$ 的邊是雙向邊就能解決這問題了。 邊建完後跑一次最短路就行了。 ### 標準程式 :::spoiler ```cpp #include <cstdio> #include <queue> #include <set> #include <vector> using namespace std; const int maxN = 6e5 + 10; const int INF = 0x3f3f3f3f; struct Edge { int to, val; Edge(int a, int b) : to(a) , val(b) {}; bool operator<(const Edge& rhs) const { return val > rhs.val; } }; int t, n, m, c, x, y, z; int vis[maxN], dis[maxN], lay[maxN], has[maxN]; vector<Edge> G[maxN]; queue<int> q; int spfa(int st, int ed) { for (int i = 0; i <= 2 * n + 1; i++) vis[i] = 0, dis[i] = INF; dis[st] = 0, q.push(st); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = 0; i < (int)G[u].size(); i++) { Edge* tmp = &G[u][i]; int v = (*tmp).to, w = (*tmp).val; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if (!vis[v]) vis[v] = 1, q.push(v); } } } return (dis[ed] == INF ? -1 : dis[ed]); } int main() { scanf("%d%d%d", &n, &m, &c); for (int i = 0; i <= 2 * n + 1; i++) G[i].clear(), lay[i] = 0, has[i] = 0; for (int i = 1; i <= n; i++) { scanf("%d", &x); lay[i] = x, has[x] = 1; } for (int i = 1; i <= n; i++) { G[lay[i] + n].push_back(Edge(i, 0)); if (lay[i] > 1) G[i].push_back(Edge(lay[i] + n - 1, c)); if (lay[i] < n) G[i].push_back(Edge(lay[i] + n + 1, c)); } for (int i = 1; i <= n; i++) { if (has[i] && has[i - 1]) { G[i + n].push_back(Edge(i + n - 1, c)); G[i + n - 1].push_back(Edge(i + n, c)); } } while (m--) { scanf("%d%d%d", &x, &y, &z); G[x].push_back(Edge(y, z)); G[y].push_back(Edge(x, z)); } printf("%d\n", spfa(1, n)); } ``` ::: ## [渣男小嵐](https://judge.csie.ncku.edu.tw/problems/137) - Task Provider: XDEv11 - Task Setter: ys ### 首殺 team21_24 (03:23) ### 解法說明 我們先將 $n, m$ 變為一樣大,再將不存在的邊補全,這題就是個很標準的匈牙利演算法的問題;至於不存在的邊該補成什麼,因為題目要求最大權最大匹配,我們可以將邊補成一個很大的負數,來確保轉化後的圖的最大權完美匹配,一定會是一個最大匹配。 ### 標準程式 :::spoiler ```cpp! #include <ios> #include <iostream> #include <vector> #include <queue> #include <utility> #include <algorithm> using namespace std; // Hungarian Algorithm - O(V^3) class WeightedBipartiteMatching { int n; vector<long long> lx{}, ly{}; vector<bool> vx{}, vy{}; queue<int> qu{}; // only X's vertices vector<int> py{}; vector<long long> dy{}; // smallest (lx[x] + ly[y] - w[x][y]) vector<int> pdy{}; // & which x vector<int> mx{}, my{}; void relax(const vector<vector<long long>>& w, int x) { for (int y{0}; y < n; ++y) if (lx[x] + ly[y] - w[x][y] < dy[y]) dy[y] = lx[x] + ly[y] - w[x][y], pdy[y] = x; } void augment(int y) { while (y != -1) { int x{py[y]}, yy{mx[x]}; mx[x] = y, my[y] = x; y = yy; } } bool bfs(const vector<vector<long long>>& w) { while (!qu.empty()) { int x{qu.front()}; qu.pop(); for (int y{0}; y < n; ++y) { if (!vy[y] && lx[x] + ly[y] == w[x][y]) { vy[y] = true, py[y] = x; if (my[y] == -1) return augment(y), true; int xx{my[y]}; qu.push(x), vx[xx] = true, relax(w, xx); } } } return false; } void relabel() { long long d{numeric_limits<long long>::max()}; for (int y{0}; y < n; ++y) if (!vy[y]) d = min(d, dy[y]); for (int x{0}; x < n; ++x) if (vx[x]) lx[x] -= d; for (int y{0}; y < n; ++y) if (vy[y]) ly[y] += d; for (int y{0}; y < n; ++y) if (!vy[y]) dy[y] -= d; } bool expand(const vector<vector<long long>>& w) { // expand one layer with new equality edges for (int y{0}; y < n; ++y) { if (!vy[y] && dy[y] == 0) { vy[y] = true, py[y] = pdy[y]; if (my[y] == -1) return augment(y), true; int xx{my[y]}; qu.push(xx), vx[xx] = true, relax(w, xx); } } return false; } public: pair<vector<int>, vector<int>> operator()(const vector<vector<long long>>& w) { n = w.size(), lx.assign(n, 0), ly.assign(n, 0), vx.resize(n), vy.resize(n), py.resize(n), dy.resize(n), pdy.resize(n), mx.assign(n, -1), my.assign(n, -1); for (int i{0}; i < n; ++i) for (int j{0}; j < n; ++j) lx[i] = max(lx[i], w[i][j]); for (int x{0}; x < n; ++x) { fill(vx.begin(), vx.end(), false); fill(vy.begin(), vy.end(), false); fill(dy.begin(), dy.end(), numeric_limits<long long>::max()); qu = {}, qu.push(x), vx[x] = true, relax(w, x); while (!bfs(w)) { relabel(); if (expand(w)) break; } } return {move(mx), move(my)}; } }; void solve() { const long long NONE{-1000000000}; int n, m; cin >> n >> m; vector<vector<long long>> w(max(n, m), vector<long long>(max(n, m), NONE)); for (int i{0}; i < m; ++i) { int k; cin >> k; while (k--) { int g, a; cin >> g >> a, --g; w[i][g] = a; } } int ans{0}; auto mh{WeightedBipartiteMatching{}(w).first}; for (int i{0}; i < m; ++i) { if (w[i][mh[i]] != NONE) ans += w[i][mh[i]]; } cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t{1}; //cin >> t; while (t--) solve(); return 0; } ``` ::: ## [史萊姆農場](https://judge.csie.ncku.edu.tw/problems/138) - Task Provider: GY - Task Setter: ys ### 首殺 team21_24 (01:48) ### 解法說明 問題是在求 $\sum\limits^n_{i=2}\sum\limits^{i-1}_{j=1}\gcd(a_j, a_{j+1}, \cdots , a_i)$ 枚舉每個區間,並利用**重疊**的區間減少計算量,其複雜度為 $O(n^2)$ > 例如計算 $\gcd(a_1, \cdots , a_4)$ 可用已經算過的 $\gcd(a_1, \cdots , a_3)$ 來算 由於這種作法複雜度過高,需要再仔細觀察問題特性,以減少計算量 令 $(a_k)^i_{k=j} = \gcd(a_j, a_{j+1}, \cdots , a_i)$ 會發現 $(a_k)^i_{k=i} \ge (a_k)^{i}_{k=i-1} \ge \cdots \ge (a_k)^i_{k=1}$ 並且對任意的 $i \le n$ 最多只會有 $O(\log_2{a_k})$ 個相異的 $(a_k)^i_{k=j}$ > 因為一個數 $x$ 的質因數個數不超過 $\log_2 x$ 個 於是對每個 $i$ 找出這些**相異數** $\{(a_k)^i_{k=j} \mid j \le i \}$ 且乘上對應的數量,接著加總起來就行 #### 解法 1 對於每個 $i \in [2, n]$ 在 $[1, i]$ 找到所有 $m$ 個位置 $X$ 滿足 $(a_k)^i_{k=X_1} \not= (a_k)^i_{k=X_2} \not= \cdots \not= (a_k)^i_{k=X_m}$ 將這些相異數一個個跟 $a_{i+1}$ 取 GCD,會得到 $(a_k)^{i+1}_{k=X_1} , (a_k)^{i+1}_{k=X_2} , \cdots , (a_k)^{i+1}_{k=X_m}$ 若 $y_1, y_2 \in X$ 有 $(a_k)^{i+1}_{k=y_1} = (a_k)^{i+1}_{k=y_2}$ 則**保留其中一個**,這樣就得到對於 $i+1$ 的所有相異數 實作上對於 $i$ 用陣列 `num` 存相異數 $\{(a_k)^{i-1}_{k=j} \mid j \le i-1 \}$、陣列 `cnt` 存對應的個數 而 `_num` 及 `_cnt` 分別會暫存對於 $i$ 的相異數 $\{(a_k)^{i}_{k=j} \mid j \le i \}$ 及其對應的個數 #### 解法 2 對於每個 $i \in [2, n]$ 有 $(a_k)^i_{k=i} \ge (a_k)^{i+1}_{k=i} \ge \cdots \ge (a_k)^n_{k=i}$ 對任意 $j \ge i$ 能找到 $(a_k)^j_{k=i}$ 的 lower bound 以及 upper bound 且可以順便得知下個**相異**於 $(a_k)^j_{k=i}$ 的數的位置 實作上對於任意 $i, j$ 採用 Sparse Table 查詢 $(a_k)^j_{k=i}$ 的值,並用二分搜找出 bound ### 標準程式 :::spoiler 解法 1 ```cpp #include<bits/stdc++.h> using namespace std; typedef long long Int; int constexpr maxn = 5e5 + 5; Int n, a[maxn]; int main() { cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; Int sum = 0; vector<Int> num, cnt; // differences, count for(int i = 0; i < n; i++) { vector<Int> _num {a[i]}, _cnt {1}; // a[i] 可能與 gcd(a[i], a[i-1]) 相異 for(int j = 0; j < num.size(); j++) { Int g = __gcd(a[i], num[j]); sum += cnt[j] * g; if(g < _num.back()) { _num.push_back(g); _cnt.push_back(cnt[j]); } else { _cnt.back() += cnt[j]; } } num = _num, cnt = _cnt; } cout << sum << endl; return 0; } ``` ::: :::spoiler 解法 2 ```cpp #include<bits/stdc++.h> using namespace std; typedef long long Int; int constexpr maxn = 5e5 + 5, lgmaxn = 19; Int n, a[maxn], ST[maxn][lgmaxn]; int main() { cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; /* Sparse Table construction */ for(int i = 0; i < n; i++) ST[i][0] = a[i]; for(int k = 1; k <= log2(n); k++) for(int i = 0; i+(1<<k) <= n; i++) ST[i][k] = __gcd(ST[i][k-1], ST[i+(1<<k-1)][k-1]); auto query = [](int l, int r) { int k = 31 - __builtin_clz(r+1-l); return __gcd(ST[l][k], ST[r+1-(1<<k)][k]); }; /* solution */ Int sum = 0; for(int i = 0; i < n; i++) { int j = i+1; // 根據題意 gcd(a[i]) 不需加進總和,故從 gcd(a[i], a[i+1]) 開始 while(j < n) { int l = j, r = n; while(l != r) { int m = (l+r)/2; if(query(i, m) >= query(i, j)) l = m+1; else r = m; } sum += (r-j) * query(i, j); j = r; } } cout << sum << endl; return 0; } ``` ::: ## [撿紅包遊戲](https://judge.csie.ncku.edu.tw/problems/139) - Task Provider: ccbeginner - Task Setter: ccbeginner ### 首殺 -- (-:-) ### 解法說明 先把題目給出的矩陣變成一個二分圖,假設有兩個子圖 $X,Y$ ,$X$ 有 $n$ 個節點,$Y$ 有 $m$ 個節點,然後如果第 $i$ 行第 $j$ 列的數字大於 $0$,就把 $X_i$ 跟 $Y_j$ 連一條邊起來。 然後……就是求整張圖的最小生成樹啦~ 最小生成樹上的錢錢數量就是大人拿到的數量。 最後再把圖上權重和減掉最小生成樹上的權重和就是答案。 ### 標準程式 :::spoiler ```cpp /* https://judge.csie.ncku.edu.tw/problems/139 */ #include <bits/stdc++.h> using namespace std; #define int long long #define SZ(x) (int)(x.size()) int parent[2001]; int find_p(int k){ if(k == parent[k])return k; return parent[k] = find_p(parent[k]); } bool Union(int a, int b){ int A = find_p(a); int B = find_p(b); if(A == B)return 0; if(A > B)swap(A,B); parent[B] = A; return 1; } struct edge{ int u,v,w; bool operator<(const edge &rhs){ return w < rhs.w; } }; vector<edge> edges; int32_t main(){ int n,m; cin >> n >> m; for(int i = 1; i <= n+m; ++i){ parent[i] = i; } int ans = 0; for(int i = 1; i <= n; ++i){ for(int j = 1; j <= m; ++j){ edge x; cin >> x.w; if(x.w == 0)continue; x.u = i; x.v = n+j; ans += x.w; edges.emplace_back(x); } } sort(edges.begin(), edges.end()); for(int i = 0; i < SZ(edges); ++i){ if(Union(edges[i].u, edges[i].v)){ ans -= edges[i].w; } } printf("%lld\n", ans); return 0; } ``` :::