第二場比賽題解

啦啦啦大家加油

z011：

很直覺的，每次挑選最小的兩個數字相加起來，成本一定最少
最後總成本也會是所有方法中最少的
於是先構造一個能夠每次將最小數字拿出來的 priority_queue：

priority_queue<long long, vector<long long>, greater<long long> > PQ;

也可將數字變為負數推入 priority_queue，推出後再變回正數，也是當前最小的數字
還記得 STL 的 priority queue 的 front 會優先選容器中最大的元素吧?

接著將兩個最小數相加，推回 PQ 中就行了：

long long a = PQ.top(); PQ.pop();
long long b = PQ.top(); PQ.pop();
cost += a += b;
PQ.push(a);

以下完整解題程式碼：

#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：

這題在一開始就不保證每個點是連通的喔！
這題需要從

D

大往

D

小的方式去做
利用 Disjoint sets 的特性去知道在剩餘的網路結構下，有幾個不同的連通圖
此時需要重建的網路線就是連通圖個數-1
然後再依照

D

變小的條件維護剩餘的網路結構下，有幾個不同的連通圖，此時需要重建的網路線就是連通圖個數-1
…直到做完所有的

D

#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：

基於朋友的朋友還是自己的朋友，所以在這圈子挑個黃金需求最少的角色賄賂就行
也就是對於第

i

個人，將這個圈子 (

i

與朋友們) 都遍歷一遍，算出最小的黃金(g)
並累加起來：

dfs(i, g);
sum += g;

而走過的第

p

位角色會設為：

vis[p] = true;

所以這個圈子下次不會再次拜訪。

而 dfs 將當前最小的黃金 (gold) 與鄰點的

C_{v}

比較，然後更新其 gold
(這裡 gold 是以傳參考的方式)

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);
  }
}

以下完整解題程式碼：

#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：

這是一題 BFS 或 DFS，簡單來說，儲存一個狀態，包含 yuri、WOLF、KIILITOU、CORN 的位置，不斷檢查下一個步驟可以做哪些行動，保證東西不會被吃掉，直到步數等於

N

。
特別要注意的是如果已經完成，便不能再開船，例如在七步的時候運完所有東西，就不能再開船將 KIILITOU 帶走，不然會被白眼。這個部分包含我在內有三個人寫錯，結果大家都寫出假 AC。
Code:

#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：

走路沒什麼好說的，直接 BFS 即可。
下坡車就是多了兩個限制條件：

每次都要走嚴格遞減高度的路

if(vis[v] || K[v] >= K[u]) continue;

並且挑的路(ori)要是最陡(stp)的

if(stp > K[v]) stp = K[v], ori = v;

綜合起來：

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});
}

以下完整解題程式碼：

#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;
}

第二場比賽 題解

z011：

z012：

z013：

z014：

z015：

第二場比賽題解