2020 高階競程 Contest #2 - 題解

藍的競程之旅–藍的夢

• Task Provider:ian
• Task Setter:ian

首殺 team20_23 (00:04)

解法說明

因為記憶體很小所以不能開陣列儲存數字，只能用 counting sort 解

標準程式

#include <bits/stdc++.h>
using namespace std;

int n, tmp, i;
int cnt[110];

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  for (i = 0; i < n; i++) {
    cin >> tmp;
    cnt[tmp]++;
  }
  for (i = 100; i > 0; i--) {
    while (cnt[i] --> 0) {
      cout << i << " ";
    }
  }
  cout << endl;
  return 0;
}

數根

• Task Provider:ian
• Task Setter:ian

首殺 team20_49 (00:14)

解法說明

仔細看就會發現每九個就會重複一輪，所以就有以下的公式解

標準程式

#include <iostream>
using namespace std;

int main(void) {
    long long int n, a, b;
    cin >> n;
    while (n --) {
        cin >> a >> b;
        cout << b + 9 * (a - 1) << '\n';
    }

    return 0;
}

喵嗚朋友

• Task Provider:Miohitokiri5474
• Task Setter:Miohitokiri5474

首殺 – (-:-)

解法說明

想法很簡單，先將陣列開兩倍
一個人有兩個點

$i,i+n$ ，一個是紀錄朋友用的，另外一個是敵人

所以：

1. 如果
   $a,b$ 是朋友，則
   $a,b$ 應該要屬於同一個集合（
   $a+n,b+n$ 也屬於同一個集合）
2. 如果
   $a,b$ 是敵人，則
   $a,b+n$ 應該要屬於同一個集合（
   $a+n,b$ 也屬於同一個集合）

換成 code 的話應該會變成這樣：

• 如果
  $a,b$ 是朋友
  • Union ( a, b ), Union ( a + n, b + n );
• 如果
  $a,b$ 是敵人
  • Union ( a, b + n ), Union ( a + n, b );

換個簡單的說法，只要關係線有跨過

$n$ 就算是敵人

標準程式

解法 1

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

#define maxN 200005

int dis[maxN], sz[maxN];

inline void init ( void ){
    for ( int i = 0 ; i < maxN ; i++ )
        dis[i] = i;
}

int find ( int a ){
    return dis[a] == a ? a : dis[a] = find ( dis[a] );
}

inline void Union ( int a, int b ){
    dis[find ( a )] = find ( b );
}

inline bool same ( int a, int b ){
    return find ( a ) == find ( b );
}

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );

    int n, m, a, b, type, an, bn;
    cin >> n >> m;
    init();
    while ( m-- ){
        cin >> type >> a >> b;
        an = a + n, bn = b + n;
        if ( type == 1 ){
            if ( same ( a, bn ) || same ( an, b ) ){
                cout << "nani\n";
                continue;
            }
            Union ( a, b );
            Union ( an, bn );
        }
        else if ( type == 2 ){
            if ( same ( a, b ) || same ( an, bn ) ){
                cout << "nani\n";
                continue;
            }
            Union ( a, bn );
            Union ( b, an );
        }
        else if ( type == 3 ){
            if ( same ( a, b ) || same ( an, bn ) )
                cout << "friend\n";
            else if ( same ( an, b ) || same ( a, bn ) )
                cout << "enemy\n";
            else
                cout << "none\n";
        }
    }
}

解法 2

可以把 dsu 的值直接加負號如以下：

#include<bits/stdc++.h>
// by 藍
using namespace std;
int dsu[100005];
int findroot(int x){
    if(x > 0){
        if(dsu[x] == x) return x;
        return dsu[x] = findroot(dsu[x]);     
    }
    else {
        if(dsu[-x] == -x) return x;
        dsu[-x] = findroot(dsu[-x]);
        return -dsu[-x];
    }
}

int main() {
    int n,m;
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=0;i<=n;i++) {
        dsu[i]=i;
    }
    int a,b,c;
    while(m--) {
        cin>>c>>a>>b;
        a++;b++;
        if(c==1){
            if(findroot(a) == -findroot(b)){
                cout<<"nani"<<'\n';
                continue;
            }
            findroot(a);
            if(dsu[a]>0) 
                dsu[findroot(a)] = findroot(b);            
            if(dsu[a]<0) 
                dsu[-findroot(a)] = -findroot(b);            
        }
        if(c==2){
            if(findroot(a) == findroot(b)){
                cout<<"nani"<<'\n';
                continue;
            }
            findroot(a);
            if(dsu[a]>0) 
                dsu[findroot(a)] = -findroot(b);            
            if(dsu[a]<0) 
                dsu[-findroot(a)] = findroot(b);            
        }
        if(c==3){
            if(findroot(a) == findroot(b)){
                cout<<"friend\n";
            }
            else if(-findroot(a) == findroot(b)){
                cout<<"enemy\n";
            }
            else{
                cout<<"none\n";
            }

        }
    }

    return 0;
}

都市滑翔

• Task Provider:leo900807
• Task Setter:leo900807

首殺 – (-:-)

解法說明

本題要找出有幾組

$i,j,k$ 符合

$a_i>a_j>a_k$ ，也就是「三元逆序數對」。

Subtask 1

$O(N^3)$

用迴圈尋找所有的

$i,j,k$ ，並判斷是否符合

$a_i>a_j>a_k$ 。

Subtask 2

$O(N^2)$

每次

$O(N)$ 尋找有多少的

$i<j$ 且

$a_i>a_j$ 以及

$k>j$ 且

$a_j>a_k$ ，並將兩者相乘即是以

$a_j$ 為中間的三元逆序數對數量，只要枚舉所有的

$j$ 並加總即可。

Subtask 3

$O(N+N\log N)$

有了 Subtask 2 的想法後，可以將其改良，利用 merge sort 計算對於每個數字有多少比自己大的數字在前面，多少比自己小的數字在後面，最後相乘加總即可。

註：因為

$a_i$ 到

${10}^9$，所以需離散化。

標準程式

#include <iostream>
#include <algorithm>
#define F first
#define S second
using namespace std;

pair<int, int> a[800000];

long long tmp[800000], comb[800000][2], n;

void mergesort(int l, int r){
    int i, j, k, mid;
    if(l == r)
        return;
    mid = (l + r) / 2;
    mergesort(l, mid);
    mergesort(mid + 1, r);
    for(i = k = l, j = mid + 1; i <= mid && j <= r;){
        if(a[i] <= a[j]){
            comb[a[i].F][1] += j - (mid + 1);
            tmp[k++] = a[i++].F;
        }
        else{
            comb[a[j].F][0] += mid - i + 1;
            tmp[k++] = a[j++].F;
        }
    }
    while(i <= mid){
        comb[a[i].F][1] += r - (mid + 1) + 1;
        tmp[k++] = a[i++].F;
    }
    while(j <= r)
        tmp[k++] = a[j++].F;
    for(i = l; i <= r; i++)
        a[i].F = tmp[i];
}

inline bool restore(const pair<int, int> &a, const pair<int, int> &b){
    return a.S < b.S;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    long long count = 0;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i].F, a[i].S = i;
    sort(a, a + n);
    for(int i = 0; i < n; i++)
        a[i].F = i;
    sort(a, a + n, restore);
    mergesort(0, n - 1);
    for(int i = 0; i < n; i++)
        count += comb[i][0] * comb[i][1];
    cout << count << "\n";
}

和諧的圖

• Task Provider:ys
• Task Setter:raiso

首殺 – (-:-)

解法說明

解法 1

假設有點

$l<r$，

$l$ 和

$r$ 相連，但

$\mathrm{\forall }m.l<m<r$ 都沒有和

$l,r$ 相連，那麼就得把這些

$m$ 給加進圖裡 (有

$l,r$ 的這個圖)
換句話說，所有含有這種

$l,r$ 的連通塊，要和其他連通塊相連形成和諧的連通塊

例如圖中有這 5 個連通塊：

1. $1,5,6$
2. $2,3$
3. $4$
4. $7,8$
5. $9$

那麼 1 號連通塊滿足上述性質(不和諧)，所以從小到大要把

$2,3,4$ 這幾個數字納入 1 號連通圖
接著圖就會變成：

1. $1,2,3,4,5,6$
4. $7,8$
5. $9$

這樣整個圖就和諧了。

實作上會採用 Union-Find forest 作為不同連通塊之間的判斷
首先一個個數字

$l$ 去檢驗，含有

$l$ 的連通塊，是否和諧？

for(int l = 1; l <= n; l++) {
  :
  .
}

也就是對於當前

$l$ 到該連通塊中最大的數

$r$ 中所有

$m$，判斷

$m$ 是否在連通塊中，不在的話就把

$m$ 加進去 (加 1 條邊)

for(int m = l+1; m <= mx[Find(l)]; m++) {
  if(Find(l) == Find(m)) continue;
  else Union(l, m);
}

mx[Find(l)] 為含有

$l$ 的連通塊中的最大數，也就是

$r$
如何維護連通塊中的最大數請參考標準程式

實作的概念大致上是這樣，可是複雜度還是過高
但可以觀察到：

1. $1,2,3,4,5,6$
2. $7,8$
3. $9$

已經把 1 號連通塊和諧了，那麼下個數就挑

$7$ (1 號中最大數

$6$ 的下個數)
然後嘗試把含有

$7$ 的 2 號連通塊和諧

雖然它早已和諧 :+1:

也就是說若含

$l$ 的連通塊已和諧，則下個欲選擇的連通塊可挑含

$l$ 連通塊中最大數的下個數：

for(int l = 1, m; l <= n; l=m) {
  for(m = l+1; m <= mx[Find(l)]; m++) {
    if(Find(l) == Find(m)) continue;
    Union(l, m);
  }
}

標準程式

解法 1

#include<bits/stdc++.h>
using namespace std;

int const maxn = 2e5 + 10;

int n, m, gp[maxn], mx[maxn]; // gp := group, mx := maximum of group

int Find(int v) {
  if(v == gp[v]) return v;

  int rt = Find(gp[v]); // rt := root of the group
  mx[rt] = max(mx[rt], mx[v]);
  return gp[v] = rt;
}

void Union(int u, int v) {
  int a = Find(u), b = Find(v);
  gp[a] = b;
  mx[a] = mx[b] = max(mx[a], mx[b]);
}

int main()
{
  scanf("%d%d", &n, &m);
  for(int v = 1; v <= n; v++) gp[v] = mx[v] = v;

  for(int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    Union(u, v);
  }

  int cnt = 0;
  for(int u = 1, v; u <= n; u=v)
    for(v = u+1; v <= mx[Find(u)]; v++) {
      if(Find(u) == Find(v)) continue;
      Union(u, v);
      cnt++;
    }

  printf("%d\n", cnt);

  return 0;
}

解法 2

#include <bits/stdc++.h>
using namespace std;
 
int n, m;
vector<int> boss;
vector< pair<int, int> > bound; //定義一個連通圖的上下界
 
int fboss(int a) {
	return boss[a] = (boss[a] == a)? a: fboss(boss[a]);
}
 
 
int main() {
 
	cin >> n >> m;
	boss.resize(n);
	bound.resize(n);
	for(int i = 0; i < n; i++) {
		boss[i] = i;
		bound[i] = make_pair(i, i);
	}
	for(int i = 0; i < m; i++) {
		int a, b;
		int ba, bb;
		cin >> a >> b;
		a--, b--;
		ba = fboss(a);
		bb = fboss(b);
		boss[bb] = ba;
	}
 
	for(int i = 0; i < n; i++) {
		int bs = fboss(i);
		if(bs != i) bound[i].first = bound[i].second = 2e9;
		bound[bs].first = min(bound[bs].first, i);
		bound[bs].second = max(bound[bs].second, i);
	}

	int ans = 0;
	sort(bound.begin(), bound.end());
	for(int i = 0; i < n-1 && bound[i+1].first < 1e9; i++) {
		int j = i+1;
		int upperb = bound[i].second;
		while(upperb >= bound[j].first) {
			upperb = max(upperb, bound[j].second);
			ans++, j++;
		}
		i = j-1;
	}
	cout << ans << endl;
	return 0;
}

母牛與農地

• Task Provider:ys
• Task Setter:raiso

首殺 team20_12 (02:05)

解法說明

解法 1

明顯的，在加入一條邊之後或多或少會讓最短路更短

• 如果更短了，肯定是最短路徑用了新加的這條邊
• 如果沒有改善，那就是最短路徑沒有改走新加的邊

也就是說，只需關心當最短路徑用了新加的邊的狀況
那麼設此邊為

$(a,b)$ 則要讓

$1⇝n$ 盡量長，
而路徑是

$1⇝a\to b⇝n$ 或

$1⇝b\to a⇝n$

這裡

$x⇝y$ 是

$x$ 到

$y$ 的最短路徑

設

$d_x(y)$ 為

$x⇝y$ 的長度

則

$1⇝a\to b⇝n$ 的長度就是

$d_1(a)+1+d_n(b)$

若最短路徑是

$1⇝a\to b⇝n$
則長度會有

$d_1(a)+1+d_n(b)\le d_1(b)+1+d_n(a)$

而任意特殊點對(邊)

$(a,b)$ 都得滿足此不等式，也就是例如有點對

$(a,b),(b,c),(c,a)$
會有三個不等式要滿足，假設為

$d_1(a)+1+d_n(b)<d_1(b)+1+d_n(a)$

$d_1(b)+1+d_n(c)<d_1(c)+1+d_n(b)$

$d_1(c)+1+d_n(a)<d_1(a)+1+d_n(c)$

在特殊點為三個以上，就不會出現等於關係了

會發現這些不等式能化簡成

$d_1(a)-d_n(a)<d_1(b)-d_n(b)$

$d_1(b)-d_n(b)<d_1(c)-d_n(c)$

$d_1(c)-d_n(c)<d_1(a)-d_n(a)$
再化簡

$\underset{―}{d_1(a)-d_n(a)}<d_1(b)-d_n(b)<d_1(c)-d_n(c)<\underset{―}{d_1(a)-d_n(a)}$
會發現得得到矛盾的結論

所以須從確定的結論往前推，不失一般性的，設有

$d_1(a)-d_n(a)<d_1(b)-d_n(b)<d_1(c)-d_n(c)$
則回推的不等式為

$d_1(a)+1+d_n(b)<d_1(b)+1+d_n(a)$

$d_1(b)+1+d_n(c)<d_1(c)+1+d_n(b)$

$d_1(a)+1+d_n(c)<d_1(c)+1+d_n(a)$
所以要比較這三者的大小

$d_1(a)+1+d_n(b),d_1(b)+1+d_n(c),d_1(a)+1+d_n(c)$

推廣至一般狀況，若是

$d_1(a_1)-d_n(a_1)<d_1(a_2)-d_n(a_2)<\cdots <d_1(a_k)-d_n(a_k)$
則可只比較所有

$d_1(a_x)+1+d_n(a_y)$ 其中

$1\le x<y\le k$

解法 2

同樣只關心有加入新邊的情況

設特殊點

$a,b$ 滿足

$d_1(a)<d_1(b)$ 有雙向邊

$(a,b)$，則有三種情況需考慮﹔

• $d_1(n)<d_1(a)<d_1(b)$
  最短路徑不經過
  $a,b$
• $d_1(a)<d_1(n)<d_1(b)$
  最短路徑不經過
  $b$
• $d_1(a)<d_1(b)<d_1(n)$
  
  $d_1(a)+1<d_1(b)+1$，且
  $d_n(b)$ 與
  $d_n(a)$ 只相差
  $1$
  若是
  $x\in \{a,b\}.d_1(x)+d_n(x)>d_1(n)$，則最短路徑不經過
  $x$。

由上推得

$d_1(a)+1+d_n(b)\le d_1(b)+1+d_n(a)$
所以特殊點依照 BFS 的深度排列，比較所有

$d_1(a_x)+1+d_n(a_y)$ 其中

$1\le x<y\le k$ 得解

標準程式

解法 1

#include<bits/stdc++.h>
using namespace std;

int const maxn = 2e5 + 10;

int n, m, k, x, y;
vector<int> E[maxn], a;

void bfs(int s, vector<int> &d) {
  queue<int> q;
  set<int> vis;
  q.push(s);
  vis.insert(s);
  d[s] = 0;
  while(q.size()) {
    int u = q.front(); q.pop();
    for(int v: E[u]) {
      if(vis.count(v)) continue;
      vis.insert(v);
      d[v] = d[u] + 1;
      q.push(v);
    }
  }
}

int main()
{
  scanf("%d%d%d", &n, &m, &k);

  a.resize(k);
  for(int i = 0; i < k; i++) scanf("%d", &a[i]);
  for(int i = 0; i < m; i++) {
    scanf("%d%d", &x, &y);
    E[x].push_back(y);
    E[y].push_back(x);
  }

  vector<int> d1(n+1), dn(n+1);
  bfs(1, d1);
  bfs(n, dn);

  sort(a.begin(), a.end(), [&](int x, int y) { return d1[x]-dn[x] < d1[y]-dn[y]; });

  int ans = 0, d1_mx = 0;
  for(int i = 0; i+1 < k; i++) {
    d1_mx = max(d1_mx, d1[a[i]]);
    ans = max(ans, d1_mx + 1 + dn[a[i+1]]);
  }

  printf("%d\n", min(ans, d1[n]));

  return 0;
}

解法 2

#include<bits/stdc++.h>
using namespace std;

int const maxn = 2e5 + 10;

int n, m, k, a, x, y;
vector<int> E[maxn], ord; // ord := order
vector<bool> sp; // sp := special

void bfs(int s, vector<int> &d) {
  queue<int> q;
  q.push(s);
  d.assign(n+1, -1);
  d[s] = 0;

  while(q.size()) {
    int u = q.front(); q.pop();
    if(s == 1 && sp[u]) ord.push_back(u);

    for(int v: E[u]) {
      if(d[v] != -1) continue;
      d[v] = d[u] + 1;
      q.push(v);
    }
  }
}

int main()
{
  scanf("%d%d%d", &n, &m, &k);

  sp.assign(n+1, false);
  for(int i = 0; i < k; i++) scanf("%d", &a), sp[a] = true;
  for(int i = 0; i < m; i++) {
    scanf("%d%d", &x, &y);
    E[x].push_back(y);
    E[y].push_back(x);
  }

  vector<int> d1, dn;
  bfs(1, d1);
  bfs(n, dn);

  int ans = 0, d1_mx = 0;
  for(int i = 0; i+1 < ord.size(); i++) {
    d1_mx = max(d1_mx, d1[ord[i]]);
    ans = max(ans, d1_mx + 1 + dn[ord[i+1]]);
  }

  printf("%d\n", min(ans, d1[n]));

  return 0;
}