---
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 參考程式
```cpp
#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
```cpp
#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
```cpp
#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
```cpp
#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
```cpp
#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
```cpp
#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
```cpp
#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])));
}
}
```
:::
Sign in with Wallet
Connect another wallet