---
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;
}
```
:::
Sign in with Wallet
Connect another wallet