---
tags: 成大高階競技程式設計 2021
image: https://i.imgur.com/IIj9BcL.png
---

# 2021 高階競程 Contest #2 - 題解

## [無線通訊網路](https://judge.csie.ncku.edu.tw/problems/94)
- Task Provider: leo
- Task Setter: leo

### 首殺 team21_28 (00:28)

### 解法說明

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

P.S. 題目測資的輸入中，$M$ 其實都是 $N-1$，題目中 $M$ 的範圍算是一種誤導

### 標準程式
:::spoiler

#include <iostream>
using namespace std;

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

:::

## [我叫做偉杰，是個會計師](https://judge.csie.ncku.edu.tw/problems/95)
- Task Provider: ys
- Task Setter: ys

### 首殺 team21_09 (00:42)

### 解法說明
#### 解法 1
觀察當 $a$ 長度為 $3$ 的情況 (因為足夠小 以便摸索解法)
如 $a = (x, -1, y)$

不失一般性的設 $x < y$
1. 若 $k \le x$ 則 $m \ge y-x$
2. 若 $k \ge y$ 則 $m \ge y-x$
3. 若 $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 \ge z$ 得 $k > x$ (因 $x$ 是最小值)，但 $k-z > k-x \implies z < x$ 矛盾
或若 $k \le z$ 得 $k < y$ (因 $y$ 是最大值)，但 $z-k > y-k \implies 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{split}
&\implies y - k = k - x \\
&\implies k = {{x+y} \over 2}
\end{split}
$$

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

#### 解法 3
根據**解法 1** 的結論，$m$ 對 $k$ 的函數是類似二次函數的凸函數
也就是說，該函數的斜率是**單調的**，所以可以用**二分搜**來找 $k$

實作上，利用解法 1 的程式 `double m(double k)`
透過 `m(k+0.01) - m(k) > 0` 就能知道在 `k` 上 `m(k)` 的**變化**是否為遞增
> 此變化量也可以看做是該函數在 $k$ 上的微分

### 標準程式

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

:::

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

:::

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

:::

## [驗收成果](https://judge.csie.ncku.edu.tw/problems/96)
- Task Provider: D4nnyLee
- Task Setter: D4nnyLee

### 首殺 team21_12 (02:30)

### 解法說明

這題可以用**二分搜**來解。

首先我們先定義 $seg$ 代表所有合併前的陣列，$seg_i$ 代表第 $i$ 個陣列，
然後再寫一個函式 $cnt$，使得 $cnt(seg, x)$ 是所有 $seg$ 的陣列中，小於 $x$ 的元素數量。

因為每個 $seg_i$ 都有規律，所以要算出 $cnt(seg, x)$ 其實不難。

有了 $cnt$ 之後，可以發現這題的答案有**單調性**，
因為 $cnt(seg, x) \leq cnt(seg, x + 1)$ 一定成立。

假設最後的答案為 $ans$，則 $cnt(seg, ans) \leq k$ 必定成立。

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

題目要找的就是一個最大的整數 $ans$，使得 $cnt(seg, ans) \leq k$。

### 標準程式

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

:::spoiler

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

:::

## [著色遊戲](https://judge.csie.ncku.edu.tw/problems/96)
- Task Provider: alan8585
- Task Setter: leo

### 首殺 -- (-:-)

### 解法說明

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

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

時間複雜度為輸入的 $O(NM)$，
加上每次合併查詢操作的 $O(\alpha(NM))$，
乘上操作次數 $Q$，總複雜度為 $O(NM+Q\cdot\alpha(NM))$。

### 標準程式
:::spoiler

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

:::

## [每個人都需要一個機器貓朋友](https://judge.csie.ncku.edu.tw/problems/98)
- 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$，當我們將問題思考到這邊的時候，就完成了這題的要求。
前綴和的逆序數對數量就是解。

### 標準程式
:::spoiler 解法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;
}

:::

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

:::