第二場比賽 題解
=
>啦啦啦大家加油
>
# [z011](https://judge.cp.ccns.io/problem/z011)：
很直覺的，每次挑選**最小的兩個**數字相加起來，成本一定最少
最後總成本也會是所有方法中最少的
於是先構造一個能夠每次將最小數字拿出來的 `priority_queue`：
```cpp
priority_queue<long long, vector<long long>, greater<long long> > PQ;
```
> 也可將數字變為**負數**推入 `priority_queue`，推出後再變回正數，也是當前最小的數字
> [還記得](https://hackmd.io/s/SJ7nxwRL4#Priority-queue) STL 的 priority queue 的 front 會優先選**容器中最大**的元素吧?
接著將兩個最小數相加，推回 `PQ` 中就行了：
```cpp
long long a = PQ.top(); PQ.pop();
long long b = PQ.top(); PQ.pop();
cost += a += b;
PQ.push(a);
```
以下完整解題程式碼：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long Int;
int N;
priority_queue<Int, vector<Int>, greater<Int> > PQ;
int main()
{
while(scanf("%d", &N) && N) {
while(N--) {
int num;
scanf("%d", &num);
PQ.push(num);
}
Int cost = 0;
while(PQ.size() != 1) {
Int a = PQ.top(); PQ.pop();
Int b = PQ.top(); PQ.pop();
cost += a += b;
PQ.push(a);
} PQ.pop();
printf("%lld\n", cost);
}
return 0;
}
```
(注意測資範圍)
# [z012](https://judge.cp.ccns.io/problem/z012)：
這題在一開始就不保證每個點是連通的喔！
這題需要從 $D$ 大往 $D$ 小的方式去做
利用 Disjoint sets 的特性去知道在`剩餘的網路結構`下，有幾個不同的連通圖
此時需要重建的網路線就是`連通圖個數-1`
然後再依照 $D$ 變小的條件維護`剩餘的網路結構`下，有幾個不同的連通圖，此時需要重建的網路線就是`連通圖個數-1`
...直到做完所有的 $D$
```cpp
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
int n, m;
vector<int> deg;
priority_queue< pair<int, pii> > edge;
vector< pii > data;
vector<int> bs;//boss
int fboss(int x) {
if(x == bs[x]) return x;
return bs[x] = fboss(bs[x]);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
bs.resize(n+1);
for(int i = 1; i <= n; i++) bs[i] = i;
deg.resize(n+1);
data.resize(m);
for(int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
deg[a]++, deg[b]++;
data[i].ff = a;
data[i].ss = b;
}
for(int i = 0; i < m; i++) {
int a = data[i].ff;
int b = data[i].ss;
int deg_min = min(deg[a], deg[b]);
edge.push(make_pair(deg_min, data[i]));
}
vector<int> ans;
ans.resize(n);
int cnt = n;
for(int i = n-1; i >= 0; i--) {
//rebuild
while(!edge.empty() && edge.top().ff > i) {
pii now = edge.top().ss; edge.pop();
int bs_a = fboss(now.ff);
int bs_b = fboss(now.ss);
if(bs_a != bs_b) cnt--, bs[bs_a] = bs_b;
}
ans[i] = cnt-1;
}
cout << ans[0];
for(int i = 1; i < n; i++) cout << " " << ans[i];
cout << endl;
return 0;
}
```
# [z013](https://judge.cp.ccns.io/problem/z013)：
基於**朋友的朋友還是自己的朋友**，所以在這圈子挑個黃金**需求最少**的角色賄賂就行
也就是對於第 $i$ 個人，將這個圈子 ($i$ 與朋友們) 都**遍歷**一遍，算出最小的黃金(`g`)
並累加起來：
```cpp
dfs(i, g);
sum += g;
```
而走過的第 $p$ 位角色會設為：
```cpp
vis[p] = true;
```
所以這個圈子下次不會再次拜訪。
而 `dfs` 將當前最小的黃金 (`gold`) 與鄰點的 $C_v$ 比較，然後更新其 `gold`
(這裡 `gold` 是以**傳參考**的方式)
```cpp
void dfs(int u, int &gold) {
for(auto &v: E[u]) {
if(vis[v]) continue;
vis[v] = true;
gold = min(gold, c[v]);
dfs(v, gold);
}
}
```
以下完整解題程式碼：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
int n, m, c[maxn];
bool vis[maxn];
vector<int> E[maxn];
void dfs(int u, int &gold) {
for(auto &v: E[u]) {
if(vis[v]) continue;
vis[v] = true;
gold = min(gold, c[v]);
dfs(v, gold);
}
}
int main() {
while(~scanf("%d%d", &n, &m)) {
//init
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++) E[i].clear();
//input
for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
int u, v;
for(int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
E[u].push_back(v);
E[v].push_back(u);
}
//solution
long long sum = 0;
for(int i = 1; i <= n; i++) {
if(vis[i]) continue;
int g = c[i];
dfs(i, g);
sum += g;
}
printf("%lld\n", sum);
}
return 0;
}
```
(注意測資範圍， `sum` 要開大一點)
# [z014](https://judge.cp.ccns.io/problem/z014)：
這是一題 BFS 或 DFS，簡單來說，儲存一個狀態，包含 yuri、WOLF、KIILITOU、CORN 的位置，不斷檢查下一個步驟可以做哪些行動，保證東西不會被吃掉，直到步數等於 $N$。
特別要注意的是如果已經完成，便不能再開船，例如在七步的時候運完所有東西，就不能再開船將 KIILITOU 帶走，不然會被白眼。這個部分包含我在內有三個人寫錯，結果大家都寫出假 AC。
Code:
```cpp
#include <bits/stdc++.h>
// define boat 0
// define CORN 1
// define KIILITOU 2
// define WOLF 3
// 3 eat 2 eat 1
#define South 0
#define North 1
using namespace std;
string names[4] = {"nothing", "CORN", "KIILITOU", "WOLF"};
struct condition {
int pos[4] = {South};
queue<pair<int, int>> operations;
};
bool chk_not_eat(int* now) {
for (int i = 2; i <= 3; i++) {
if (now[i] == now[i - 1]) return false;
}
return true;
}
bool chk_success(condition now) {
for (int i = 0; i <= 3; i++) {
if (now.pos[i] == South) return false;
}
return true;
}
int main() {
queue<condition> bfs;
condition init;
int n;
cin >> n;
bfs.push(init);
int cnt = 0;
while (!bfs.empty()) {
condition front = bfs.front();
bfs.pop();
if (chk_success(front)) {
if (front.operations.size() == n) {
/* for print all possible sol
while (!front.operations.empty()) {
cout << names[front.operations.front().first] << " to "
<< ((front.operations.front().second) ? "North"
: "South")
<< endl;
front.operations.pop();
}
cout << endl;
*/
cnt++;
}
continue;
} else if (front.operations.size() == n)
continue;
for (int i = 0; i <= 3; i++) { // i=0 代表空船
if (front.pos[0] == front.pos[i]) {
int tmp = front.pos[i];
front.pos[i] = 3; // 載上船 改成 3 不屬於任何一邊
if (chk_not_eat(front.pos)) {
condition next = front;
next.pos[0] = !tmp;
next.pos[i] = next.pos[0];
next.operations.push({i, next.pos[0]});
bfs.push(next);
}
front.pos[i] = tmp;
}
}
}
cout << cnt;
return 0;
}
```
# [z015](https://judge.cp.ccns.io/problem/z015)：
走路沒什麼好說的，直接 BFS 即可。
下坡車就是多了兩個限制條件：
- 每次都要走**嚴格遞減**高度的路
```cpp
if(vis[v] || K[v] >= K[u]) continue;
```
- 並且挑的路(`ori`)要是**最陡**(`stp`)的
```cpp
if(stp > K[v]) stp = K[v], ori = v;
```
綜合起來：
```cpp
int stp = K[u], ori = -1; // steep, orientation
for(auto v: E[u]) {
if(vis[v] || K[v] >= K[u]) continue;
if(stp > K[v]) stp = K[v], ori = v;
}
if(ori != -1) {
vis[ori] = true;
car.push({ori, t+1});
}
```
以下完整解題程式碼：
```cpp
#include<bits/stdc++.h>
using namespace std;
int const maxn = 1e4 + 10;
int T, N, M, S, K[maxn];
bool vis[maxn];
vector<int> E[maxn];
int main()
{
int kase = 0;
scanf("%d", &T);
while(T--) {
vector<int> tmp[maxn]; swap(E, tmp); // E 初始化
scanf("%d%d%d", &N, &M, &S);
for(int i = 0; i < N; i++) scanf("%d", &K[i]);
for(int i = 0; i < M; i++) {
int u, v;
scanf("%d%d", &u, &v);
E[u].push_back(v);
E[v].push_back(u);
}
int low = *min_element(K, K+N); //lowest
int time1 = -1, time2 = -1;
// walk time computing
queue<pair<int, int> > wlk; // walk
memset(vis, false, sizeof vis);
wlk.push({S, 0});
vis[S] = true;
while(!wlk.empty()) {
int u, t;
tie(u, t) = wlk.front(); wlk.pop();
if(K[u] == low) { time1 = t; break; }
for(auto v: E[u]) {
if(vis[v]) continue;
vis[v] = true;
wlk.push({v, t+6});
}
}
// car time computing
queue<pair<int, int> > car;
memset(vis, false, sizeof vis);
car.push({S, 0});
vis[S] = true;
while(!car.empty()) {
int u, t;
tie(u, t) = car.front(); car.pop();
if(K[u] == low) { time2 = t; break; }
int stp = K[u], ori = -1; // steep, orientation
for(auto v: E[u]) {
if(vis[v] || K[v] >= K[u]) continue;
if(stp > K[v]) stp = K[v], ori = v;
}
if(ori != -1) {
vis[ori] = true;
car.push({ori, t+1});
}
}
// print answer
printf("Case #%d: ", ++kase);
if(time2 == -1) {
if(time1 == -1) puts("Call 119!");
else printf("%d\n", time1);
} else printf("%d\n", time1 - time2);
}
return 0;
}
```
Sign in with Wallet
Connect another wallet