2021 高階競程 Contest #4 - 題解

區間 xor

Task Provider: leo
Task Setter: leo

首殺 team21_25 (00:02)

解法說明

整數的 xor 運算符合以下條件，下方以「

\oplus

」當作 xor 運算符：

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

解法 1

可以注意到 xor 有結合律的特性，因此可以直接用線段樹維護，
建造 O(

N \log N

)，單次查詢

O (\log N)

，
總複雜度

O ((N + Q) \log N)

。

參考程式

#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

先思考區間合的問題，在解區間和問題時可以預處理前綴和，
在此假設預處理完的前綴和陣列名字叫做

p r e

每次查詢

[l, r]

的和時，只要輸出

p r e [r] - p r e [l - 1]

即可。
前綴和這個做法利用了上述四種特性。
而 xor 也有這種特性，因此可以預處理前綴 xor 的值，
每次查詢輸出

p r e [r] \oplus p r e [l - 1]

即可。
預處理

O (N)

，單次查詢

O (1)

，總複雜度

O (N + Q)

標準程式

#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

Task Provider: D4nnyLee
Task Setter: D4nnyLee

首殺 team21_12 (00:28)

解法說明

定義一個新的長度為

n - 1

的陣列

b

，而

b_{i} = | a_{i + 1} - a_{i} |

。

解法 1

考慮以下兩個陣列：

$[b_{1}, - b_{2}, b_{3}, \dots, (- 1)^{n - 2} b_{n - 1}]$
$[- b_{1}, b_{2}, - b_{3}, \dots, (- 1)^{n - 1} b_{n - 1}]$

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

第

1

個陣列的最大連續和就是所有

l

為奇數的

[l, r]

代入

f

後的最大值，
以此類推，第

2

個陣列的最大連續和就是

l

為偶數的最大值，因此兩個取最大值就是所有可能的

[l, r]

的最大值。

解法 2

定義

d p_{i, 0}

是所有以

i

為開頭的區間代入

f

後可以得到的最小值，而

d p_{i, 1}

就是最大值。

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

$d p_{i, 0} = min (b_{i}, b_{i} - d p_{i + 1, 1})$
$d p_{i, 1} = max (b_{i}, b_{i} - d p_{i + 1, 0})$

最後的答案就是

max_{1 \leq i \leq n - 1} {d p_{i, 1}}

。

標準程式

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

}

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

該睡覺了晚安

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$

標準程式

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

眼神殺 - 風起

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 掉

標準程式

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

}

男廁的默契

Task Provider: arashi87
Task Setter: arashi87

首殺 team21_15 (01:31)

解法說明

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

我們可以在線段樹上每個節點都開一個 dp 數組，對於每個 root 節點維護一個 dp 數組，

d p [r o o t] [i] [j]

，且

i, j \in {1, 0}

，其代表意義為 root 節點的左節點選 (不選)，右節點選（不選），給定初值只要對於每個葉節點進行

d p [r o o t] [1] [1] = a r r [i d x]

就行。

因為相鄰兩個節點不能被同時選中，所以在進行 pushup 回溯時要注意不能出現像是

d p [r o o t << 1] [0] [1] + d p [r o o t << 1 | 1] [1] [0]

這種，接下來我們就可以推出下面一個很長的轉移式。

l c = r o o t << 1, r c = (r o o t << 1) | 1

d p [r t] [0] [0] = m a x (d p [l c] [0] [0] + d p [r c] [0] [0], d p [l c] [0] [0] + d p [r c] [1] [0], d p [l c] [0] [1] + d p [r c] [0] [0])

d p [r t] [0] [1] = m a x (d p [l c] [0] [0] + d p [r c] [0] [1], d p [l c] [0] [1] + d p [r c] [0] [1], d p [l c] [0] [0] + d p [r c] [1] [1])

d p [r t] [1] [0] = m a x (d p [l c] [1] [0] + d p [r c] [0] [0], d p [l c] [1] [0] + d p [r c] [1] [0], d p [l c] [1] [1] + d p [r c] [0] [0])

d p [r t] [1] [1] = m a x (d p [l c] [1] [0] + d p [r c] [0] [1], d p [l c] [1] [1] + d p [r c] [0] [1], d p [l c] [1] [0] + d p [r c] [1] [1])

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

d p [r t] [i] [j] = m a x (d p [l c] [i] [0] + d p [r c] [0] [j], d p [l c] [i] [{0, 1}] + d p [r c] [{0, 1}] [j], d p [l c] [i] [{0, 1}] + d p [r c] [{0, 1}] [j])

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

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 →

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

標準程式

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

2021 高階競程 Contest #4 - 題解

區間 xor

首殺 team21_25 (00:02)

解法說明

解法 1

解法 2

標準程式

Range Max

首殺 team21_12 (00:28)

解法說明

解法 1

解法 2

標準程式

該睡覺了 晚安

首殺 team21_24 (01:21)

解法說明

標準程式

眼神殺 - 風起

首殺 team21_12 (02:00)

解法說明

標準程式

男廁的默契

首殺 team21_15 (01:31)

解法說明

標準程式

Read more

2020 Week 7: Dynamic Programming

2020 Week 1: Introduction

2020 Week 4: Search

2020 Week 14: Number theory

該睡覺了晚安