2021 高階競程 Contest #8 - 題解

意義不明的糖果

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，使用現成演算法進行求解

標準程式

解法 1

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

解法 2

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

鎮長小嵐

Task Provider: D4nnyLee
Task Setter: D4nnyLee

首殺 team21_24 (00:26)

解法說明

令

a_{i}

為門牌號碼為

i

的住戶的收入。

定義

f (i) = {\begin{matrix} 0, & if a_{i} > y \\ 1, & otherwise \end{matrix}

可以發現陣列

a

透過

f

映射之後會有單調性，
因此我們只要在映射之後的陣列上面做二分搜即可。

標準程式

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

今天的塔矢亮不開心

Task Provider: CF 1622 C
Task Setter: raiso

首殺 team21_23 (00:51)

解法說明

思考
$A$ 矩陣的順序是否影響最終結果？否
思考「減法」在「同化」之前是否只有好處沒有壞處？是
本題枚舉同化人數
$t$ ，從
$0$ 到
$N - 1$ ，找出不同
$t$ 所需要的操作數量。
- 同化的對象為
  $A$ 矩陣中的較大值，目標為
  $A$ 矩陣中最小值，所以先將
  $A$ 從小到大排序
- $Σ$ IQ =
  $A_{1} + . . + A_{N - t} + t * A_{1}$
- 操作數量 =
  $A_{1}$ 的減法次數
  $+ t$
針對每個
$t$ 計算
$A_{1}$ 所需要的減法次數。
補充說明：範例code中的
$(X + t) / (t + 1)$ 為除法取頂的實作方案。

標準程式

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

產業鏈

Task Provider: leo
Task Setter: leo

首殺 – (-:-)

解法說明

題目的要求是你要將一張無向圖的點分成兩個點集，
其中某些點要在點集

X

，另一些點要在點集

Y

。
而且要使得不跨點集的那些邊的權重和最大。

可以假設一開始可以獲得所有的經濟效益，
且把一個點分配在點集

X

，則該點屬於源點這一邊；
如果分配在點集

Y

則在匯點這邊。
題目的要求變成是要使得跨越點集那些邊的權重和最小，
則這道題目就變成最小割問題。

再考慮那些必定在點集

X

的那些點，
因為那些點不可以被分配到匯點的那一側，
所以從源點連接一條流量無限大的邊到那些點，
同理，必定在點集

Y

的那些點，
則連接一條流量無限大的邊到匯點。

就可以跑一次從源點到匯點的最小割，
再用總經濟效益減掉最小割的值即為答案。

請注意：本題所有的邊都需要建雙向邊。

題外話：
如果題目沒有限制某些企業需要在某個廠區，
則此題會變成全域最小割問題，
有興趣的人可以自己上網搜尋解法。

標準程式

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

時空旅人小嵐

Task Provider: arashi87
Task Setter: arashi87

首殺 – (-:-)

解法說明

這題就是很單純的最短路而已，並沒卡特別的東西，唯一的難點就在於怎麼建邊而已，因為按照題目的規則在樓層間最多可以建到

445^{445}

條邊，因此樓層間的邊不能用常規的方法建。
所以在這題我們對於樓層間邊的建法需要用到一點小技巧，對於每層樓我們都多開一個虛點代表，兩層樓間需要相連的教室通通都連到這個虛點就行，這樣邊數就會從

N^{2}

退化到

2 N

，但這樣還會有個問題是題目要求同樓層的教室不能相連，因此對於第

L_{i}

層樓連到

L_{i + 1}

層的邊通通是單向邊，連到

L_{i - 1}

的邊是雙向邊就能解決這問題了。
邊建完後跑一次最短路就行了。

標準程式

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

渣男小嵐

Task Provider: XDEv11
Task Setter: ys

首殺 team21_24 (03:23)

解法說明

我們先將

n, m

變為一樣大，再將不存在的邊補全，這題就是個很標準的匈牙利演算法的問題；至於不存在的邊該補成什麼，因為題目要求最大權最大匹配，我們可以將邊補成一個很大的負數，來確保轉化後的圖的最大權完美匹配，一定會是一個最大匹配。

標準程式

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

史萊姆農場

Task Provider: GY
Task Setter: ys

首殺 team21_24 (01:48)

解法說明

問題是在求

\sum_{i = 2}^{n} \sum_{j = 1}^{i - 1} gcd (a_{j}, a_{j + 1}, \dots, a_{i})

枚舉每個區間，並利用重疊的區間減少計算量，其複雜度為

O (n^{2})

例如計算
$gcd (a_{1}, \dots, a_{4})$ 可用已經算過的
$gcd (a_{1}, \dots, a_{3})$ 來算

由於這種作法複雜度過高，需要再仔細觀察問題特性，以減少計算量

令

(a_{k})_{k = j}^{i} = gcd (a_{j}, a_{j + 1}, \dots, a_{i})

會發現

(a_{k})_{k = i}^{i} \geq (a_{k})_{k = i - 1}^{i} \geq \dots \geq (a_{k})_{k = 1}^{i}

並且對任意的

i \leq n

最多只會有

O (\log_{2} a_{k})

個相異的

(a_{k})_{k = j}^{i}

因為一個數
$x$ 的質因數個數不超過
$\log_{2} x$ 個

於是對每個

i

找出這些相異數

{(a_{k})_{k = j}^{i} ∣ j \leq i}

且乘上對應的數量，接著加總起來就行

解法 1

對於每個

i \in [2, n]

在

[1, i]

找到所有

m

個位置

X

滿足

(a_{k})_{k = X_{1}}^{i} \neq (a_{k})_{k = X_{2}}^{i} \neq \dots \neq (a_{k})_{k = X_{m}}^{i}

將這些相異數一個個跟

a_{i + 1}

取 GCD，會得到

(a_{k})_{k = X_{1}}^{i + 1}, (a_{k})_{k = X_{2}}^{i + 1}, \dots, (a_{k})_{k = X_{m}}^{i + 1}

若

y_{1}, y_{2} \in X

有

(a_{k})_{k = y_{1}}^{i + 1} = (a_{k})_{k = y_{2}}^{i + 1}

則保留其中一個，這樣就得到對於

i + 1

的所有相異數

實作上對於

i

用陣列 num 存相異數

{(a_{k})_{k = j}^{i - 1} ∣ j \leq i - 1}

、陣列 cnt 存對應的個數
而 _num 及 _cnt 分別會暫存對於

i

的相異數

{(a_{k})_{k = j}^{i} ∣ j \leq i}

及其對應的個數

解法 2

對於每個

i \in [2, n]

有

(a_{k})_{k = i}^{i} \geq (a_{k})_{k = i}^{i + 1} \geq \dots \geq (a_{k})_{k = i}^{n}

對任意

j \geq i

能找到

(a_{k})_{k = i}^{j}

的 lower bound 以及 upper bound
且可以順便得知下個相異於

(a_{k})_{k = i}^{j}

的數的位置

實作上對於任意

i, j

採用 Sparse Table 查詢

(a_{k})_{k = i}^{j}

的值，並用二分搜找出 bound

標準程式

解法 1

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

解法 2

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

撿紅包遊戲

Task Provider: ccbeginner
Task Setter: ccbeginner

首殺 – (-:-)

解法說明

先把題目給出的矩陣變成一個二分圖，假設有兩個子圖

X, Y

，

X

有

n

個節點，

Y

有

m

個節點，然後如果第

i

行第

j

列的數字大於

0

，就把

X_{i}

跟

Y_{j}

連一條邊起來。

然後……就是求整張圖的最小生成樹啦～
最小生成樹上的錢錢數量就是大人拿到的數量。
最後再把圖上權重和減掉最小生成樹上的權重和就是答案。

標準程式

/* 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;
}

2021 高階競程 Contest #8 - 題解

首殺 team21_24 (00:04)

解法說明

解法 1

解法 2

標準程式

首殺 team21_24 (00:26)

解法說明

標準程式

首殺 team21_23 (00:51)

解法說明

標準程式

首殺 – (-:-)

解法說明

標準程式

首殺 – (-:-)

解法說明

標準程式

首殺 team21_24 (03:23)

解法說明

標準程式

首殺 team21_24 (01:48)

解法說明

解法 1

解法 2

標準程式

首殺 – (-:-)

解法說明

標準程式

Read more

2020 Week 7: Dynamic Programming

2020 Week 1: Introduction

2020 Week 4: Search

2020 Week 14: Number theory