# TOI練習賽202504潛力組
### [第一題](https://zerojudge.tw/ShowProblem?problemid=q377)
#### 考點：貪心
#### 實作方法
##### 子題一
暴力枚舉所有拆除情況，時間複雜度$\mathcal O(n*n!)$
::: spoiler Python 15% code
```python=
from itertools import permutations as P
n=int(input())
ans=float('inf')
mylist=[]
total=0
for i in range(n):
a,b=map(int,input().split())
mylist.append((a,b))
total+=a
for i in P(list(range(n))):
temp=total
cost=0
for j in i:
cost+=temp*mylist[j][1]
temp-=mylist[j][0]
ans=min(ans,cost)
print(ans)
```
:::
:::spoiler C++ 20% code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> mylist;
vector<int> perm(n);
int total = 0;
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
mylist.push_back({a, b});
total += a;
perm[i] = i;
}
long long ans = LLONG_MAX;
do {
int temp = total;
long long cost = 0;
for (int j = 0; j < n; ++j) {
int idx = perm[j];
cost += 1LL * temp * mylist[idx].second;
temp -= mylist[idx].first;
}
ans = min(ans, cost);
} while (next_permutation(perm.begin(), perm.end()));
cout << ans << endl;
return 0;
}
```
:::
##### 子題二
觀察到所有工程都只要一天，貪心準則：罰金多的先做。
簡易證明：假設兩個工程罰金分別為$a_1$、$a_2$，第一天固定為$a_1+a_2$，第二天可能是$a_1$或$a_2$。顯然要讓罰金比較小，第二天就要是$\min(a_1,a_2)$，也就是第一天是$\max(a_1,a_2)$，依此類推。
時間複雜度$\mathcal O(nlogn+n)$
::: spoiler Python 20% code(有判斷是否天數皆為1)
```python=
n=int(input())
ans=0
mylist=[]
total=0
flag=1
for i in range(n):
a,b=map(int,input().split())
mylist.append((a,b))
total+=a
flag&=(b==1)
if flag:
mylist.sort(key=lambda x:x[0])
while mylist:
cost,day=mylist.pop()
ans+=total*day
total-=cost
print(ans)
```
:::
::: spoiler C++ 20% code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, flag = 1;
long long int ans = 0, total = 0;
cin >> n;
vector<pair<int, int>> mylist;
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
mylist.push_back({a, b});
total += a;
flag &= (b == 1);
}
if (flag) {
sort(mylist.begin(), mylist.end());
while (!mylist.empty()) {
auto [cost, day] = mylist.back();
mylist.pop_back();
ans += total * day;
total -= cost;
}
cout << ans << endl;
}
return 0;
}
```
:::
::: spoiler Python 45% code(省去判斷，增加AC測資數)
```python=
n=int(input())
ans=0
mylist=[]
total=0
for i in range(n):
a,b=map(int,input().split())
mylist.append((a,b))
total+=a
mylist.sort(key=lambda x:x[0])
while mylist:
cost,day=mylist.pop()
ans+=total*day
total-=cost
print(ans)
```
:::
::: spoiler C++ 45% code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
long long int ans = 0, total = 0;
cin >> n;
vector<pair<int, int>> mylist;
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
mylist.push_back({a, b});
total += a;
}
sort(mylist.begin(), mylist.end());
while (!mylist.empty()) {
auto [cost, day] = mylist.back();
mylist.pop_back();
ans += total * day;
total -= cost;
}
cout << ans << endl;
return 0;
}
```
:::
##### 子題三
這次考慮$b$。在拆除時，固定有$a_1*b_1$，$a_2*b_2$的罰金。但是中間會有$a_1*b_2$或$a_2*b_1$的罰金(代表兩棟建築同時存在)，選擇較小，也就是每次兩個比較，較大的要先做。時間複雜度$\mathcal O(n^2+n)$
:::spoiler Python 50% code
```python=
n = int(input())
ans = 0
mylist = []
total = 0
flag=1
for i in range(n):
a, b = map(int, input().split())
mylist.append((a, b))
total += a
flag&=(b==1)
if n<=100: #因為zero judge的設計，不加這行可能會在前幾筆就TLE然後不能跑後面的測資
for i in range(n):
for j in range(0, n - i - 1):
a = mylist[j]
b = mylist[j + 1]
if a[0] * b[1] > b[0] * a[1]:
mylist[j], mylist[j + 1] = mylist[j + 1], mylist[j]
while mylist:
cost, day = mylist.pop()
ans += total * day
total -= cost
print(ans)
```
:::
:::spoiler C++ 50% code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, flag = 1;
long long int ans = 0, total = 0;
cin >> n;
vector<pair<int, int>> mylist;
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
mylist.push_back({a, b});
total += a;
flag &= (b == 1);
}
if (n <= 100) {//因為zero judge的設計，不加這行可能會在前幾筆就TLE然後不能跑後面的測資
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
auto a = mylist[j];
auto b = mylist[j + 1];
if (1LL * a.first * b.second > 1LL * b.first * a.second) {
swap(mylist[j], mylist[j + 1]);
}
}
}
while (!mylist.empty()) {
auto [cost, day] = mylist.back();
mylist.pop_back();
ans += total * day;
total -= cost;
}
cout << ans << endl;
}
return 0;
}
```
:::
##### AC
將上述排序依據($a_1*b_2$,$a_2*b_1$)同除以($b_1*b_2$)得到($a_1/b_1$,$a_2/b_2$)，這個即可作為Python排序的鍵值。C++則因為浮點數精度誤差，故不必變成除法。使用內建排序，時間複雜度$\mathcal O(nlogn+n)$
:::spoiler Python AC(1.1s, 39.3MB) code
```python=
n=int(input())
ans=0
mylist=[]
total=0
for i in range(n):
a,b=map(int,input().split())
mylist.append((a,b))
total+=a
mylist.sort(key=lambda x:x[0]/x[1])
while mylist:
cost,day=mylist.pop()
ans+=total*day
total-=cost
print(ans)
```
:::
::: spoiler C++ AC(0.3s,3.9MB) code
```cpp=
#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.first * b.second < b.first * a.second;
}
int main() {
int n;
long long int ans = 0, total = 0;
cin >> n;
vector<pair<int, int>> mylist;
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
mylist.push_back(make_pair(a, b));
total += a;
}
sort(mylist.begin(), mylist.end(), cmp);
while (!mylist.empty()) {
auto [cost, day] = mylist.back();
mylist.pop_back();
ans += total * day;
total -= cost;
}
cout <<ans << endl;
return 0;
}
```
:::
:::spoiler C++ AC(0.3s,3.9MB) code(除法比較)
```cpp=
#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<double, double> a, pair<double, double> b) {
double c=a.first/a.second,d=b.first/b.second;
return c<d;
}
int main() {
int n;
long long int ans = 0, total = 0;
cin >> n;
vector<pair<int, int>> mylist;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
mylist.push_back({a, b});
total += a;
}
sort(mylist.begin(), mylist.end(), cmp);
while (!mylist.empty()) {
auto [cost, day] = mylist.back();
mylist.pop_back();
ans += total * day;
total -= cost;
}
cout <<ans << endl;
return 0;
}
```
:::
### [第二題](https://zerojudge.tw/ShowProblem?problemid=q378)
#### 考點：DP
#### 實作方法
##### 子題一
暴力窮舉在長度為`now`時，共有幾種組合。把每個組合依序配對。
例如`n=3`，共有`(0),(1),(2),(0,1),(0,2),(1,2),(0,1,2)`七種。
在`now=2`，取出`(0,1),(0,2),(1,2)`兩兩配對為`out`,`in_`的`index`，共有`((0,1),(0,1)),((0,1),(0,2)),((0,2),(1,2)),((0,2),(1,2))`...九種。
以`((0,1),(0,2))`為範例，這個代表`out[0]`接`in_[1]`，`out[1]`接`in_[2]`
由於產生組合的方法是遞增的，故不會出現交叉，再把每組都計算一次得到答案。
時間複雜度$\mathcal O(\sum_{k=1}^{n} [C(n, k)^2 × k])\approx \mathcal O(4^n*n)$，$C$表組合計算公式。
:::spoiler Python 40% code
```python=
from itertools import combinations as C
n=int(input())
out=list(map(int,input().split()))
in_=list(map(int,input().split()))
nums=list(range(n))
ans=-1
for now in range(1,n+1):
com=list(C(nums,now))
for i in com:
for j in com:
cost=0
for s in range(now):
cost+=min(out[i[s]],in_[j[s]])
ans=max(ans,cost)
print(ans)
```
:::
::: spoiler C++ 40% code
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n, ans = -1;
vector<int> out, in_, comb;
void generate_combinations(int start, int depth, int k, vector<vector<int>> &res) {
if(depth == k) {
res.push_back(comb);
return;
}
for(int i = start; i < n; i++) {
comb[depth] = i;
generate_combinations(i + 1, depth + 1, k, res);
}
}
int main() {
cin >> n;
out.resize(n);
in_.resize(n);
for(int i = 0; i < n; i++) cin >> out[i];
for(int i = 0; i < n; i++) cin >> in_[i];
for(int now = 1; now <= n; now++) {
vector<vector<int>> com;
comb.resize(now);
generate_combinations(0, 0, now, com);
for(auto &i : com) {
for(auto &j : com) {
int cost = 0;
for(int s = 0; s < now; s++) {
cost += min(out[i[s]], in_[j[s]]);
}
ans = max(ans, cost);
}
}
}
cout << ans << endl;
return 0;
}
```
:::
##### AC
定義 $dp[i][j]$代表考慮前`i-1`個出水口和前`j-1`個進水口的最大值(不包含`i`,`j`)
枚舉出水口`i`、進水口`j`，考慮連不連接
一、不連接：$dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])$
二、連接：$dp[i][j]=dp[i][j]+min(in_[i],out[j])$
合併：$dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j],dp[i][j]+min(in_[i],out[j]))$
時間複雜度$\mathcal O(n^2)$
:::spoiler Python AC(1.3s, 27.1MB) code
```python=
def DP(n,in_,out):
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(n):
for j in range(n):
dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j],dp[i][j]+min(in_[i],out[j]))
return dp[n][n]
n=int(input())
in_=list(map(int,input().split()))
out=list(map(int,input().split()))
print(DP(n,in_,out))
```
:::
:::spoiler C++ AC(8ms, 4.2MB) code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int DP(int n, vector<int>& in_, vector<int>& out) {
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
dp[i + 1][j + 1] = max({dp[i][j + 1], dp[i + 1][j], dp[i][j] + min(in_[i], out[j])});
}
}
return dp[n][n];
}
int main() {
int n;
cin >> n;
vector<int> in_(n), out(n);
for (int i = 0; i < n; ++i) cin >> in_[i];
for (int i = 0; i < n; ++i) cin >> out[i];
cout << DP(n, in_, out) << endl;
return 0;
}
```
:::
### [第三題](https://zerojudge.tw/ShowProblem?problemid=q379)
#### 考點：最小生成樹(MST)、二分搜
#### 實作方法
##### 子題一、二
用kruskal建構一個MST計算初始最小成本。
觀察到`Q=1`，讀入一筆資料重新計算。時間複雜度$\mathcal O(MlogM)$
::: spoiler Python 60% code
```python=
import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
xr, yr = self.find(x), self.find(y)
if xr == yr:
return False
self.parent[yr] = xr
return True
def kruskal(N, edge_dict):
uf = UnionFind(N)
edges = sorted([(u, v, w) for (u, v), w in edge_dict.items()], key=lambda x: x[2])
mst_cost = 0
count = 0
for u, v, w in edges:
if uf.union(u, v):
mst_cost += w
count += 1
if count == N - 1:
break
return mst_cost
N, M, Q = map(int, input().split())
edge_dict = {}
for _ in range(M):
S, T, C = map(int, input().split())
edge_dict[(S, T)] = C
Qs, Qt, Qc = map(int, input().split())
K = int(input())
if kruskal(N, edge_dict) > K:
print(0)
else:
if (Qs, Qt) in edge_dict:
edge_dict[(Qs, Qt)] += Qc
else:
edge_dict[(Qs, Qt)] = Qc
if kruskal(N, edge_dict) > K:
print(1)
else:
print(-1)
```
:::
:::spoiler C++ 60% code
```cpp=
#include <bits/stdc++.h>
using namespace std;
class UnionFind {
public:
vector<int> parent;
UnionFind(int size) {
parent.resize(size);
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
bool union_sets(int x, int y) {
int xr = find(x), yr = find(y);
if (xr == yr) return false;
parent[yr] = xr;
return true;
}
};
int kruskal(int N, map<pair<int, int>, int>& edge_dict) {
UnionFind uf(N);
vector<tuple<int, int, int>> edges;
for (auto& e : edge_dict) {
edges.push_back({e.second, e.first.first, e.first.second});
}
sort(edges.begin(), edges.end());
int mst_cost = 0, count = 0;
for (auto& [w, u, v] : edges) {
if (uf.union_sets(u, v)) {
mst_cost += w;
count++;
if (count == N - 1) break;
}
}
return mst_cost;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, M, Q;
cin >> N >> M >> Q;
map<pair<int, int>, int> edge_dict;
for (int i = 0; i < M; i++) {
int S, T, C;
cin >> S >> T >> C;
edge_dict[{S, T}] = C;
}
int Qs, Qt, Qc;
cin >> Qs >> Qt >> Qc;
int K;
cin >> K;
if (kruskal(N, edge_dict) > K) {
cout << 0 << '\n';
return 0;
} else {
if (edge_dict.count({Qs, Qt})) {
edge_dict[{Qs, Qt}] += Qc;
} else {
edge_dict[{Qs, Qt}] = Qc;
}
if (kruskal(N, edge_dict) > K) {
cout << 1 << '\n';
} else {
cout << -1 << '\n';
}
}
return 0;
}
```
:::
### 子題三
改成讀入每筆資料並依序修改和計算，時間複雜度$\mathcal O(MlogM*Q)$
::: spoiler Python 70% code
```python=
import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, x, y):
xr, yr = self.find(x), self.find(y)
if xr == yr:
return False
self.parent[yr] = xr
return True
def kruskal(N, edges):
edges.sort(key=lambda x: x[2])
uf = UnionFind(N)
total = 0
count = 0
for u, v, w in edges:
if uf.union(u, v):
total += w
count += 1
if count == N - 1:
break
return total
N, M, Q = map(int, input().split())
edge_dict = {}
for _ in range(M):
S, T, C = map(int, input().split())
edge_dict[(S, T)] = C
updates = [tuple(map(int, input().split())) for _ in range(Q)]
K = int(input())
edges = [(u, v, w) for (u, v), w in edge_dict.items()]
if kruskal(N, edges) > K:
print(0)
else:
for i, (Qs, Qt, Qc) in enumerate(updates):
key = (Qs, Qt)
if key in edge_dict:
edge_dict[key] += Qc
else:
edge_dict[key] = Qc
edges = [(u, v, w) for (u, v), w in edge_dict.items()]
if kruskal(N, edges) > K:
print(i + 1)
break
else:
print(-1)
```
:::
:::spoiler C++ 70% code
```cpp=
#include <bits/stdc++.h>
using namespace std;
class UnionFind {
public:
vector<int> parent;
UnionFind(int size) {
parent.resize(size);
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
bool union_sets(int x, int y) {
int xr = find(x), yr = find(y);
if (xr == yr) return false;
parent[yr] = xr;
return true;
}
};
int kruskal(int N, vector<tuple<int, int, int>>& edges) {
UnionFind uf(N);
sort(edges.begin(), edges.end());
int mst_cost = 0, count = 0;
for (auto& [w, u, v] : edges) {
if (uf.union_sets(u, v)) {
mst_cost += w;
count++;
if (count == N - 1) break;
}
}
return mst_cost;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, M, Q;
cin >> N >> M >> Q;
map<pair<int, int>, int> edge_dict;
for (int i = 0; i < M; i++) {
int S, T, C;
cin >> S >> T >> C;
edge_dict[{S, T}] = C;
}
vector<tuple<int, int, int>> updates(Q);
for (int i = 0; i < Q; i++) {
cin >> get<0>(updates[i]) >> get<1>(updates[i]) >> get<2>(updates[i]);
}
int K;
cin >> K;
vector<tuple<int, int, int>> edges;
for (auto& e : edge_dict) {
edges.push_back({e.second, e.first.first, e.first.second});
}
if (kruskal(N, edges) > K) {
cout << 0 << '\n';
return 0;
}
for (int i = 0; i < Q; i++) {
int Qs = get<0>(updates[i]), Qt = get<1>(updates[i]), Qc = get<2>(updates[i]);
if (edge_dict.count({Qs, Qt})) {
edge_dict[{Qs, Qt}] += Qc;
} else {
edge_dict[{Qs, Qt}] = Qc;
}
edges.clear();
for (auto& e : edge_dict) {
edges.push_back({e.second, e.first.first, e.first.second});
}
if (kruskal(N, edges) > K) {
cout << i + 1 << '\n';
return 0;
}
}
cout << -1 << '\n';
return 0;
}
```
:::
##### AC
由於Q的範圍達到$2*10^5$，故二分搜答案範圍`(0~Q)`降低時間複雜度。時間複雜度$\mathcal O(MlogM*logQ)$
:::spoiler Python AC(2.1s, 39MB) code
```python=
import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, x, y):
xr, yr = self.find(x), self.find(y)
if xr == yr:
return False
self.parent[yr] = xr
return True
def kruskal(N, edge_dict):
edges = sorted([(u, v, w) for (u, v), w in edge_dict.items()], key=lambda x: x[2])
uf = UnionFind(N)
mst_cost = 0
count = 0
for u, v, w in edges:
if uf.union(u, v):
mst_cost += w
count += 1
if count == N - 1:
break
return mst_cost
# 主程式
N, M, Q = map(int, input().split())
edge_dict_base = {}
for _ in range(M):
S, T, C = map(int, input().split())
edge_dict_base[(S, T)] = C
updates = [tuple(map(int, input().split())) for _ in range(Q)]
K = int(input())
def check(mid):
edge_dict = edge_dict_base.copy()
for i in range(mid):
Qs, Qt, Qc = updates[i]
key = (Qs, Qt)
if key in edge_dict:
edge_dict[key] += Qc
else:
edge_dict[key] = Qc
return kruskal(N, edge_dict) > K
if kruskal(N, edge_dict_base) > K:
print(0)
else:
l, r = 1, Q
ans = -1
while l <= r:
mid = (l + r) // 2
if check(mid):
ans = mid
r = mid - 1
else:
l = mid + 1
print(ans)
```
:::
::: spoiler C++ AC(0.4s,6.1MB) code
```cpp=
#include <bits/stdc++.h>
using namespace std;
class UnionFind {
public:
vector<int> parent;
UnionFind(int size) {
parent.resize(size);
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
bool union_sets(int x, int y) {
int xr = find(x), yr = find(y);
if (xr == yr) return false;
parent[yr] = xr;
return true;
}
};
int kruskal(int N, map<pair<int, int>, int>& edge_dict) {
vector<tuple<int, int, int>> edges;
for (auto& e : edge_dict) {
edges.push_back({e.second, e.first.first, e.first.second});
}
sort(edges.begin(), edges.end());
UnionFind uf(N);
int mst_cost = 0, count = 0;
for (auto& [w, u, v] : edges) {
if (uf.union_sets(u, v)) {
mst_cost += w;
count++;
if (count == N - 1) break;
}
}
return mst_cost;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, M, Q;
cin >> N >> M >> Q;
map<pair<int, int>, int> edge_dict_base;
for (int i = 0; i < M; i++) {
int S, T, C;
cin >> S >> T >> C;
edge_dict_base[{S, T}] = C;
}
vector<tuple<int, int, int>> updates(Q);
for (int i = 0; i < Q; i++) {
cin >> get<0>(updates[i]) >> get<1>(updates[i]) >> get<2>(updates[i]);
}
int K;
cin >> K;
auto check = [&](int mid) {
map<pair<int, int>, int> edge_dict = edge_dict_base;
for (int i = 0; i < mid; i++) {
int Qs = get<0>(updates[i]), Qt = get<1>(updates[i]), Qc = get<2>(updates[i]);
if (edge_dict.count({Qs, Qt})) {
edge_dict[{Qs, Qt}] += Qc;
} else {
edge_dict[{Qs, Qt}] = Qc;
}
}
return kruskal(N, edge_dict) > K;
};
if (kruskal(N, edge_dict_base) > K) {
cout << 0 << '\n';
return 0;
}
int l = 1, r = Q, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans << '\n';
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet