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

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

## [區間 xor](https://judge.csie.ncku.edu.tw/problems/104)
- Task Provider: leo
- Task Setter: leo

### 首殺 team21_25 (00:02)

### 解法說明

整數的 xor 運算符合以下條件，下方以「$\oplus$」當作 xor 運算符：

1. 交換律：$a\oplus b=b\oplus a$
2. 結合律：$(a\oplus b)\oplus c=a\oplus(b\oplus c)$
3. 單位元為 $0$：$a\oplus0=0\oplus a=a$
4. 反元素為自身：$a\oplus a=0$

#### 解法 1

可以注意到 xor 有結合律的特性，因此可以直接用線段樹維護，
建造 O($N\log N$)，單次查詢 $O(\log N)$，
總複雜度 $O((N+Q)\log N)$。

:::spoiler 參考程式

#include <iostream>
#include <vector>
#include <functional>

using namespace std;

template<typename value_t, class merge_t>
class SGT {
	int n;
	vector<value_t> t; // root starts at 1
	merge_t merge; // associative function for SGT
public:
	explicit SGT(int _n = 0, const merge_t& _merge = merge_t{})
		: n{_n}, t(2 * n), merge{_merge} {}
	void modify(int p, const value_t& x) {
		for (t[p += n] = x; p > 1; p >>= 1) t[p >> 1] = merge(t[p], t[p ^ 1]);
	}
	value_t query(int l, int r, value_t init) { // [l:r)
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (l & 1) init = merge(init, t[l++]);
			if (r & 1) init = merge(init, t[--r]);
		}
		return init;
	}
};

void solve() {
	int n, q;
	cin >> n >> q;
	vector<int> v(n);
	for (auto& x : v) cin >> x;

	SGT<int, bit_xor<int>> sgt{n};
	for (int i{0}; i < n; ++i) sgt.modify(i, v[i]);

	while (q--) {
		int l, r;
		cin >> l >> r, --l;
		cout << sgt.query(l, r, 0) << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t{1};
	//cin >> t;
	while (t--) solve();

	return 0;
}

:::

#### 解法 2

先思考區間合的問題，在解區間和問題時可以預處理前綴和，
在此假設預處理完的前綴和陣列名字叫做 $pre$
每次查詢 $[l,r]$ 的和時，只要輸出 $pre[r]-pre[l-1]$ 即可。
前綴和這個做法利用了上述四種特性。
而 xor 也有這種特性，因此可以預處理前綴 xor 的值，
每次查詢輸出 $pre[r]\oplus pre[l-1]$ 即可。
預處理 $O(N)$，單次查詢 $O(1)$，總複雜度 $O(N+Q)$

### 標準程式
:::spoiler

#include <iostream>
using namespace std;

int a[400001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, q, l, r;
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i] ^= a[i - 1];
	}
	while(q--){
		cin >> l >> r;
		cout << (a[r] ^ a[l - 1]) << "\n";
	}
}

:::

## [Range Max](https://judge.csie.ncku.edu.tw/problems/105)
- Task Provider: D4nnyLee
- Task Setter: D4nnyLee

### 首殺 team21_12 (00:28)

### 解法說明

定義一個新的長度為 $n - 1$ 的陣列 $b$，而 $b_i = |a_{i + 1} - a_i|$。

#### 解法 1

考慮以下兩個陣列：

1. $[b_1, -b_2, b_3, \dots, (-1)^{n - 2}b_{n - 1}]$
2. $[-b_1, b_2, -b_3, \dots, (-1)^{n - 1}b_{n - 1}]$

題目要求的答案其實就是上面兩個陣列的最大連續和的最大值。

第 $1$ 個陣列的最大連續和就是所有 $l$ 為奇數的 $[l, r]$ 代入 $f$ 後的最大值，
以此類推，第 $2$ 個陣列的最大連續和就是 $l$ 為偶數的最大值，因此兩個取最大值就是所有可能的 $[l, r]$ 的最大值。

#### 解法 2

定義 $dp_{i, 0}$ 是所有以 $i$ 為開頭的區間代入 $f$ 後可以得到的最小值，而 $dp_{i, 1}$ 就是最大值。

則我們可以得到以下關係式：

* $dp_{i, 0} = \min(b_i, b_i - dp_{i + 1, 1})$
* $dp_{i, 1} = \max(b_i, b_i - dp_{i + 1, 0})$

最後的答案就是 $\displaystyle \max_{1 \leq i \leq n - 1}\{dp_{i, 1}\}$。

### 標準程式

:::spoiler 解法 1

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

int main() {
	int n; cin >> n;
	vector<Int> A(n);
	for(auto &it: A) cin >> it;
	vector<Int> B(n-1);
	for(int i = 0; i < n-1; i++) B[i] = abs(A[i] - A[i+1]);
	for(int i = 0; i < n-1; i+=2) B[i] = -B[i];
	Int ans = 0, now = 0;
	for(int i = 0; i < n-1; i++)
		now = max(B[i], now+B[i]), ans = max(ans, now);
	for(int i = 0; i < n-1; i++) B[i] = -B[i];
	now = 0;
	for(int i = 0; i < n-1; i++)
		now = max(B[i], now+B[i]), ans = max(ans, now);
	cout << ans << endl;
	return 0;

}

:::

:::spoiler 解法 2

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

void test_case()
{
    int n;
    cin >> n;

    vector<int> a(n);
    for (auto &ai : a)
        cin >> ai;

    for (int i{1}; i < n; ++i)
        a[i - 1] = abs(a[i] - a[i - 1]);

    --n;
    a.pop_back();

    vector<pair<long long, long long>> dp(n);
    dp.back() = {a.back(), a.back()};

    long long ans{a.back()};
    for (int i{n - 2}; i >= 0; --i) {
        auto &[mx, mn]{dp[i]};
        auto [prev_mx, prev_mn]{dp[i + 1]};

        mx = mn = a[i];

        mx -= min(0LL, prev_mn);
        mn -= max(0LL, prev_mx);

        ans = max(ans, mx);
    }

    cout << ans << '\n';
}

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

    int Case = 1;
    // cin >> Case;
    for (int i = 1; i <= Case; i++) {
        // cout << "Case #" << i << ": ";
        test_case();
    }
    return 0;
}

:::

## [該睡覺了 晚安](https://judge.csie.ncku.edu.tw/problems/106)
- Task Provider: ys
- Task Setter: ys

### 首殺 team21_24 (01:21)

### 解法說明
將一段區間從行程表中移除，就只剩下**前綴**及**後綴**的行程表
正好，題目要求的就是前後綴相加期間變化的最高及最低值

對於區間 $[l, r]$ 算出 $l$ 以前的**前綴和極值**，以及 $r$ 之後的**後綴和極值**
接著處理這些極值就能得到題目所要求的答案

定義 $p(i)$ 為以 $i$ 結尾的前綴和，則 $p(i) = p(i-1) + A_i$ 且 $p(0) = 0$
- 定義 $p_{\min}(i)$ 為以 $i$ 結尾的**最小前綴和**
則 $p_{\min}(i) = \min\{p_{\min}(i-1), p(i)\}$ 且 $p_{\min}(0) = 0$
- 定義 $p_{\max}(i)$ 為以 $i$ 結尾的**最大前綴和**
則 $p_{\max}(i) = \max\{p_{\max}(i-1), p(i)\}$ 且 $p_{\max}(0) = 0$

後綴和極值也能以**動態規劃**的方式去思考：
- 定義 $s_{\min}(i)$ 為以 $i$ 開頭的**最小後綴和**
則 $s_{\min}(i) = \min\{A_i + s_{\min}(i+1), 0\}$ 且 $s_{\min}(n+1) = 0$

> 因為後綴和是以 $0$ 開始累加的，所以該**上界**為 $0$

- 定義 $s_{\max}(i)$ 為以 $i$ 開頭的**最大後綴和**
則 $s_{\max}(i) = \max\{A_i + s_{\max}(i+1), 0\}$ 且 $s_{\max}(n+1) = 0$

> 因為後綴和是以 $0$ 開始累加的，所以該**下界**為 $0$

### 標準程式
:::spoiler

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

int constexpr maxn = 5e5 + 10;

int n, m, A[maxn], l, r;

int main()
{
  ios_base::sync_with_stdio(false), cin.tie(NULL);

  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> A[i];

  vector<int> pr(n+1), pr_mi(n+1), pr_mx(n+1); // prefix minimum & maximum
  pr[0] = pr_mi[0] = pr_mx[0] = 0;
  for(int i = 1; i <= n; i++) {
    pr[i] = pr[i-1] + A[i];
    pr_mi[i] = min(pr_mi[i-1], pr[i]);
    pr_mx[i] = max(pr_mx[i-1], pr[i]);
  }

  vector<int> su_mi(n+2), su_mx(n+2); // surfix minimum & maximum
  su_mi[n+1] = su_mx[n+1] = 0;
  for(int i = n; i >= 1; i--) {
    su_mi[i] = min(0, A[i] + su_mi[i+1]);
    su_mx[i] = max(0, A[i] + su_mx[i+1]);
  }

  while(m--) {
    cin >> l >> r;
    cout << min(pr_mi[l-1], pr[l-1] + su_mi[r+1]) << ' ';
    cout << max(pr_mx[l-1], pr[l-1] + su_mx[r+1]) << '\n';
  }

  return 0;
}

:::

## [眼神殺 - 風起](https://judge.csie.ncku.edu.tw/problems/107)
- Task Provider: raiso
- Task Setter: raiso

### 首殺 team21_12 (02:00)

### 解法說明

首先考慮討論團彼此之間不會交錯，也就是最終的討論團順序屬於三個字串的共同子序列。
在上課的時候我們有學到如何解決兩個字串的共同子序列，這時候就可以參考他的 DP 轉移式的設計方式，相同時 $+1$，不同時找附近最大值繼承。
這題是 3 個字串的 LCS 題目，不過有卡記憶體用量，並不能開 $300^3$ 個狀態。需要壓縮到 $O(N^2)$ 的狀態數量才會過。
觀察可以發現固定第一行的某元素下去找同字母的 LCS 對於第一行而言，只會用到當前跟上一個的值，所以不用存整條的 DP 式，因此 $i \geq 2$ 的時候就可以把前面的 clear 掉

### 標準程式
:::spoiler

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

vector<vector<vector<int>>> dp;

int n;

int DP(int i, int j, int k) {
	if(i >= 0 && j >= 0 && k >= 0) return dp[i][j][k];
	else return 0;
}

int main() {
	cin >> n;
	string str[3];

	dp.resize(n);
	for(int i = 0; i < 3; i++) cin >> str[i];
	for(int i = 0; i < n; i++) {
		dp[i].assign(n, vector<int>(n, 0));
		if(i-2 >= 0) dp[i-2].clear();
		for(int j = 0; j < n; j++) for(int k = 0; k < n; k++) {
			if(str[0][i] == str[1][j] && str[0][i] == str[2][k] && str[0][i] != '?')
				dp[i][j][k] = DP(i-1, j-1, k-1)+1;
			else
				dp[i][j][k] = max({DP(i-1,j,k), DP(i,j-1,k), DP(i,j,k-1)});
		}
	}
	cout << dp[n-1][n-1][n-1] * 3 << endl;
	return 0;

}

:::

## [男廁的默契](https://judge.csie.ncku.edu.tw/problems/108)
- Task Provider: arashi87
- Task Setter: arashi87

### 首殺 team21_15 (01:31)

### 解法說明
我們可以根據題序很簡單的想到這是一題 dp，但是因為有單點修改以及變相區間求和所以需要加上線段樹。

我們可以在線段樹上每個節點都開一個 dp 數組，對於每個 root 節點維護一個 dp 數組，$dp[root][i][j]$，且 $i, j\in \{1, 0\}$，其代表意義為 root 節點的左節點選 (不選)，右節點選（不選），給定初值只要對於每個葉節點進行 $dp[root][1][1] = arr[idx]$ 就行。

因為相鄰兩個節點不能被同時選中，所以在進行 pushup 回溯時要注意不能出現像是 $dp[root<<1][0][1] + dp[root<<1|1][1][0]$ 這種，接下來我們就可以推出下面一個很長的轉移式。

$$
lc = root<<1, rc = (root<<1)|1
$$

$$
dp[rt][0][0]=max(dp[lc][0][0]+dp[rc][0][0], dp[lc][0][0]+dp[rc][1][0], dp[lc][0][1]+dp[rc][0][0])
$$

$$
dp[rt][0][1]=max(dp[lc][0][0]+dp[rc][0][1], dp[lc][0][1]+dp[rc][0][1], dp[lc][0][0]+dp[rc][1][1])
$$

$$
dp[rt][1][0]=max(dp[lc][1][0]+dp[rc][0][0], dp[lc][1][0]+dp[rc][1][0], dp[lc][1][1]+dp[rc][0][0])
$$

$$
dp[rt][1][1]=max(dp[lc][1][0]+dp[rc][0][1], dp[lc][1][1]+dp[rc][0][1],dp[lc][1][0]+dp[rc][1][1])
$$

其實這可以直接合併成下列轉移式。

$$
dp[rt][i][j]=max(dp[lc][i][0]+dp[rc][0][j], dp[lc][i][\{0, 1\}]+dp[rc][\{0, 1\}][j],dp[lc][i][\{0, 1\}]+dp[rc][\{0, 1\}][j])
$$

然後因為這長度有點令人崩潰，所以我將後面兩維壓成一維，然後將其視為二進位轉換成十進位。

最後我們只要取個根節點的 `std::max(std::max(seg[1][0], seg[1][1]), std::max(seg[1][2], seg[1][3]))` 就能得到答案了。

### 標準程式
:::spoiler

#include <algorithm>
#include <stdio.h>
#define int long long
#define lc (rt << 1)
#define rc (rt << 1 | 1)
const int maxN = 2e5 + 7;

int n, m, arr[maxN];
int seg[maxN << 2][5], ans = 0;

inline int max(int a, int b, int c)
{
    return std::max(a, std::max(b, c));
}

void pushup(int rt)
{
    seg[rt][0] = max(seg[lc][0] + seg[rc][0], seg[lc][1] + seg[rc][0], seg[lc][0] + seg[rc][2]);
    seg[rt][1] = max(seg[lc][0] + seg[rc][1], seg[lc][1] + seg[rc][1], seg[lc][0] + seg[rc][3]);
    seg[rt][2] = max(seg[lc][2] + seg[rc][0], seg[lc][2] + seg[rc][2], seg[lc][3] + seg[rc][0]);
    seg[rt][3] = max(seg[lc][2] + seg[rc][1], seg[lc][3] + seg[rc][1], seg[lc][2] + seg[rc][3]);
}

void build(int rt, int L, int R)
{
    if (L == R)
        seg[rt][3] = arr[L];
    else {
        int mid = (L + R) >> 1;
        build(rt << 1, L, mid);
        build(rt << 1 | 1, mid + 1, R);
        pushup(rt);
    }
}

void modify(int rt, int L, int R, int x, int d)
{
    if (L == R)
        seg[rt][3] = d;
    else {
        int mid = (L + R) >> 1;
        if (x <= mid)
            modify(rt << 1, L, mid, x, d);
        else
            modify(rt << 1 | 1, mid + 1, R, x, d);
        pushup(rt);
    }
}

signed main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", arr + i);
    build(1, 1, n);
    for (int i = 1, x, y; i <= m; i++) {
        scanf("%lld%lld", &x, &y);
        modify(1, 1, n, x, y);
        printf("%lld\n", std::max(std::max(seg[1][0], seg[1][1]), std::max(seg[1][2], seg[1][3])));
    }
}

:::