2021 高階競程 Contest #2 - 題解

無線通訊網路

Task Provider: leo
Task Setter: leo

首殺 team21_28 (00:28)

解法說明

「保證任兩個不同的基地台都有辦法互相傳輸資料，
且兩基地台之間傳輸資料的路徑唯一。」
題目敘述最後的這句話是關鍵，
因為這句話代表了一張圖是聯通的，
且兩點之間的路徑唯一。
由這兩點可以推導出題目給定的是一棵樹，
那麼樹的著色問題就簡單了。
當節點只有一個時，僅需一種顏色即可；
如果大於一個節點也只需兩種顏色。
可以看成你將樹隨便選一個根，
第一層塗成顏色

A

，第二層塗成顏色

B

，第三層塗成顏色

A

，…
即可將所有節點著色完畢，且相鄰節點顏色不同。

P.S. 題目測資的輸入中，

M

其實都是

N - 1

，題目中

M

的範圍算是一種誤導

標準程式

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << (n == 1 ? 1 : 2) << "\n";
}

我叫做偉杰，是個會計師

Task Provider: ys
Task Setter: ys

首殺 team21_09 (00:42)

解法說明

解法 1

觀察當

a

長度為

3

的情況 (因為足夠小以便摸索解法)
如

a = (x, - 1, y)

不失一般性的設

x < y

若
$k \leq x$ 則
$m \geq y - x$
若
$k \geq y$ 則
$m \geq y - x$
若
$x < k < y$ 則
$m = max (k - x, y - k) < y - x$

所以要將

k

落在 3. 的條件下才使

m

盡量小

再細看

x < k < y

從

k = x + 1

遞增至

y - 1

會發現

k

與

x

絕對差越來越大，而與

y

絕對差越來越小
在這之中

k

與

x, y

的兩個絕對差會逐步至一個最小對，接著再增大

$m$ 則從這對中找最大的那個

反之從

k = y - 1

遞減至

x + 1

也一樣

這貌似是個類似二次函數的凸函數 (

f : k \mapsto m

) (只有一個局部極值)
若是能證明任意長度的

a

都有此函數特性，那麼可以用三分搜解決

不用管不與

$k$ 相鄰的絕對差，
因為不與

k

相鄰的絕對差之中的最大值

t

永遠都不會變動，
也就是說若函數擁有理想上的特性，那麼

m

在遞減時也只會降到

t

。

而與

$k$ 相鄰的絕對差，也只需要關心最大值

y

與最小值

x

因為若存在介於

x, y

的數

z

使得

| k - z | > max (| k - y |, | k - x |)

則若

k \geq z

得

k > x

(因

x

是最小值)，但

k - z > k - x ⟹ z < x

矛盾
或若

k \leq z

得

k < y

(因

y

是最大值)，但

z - k > y - k ⟹ z > y

矛盾

$| k - z |$ 帶絕對值，所以要拆兩狀況論證

也就是說，任意長度的

a

可類比為長度

3

的情況

解法 2

根據解法 1 的結論，只需找出與

k

相鄰數字中的最大值

y

與最小值

x

則

m = max (y - k, k - x)

，可根據該式直接計算出

k

為多少
題目要求

m

的最小值，則該值為

m^{'} = y - k

與

m^{'} = k - x

的交點

\begin{aligned} ⟹ y - k = k - x \\ ⟹ k = \frac{x + y}{2} \end{aligned}

解法 1 沒有給出
$k$ 應為多少，得用找的

解法 3

根據解法 1 的結論，

m

對

k

的函數是類似二次函數的凸函數
也就是說，該函數的斜率是單調的，所以可以用二分搜來找

k

實作上，利用解法 1 的程式 double m(double k)
透過 m(k+0.01) - m(k) > 0 就能知道在 k 上 m(k) 的變化是否為遞增

此變化量也可以看做是該函數在
$k$ 上的微分

標準程式

解法 1

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

int constexpr maxn = 5e5 + 10;

int n;
vector<double> a;

double m(double k) {
  double mx = 0; // maximum of absolute differences

  for(int i = 0; i+1 < n; i++) {
    double x = a[ i ]==-1? k : a[ i ];
    double y = a[i+1]==-1? k : a[i+1];

    mx = max(mx, abs(x - y));
  }

  return mx;
}

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

  a.resize(n);
  for(double &v: a) scanf("%lf", &v);

  double l = 0, r = 1e9+10;
  while(r - l > 0.01) {
    double k1 = l + (r-l)/3, k2 = r - (r-l)/3;
    if(m(k1) > m(k2)) l = k1;
    else r = k2;
  }

  printf("%.1lf\n", m(l));

  return 0;
}

解法 2

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

int constexpr maxn = 5e5 + 10;

int n;
double a[maxn];

int main()
{
  scanf("%d", &n);
  for(int i = 0; i < n; i++) scanf("%lf", &a[i]);

  double mx = 0, mi = 1e9;
  for(int i = 0; i < n; i++) {
    bool c1 = i >  0  && a[i-1] == -1 && a[i] != -1;
    bool c2 = i < n-1 && a[i+1] == -1 && a[i] != -1;

    if(c1 || c2) mx = max(mx, a[i]), mi = min(mi, a[i]);
  }

  double m = 0, k = (mx+mi)/2.0;
  for(int i = 0; i < n; i++) if(a[i] == -1) a[i] = k;
  for(int i = 0; i+1 < n; i++) m = max(m, abs(a[i]-a[i+1]));

  printf("%.1lf\n", m);

  return 0;
}

解法 3

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

int const maxn = 5e5 + 10;

int n;
vector<double> a;

double m(double k) {
  double mx = 0; // maximum of absolute differences

  for(int i = 0; i+1 < n; i++) {
    double x = a[ i ]==-1? k : a[ i ];
    double y = a[i+1]==-1? k : a[i+1];

    mx = max(mx, abs(x - y));
  }

  return mx;
}

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

  a.resize(n);
  for(double &v: a) scanf("%lf", &v);

  double l = 0, r = 1e9+10;
  while(r - l > 0.01) {
    double k = (l + r)/2;
    if(m(k+0.01) - m(k) > 0) r = k;
    else l = k+0.01;
  }

  printf("%.1lf\n", m(l));

  return 0;
}

驗收成果

Task Provider: D4nnyLee
Task Setter: D4nnyLee

首殺 team21_12 (02:30)

解法說明

這題可以用二分搜來解。

首先我們先定義

s e g

代表所有合併前的陣列，

s e g_{i}

代表第

i

個陣列，
然後再寫一個函式

c n t

，使得

c n t (s e g, x)

是所有

s e g

的陣列中，小於

x

的元素數量。

因為每個

s e g_{i}

都有規律，所以要算出

c n t (s e g, x)

其實不難。

有了

c n t

之後，可以發現這題的答案有單調性，
因為

c n t (s e g, x) \leq c n t (s e g, x + 1)

一定成立。

假設最後的答案為

a n s

，則

c n t (s e g, a n s) \leq k

必定成立。

為什麼會有小於
$k$ 的情況呢？

用例子來做解釋：
假設
$[1, 1, 2, 2, 2, 3, 3, 3]$ 為所有區間合併並排序完後的數列，令
$k = 7$ ，
現在索引值為
$k$ 的元素的值是
$3$ ，但是所有小於
$3$ 的元素只有
$5$ 個。

題目要找的就是一個最大的整數

a n s

，使得

c n t (s e g, a n s) \leq k

。

標準程式

因為數字的範圍很大，用 int 很容易遇到整數溢位（Integer Overflow）的問題，
所以下面實作都使用 long long。

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

long long cnt(const vector<pair<long long, long long>>& seg, long long x) {
    long long num{0};

    for (auto [l, r] : seg)
        if (x > l) num += min(x - 1, r) - l + 1;

    return num;
}

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

    int n, k;
    cin >> n >> k;

    vector<pair<long long, long long>> seg(n);
    for (auto &[l, r] : seg)
        cin >> l >> r;

    long long l{-2000000000}, r{2000000000 + 1};
    while (r - l > 1) {
        long long mid{(l + r) / 2};

        if (cnt(seg, mid) <= k) l = mid;
        else r = mid;
    }

    cout << l << '\n';

    return 0;
}

著色遊戲

Task Provider: alan8585
Task Setter: leo

首殺 – (-:-)

解法說明

可以把每個格子都當成一個獨立節點，
若兩個節點相鄰的話可以合併成一個集合，
講到這邊會想到「併查集」這個資料結構。

因為併查集支援查詢與合併，
因此可以將所有輸入都讀進來，
並且反向操作，題目變成，
「給定一張最終的圖，每次操作將一個格子塗成白色，
請問每次操作後會有多少聯通塊，以及最大聯通塊大小為何」。
只要每次塗成白色，就將該節點與周圍白色的節點合併，
並且在合併過程取最大值即可。

時間複雜度為輸入的

O (N M)

，
加上每次合併查詢操作的

O (α (N M))

，
乘上操作次數

Q

，總複雜度為

O (N M + Q \cdot α (N M))

。

標準程式

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

const int MAXN = 3001, dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

bitset<MAXN> a[MAXN];

int n, m, boss[MAXN * MAXN], sz[MAXN * MAXN], mx, cnt;

pair<int, int> que[200000], ans[200000];

int find(int x){
    if(boss[x] == x)
        return x;
    return boss[x] = find(boss[x]);
}

void combine(int x, int y){
    x = find(x), y = find(y);
    if(x == y)
        return;
    sz[x] += sz[y];
    boss[y] = x;
    cnt--;
    mx = max(mx, sz[x]);
}

bool check(int x, int y){
    return x > 0 && x <= n && y > 0 && y <= m && !a[x][y];
}

int trans(int x, int y){
    return x * m + y;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int q;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        for(int j = 1, x; j <= m; j++)
            cin >> x, a[i][j] = x, boss[trans(i, j)] = trans(i, j), sz[trans(i, j)] = 1;
    for(int i = 0; i < q; i++){
        cin >> que[i].F >> que[i].S;
        a[que[i].F][que[i].S] = 1;
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(!a[i][j]){
                cnt++, mx = max(mx, 1);
                for(int k = 0; k < 2; k++){
                    int nx = i + dx[k], ny = j + dy[k];
                    if(check(nx, ny))
                        combine(trans(i, j), trans(nx, ny));
                }
            }
    for(int i = q - 1; i >= 0; i--){
        ans[i] = make_pair(cnt, mx);
        int x = que[i].F, y = que[i].S;
        a[x][y] = 0;
        cnt++;
        for(int j = 0; j < 4; j++){
            int nx = x + dx[j], ny = y + dy[j];
            if(check(nx, ny))
                combine(trans(x, y), trans(nx, ny));
        }
        mx = max(mx, sz[trans(x, y)]);
    }
    for(int i = 0; i < q; i++)
        cout << ans[i].F << " " << ans[i].S << "\n";
}

每個人都需要一個機器貓朋友

Task Provider: NHDK Moon Festival Ten Point Round 2021
Task Setter: raiso

首殺 team21_09 (02:40)

解法說明

首先，本題目是在找區間和

\leq 0

的個數，如果直接枚舉

L

與

R

，時間複雜度為

O (N^{3})

。
使用前綴和加速計算區間和，時間複雜度是

O (N^{2})

。

考慮到一個問題，區間和就是兩個前綴和相減，也就是尋找兩個前綴和，前面的前綴和大於後面的前綴和時，此對應的區間和就是

< 0

，當我們將問題思考到這邊的時候，就完成了這題的要求。
前綴和的逆序數對數量就是解。

標準程式

解法1






































#include <bits/stdc++.h>
#define pb push_back
#define Int long long
using namespace std;

Int invpair(vector<Int> &v, int l, int r) {
	if(l == r) return 0;
	int m = (l+r)/2;
	Int res = invpair(v, l, m) + invpair(v, m+1, r);
	vector<Int> tmp;
	for(int i = l, j = m+1; i <= m || j <= r; ) {
		if(i <= m && (j > r || v[i] <= v[j])) {
			tmp.pb(v[i++]);
			res += (j-m-1);
		}
		else tmp.pb(v[j++]);
	}
	for(auto it: tmp) v[l] = it, l++;
	return res;
}

void solve(){
	int n;
	cin >> n;
	vector<Int> A(n), B{0};
	for(auto& it: A) cin >> it;
	for(auto it: A) B.pb(B.back()+it); //len(B) == n+1
	Int ans = invpair(B, 0, n); //[L, R]
	cout << ans << endl;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	int t=1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

解法2



































































#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define add insert
#define Int long long
#define pi acosl(-1)
#define MEM(x) memset(x,0,sizeof(x))
#define x first
#define y second
using namespace std;

struct BIT {
	vector<Int> A;
	int n;
	BIT(int _n) {
		n=_n;
		A.resize(n+1);
	}

	int lowbit(int idx) {
		return (idx&(-idx));
	}

	void update(int idx, Int v) {
		for(int i = idx+1; i <= n; i += lowbit(i)) A[i] += v;
	}

	Int query(int idx)
	{
		Int res = 0;
		for(int i = idx+1; i; i -= lowbit(i)) res += A[i];
		return res;
	}
};


void solve(){
	int n; cin >> n;
	vector<Int> A(n), B{0}, Buni;
	for(auto& it: A) cin >> it;
	for(auto it: A) B.pb(B.back() + it);
	Buni = B;
	sort(Buni.begin(), Buni.end());
	Buni.erase(unique(Buni.begin(), Buni.end()), Buni.end());


	//BIT
	BIT T1(Buni.size());
	Int ans = 0;
	for(int i = 0; i < B.size(); i++) {
		int idx = lower_bound(Buni.begin(), Buni.end(), B[i]) - Buni.begin();
		Int cnt = i - T1.query(idx);
		ans += cnt;
		T1.update(idx, 1LL);
	}
	cout << ans << endl;


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

	int t=1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

2021 高階競程 Contest #2 - 題解

無線通訊網路

首殺 team21_28 (00:28)

解法說明

標準程式

我叫做偉杰，是個會計師

首殺 team21_09 (00:42)

解法說明

解法 1

解法 2

解法 3

標準程式

驗收成果

首殺 team21_12 (02:30)

解法說明

標準程式

著色遊戲

首殺 – (-:-)

解法說明

標準程式

每個人都需要一個機器貓朋友

首殺 team21_09 (02:40)

解法說明

標準程式

Read more

2020 Week 7: Dynamic Programming

2020 Week 1: Introduction

2020 Week 4: Search

2020 Week 14: Number theory