Try   HackMD

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 符合
ai>aj>ak
,也就是「三元逆序數對」。

Subtask 1
   O(N3)

用迴圈尋找所有的

i,j,k ,並判斷是否符合
ai>aj>ak

Subtask 2
   O(N2)

每次

O(N) 尋找有多少的
i<j
ai>aj
以及
k>j
aj>ak
,並將兩者相乘即是以
aj
為中間的三元逆序數對數量,只要枚舉所有的
j
並加總即可。

Subtask 3
   O(N+N log N)

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

註:因為

ai
109
,所以需離散化。

標準程式

#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
相連,但
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
  2. 7,8
  3. 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 號連通塊和諧

雖然它早已和諧

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

也就是說若含

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) 則要讓
1n
盡量長,
而路徑是
1abn
1ban

這裡

xy
x
y
的最短路徑

dx(y)
xy
的長度

1abn 的長度就是
d1(a)+1+dn(b)

若最短路徑是

1abn
則長度會有
d1(a)+1+dn(b)d1(b)+1+dn(a)

而任意特殊點對(邊)

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

會有三個不等式要滿足,假設為
d1(a)+1+dn(b)<d1(b)+1+dn(a)

d1(b)+1+dn(c)<d1(c)+1+dn(b)

d1(c)+1+dn(a)<d1(a)+1+dn(c)

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

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

d1(a)dn(a)<d1(b)dn(b)
d1(b)dn(b)<d1(c)dn(c)

d1(c)dn(c)<d1(a)dn(a)

再化簡
d1(a)dn(a)<d1(b)dn(b)<d1(c)dn(c)<d1(a)dn(a)

會發現得得到矛盾的結論

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

d1(a)dn(a)<d1(b)dn(b)<d1(c)dn(c)
則回推的不等式為
d1(a)+1+dn(b)<d1(b)+1+dn(a)

d1(b)+1+dn(c)<d1(c)+1+dn(b)

d1(a)+1+dn(c)<d1(c)+1+dn(a)

所以要比較這三者的大小
d1(a)+1+dn(b),d1(b)+1+dn(c),d1(a)+1+dn(c)

推廣至一般狀況,若是

d1(a1)dn(a1)<d1(a2)dn(a2)<<d1(ak)dn(ak)
則可只比較所有
d1(ax)+1+dn(ay)
其中
1x<yk

解法 2

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

設特殊點

a,b 滿足
d1(a)<d1(b)
有雙向邊
(a,b)
,則有三種情況需考慮﹔

  • d1(n)<d1(a)<d1(b)

    最短路徑不經過
    a,b
  • d1(a)<d1(n)<d1(b)

    最短路徑不經過
    b
  • d1(a)<d1(b)<d1(n)

    d1(a)+1<d1(b)+1
    ,且
    dn(b)
    dn(a)
    只相差
    1

    若是
    x{a,b}.d1(x)+dn(x)>d1(n)
    ,則最短路徑不經過
    x

由上推得

d1(a)+1+dn(b)d1(b)+1+dn(a)
所以特殊點依照 BFS 的深度排列,比較所有
d1(ax)+1+dn(ay)
其中
1x<yk
得解

標準程式

解法 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;
}