1968(div3)

A. Maximize?

给你一个整数 $x$ 。您的任务是找出任意一个整数 $y$ ，使得 $gcd (x, y) + y$ 为最大可能数。 $(1 \leq y < x)$ 使得 $gcd (x, y) + y$ 最大。

直接模拟即可。

void solve() {
    int n;cin >> n;
    int ans = -1, ret = -1;
    for (int i = 1;i < n;i++) {
        int x = __gcd(n, i) + i;
        if (x > ans) {
            ans = x;
            ret = i;
        }
    }
    cout << ret << '\n';
}

B. Prefiquence

给您两个二进制字符串 $a$ 和 $b$ 。

您的任务是确定最大可能的数字 $k$ ，使得长度为 $k$ 的字符串 $a$ 的前缀是字符串 $b$ 的子序列。

双指针

void solve() {
    int n, m;cin >> n >> m;string a, b;cin >> a >> b;
    int j = 0, cnt = 0;
    for (int i = 0;i < m;i++) {
        if (b[i] == a[j]) {
            cnt++;j++;
        }
    }
    cout << cnt << '\n';
}

C. Assembly via Remainders

给你一个数组 $x_{2}, x_{3}, \dots, x_{n}$ 。你的任务是找出任意一个数组 $a_{1}, \dots, a_{n}$ ，其中：

$1 \leq a_{i} \leq 10^{9}$ 代表所有的 $1 \leq i \leq n$ .
$x_{i} = a_{i} mod a_{i - 1}$ 代表所有的 $2 \leq i \leq n$ 。

构造

void solve() {
    int n;cin >> n;vector<int> x(n + 1), a(n + 1);
    for (int i = 2;i <= n;i++)cin >> x[i];
    a[1] = x[2] + 1;
    for (int i = 2;i <= n;i++) {
        a[i] = x[i];
        while (i != n && a[i] <= x[i + 1]) {
            a[i] += a[i - 1];
        }
    }
    for (int i = 1;i <= n;i++)cout << a[i] << " \n"[i == n];
}

D. Permutation Game

Bodya 和 Sasha 发现了一个排列 $p_{1}, \dots, p_{n}$ 和一个数组 $a_{1}, \dots, a_{n}$ 。他们决定玩一个著名的 "排列游戏"。

它们都选择了排列的起始位置。

对局持续了 $k$ 个回合。棋手同时下棋。在每个回合中，每个棋手都会发生两件事：

如果棋手当前的位置是 $x$ ，他的得分就会增加 $a_{x}$ 。
然后棋手要么停留在当前位置 $x$ ，要么从 $x$ 移动到 $p_{x}$ 。

在整整 $k$ 个回合后，得分较高的一方即为获胜者。

知道了博迪娅的起始位置 $P_{B}$ 和萨沙的起始位置 $P_{S}$ 后，如果双方都想获胜，那么谁会赢得对局？

Solution

分别单独计算 $B, S$ 得分最大值。计算最终落在能到达的每个位置的值，能够证明走过的点只走一次，最终的点走很多次

#define int long long
void solve() {
    int n, k, b, s;cin >> n >> k >> b >> s;vector<int> p(n + 1), a(n + 1);
    for (int i = 1;i <= n;i++)cin >> p[i];
    for (int i = 1;i <= n;i++)cin >> a[i];

    auto cal = [&](int x) {
        int r = 0, cur = 0;
        for (int i = 0;i < k && i <= n + 1;i++) {
            r = max(r, cur + (k - i) * a[x]);
            cur += a[x];
            x = p[x];
        }
        return r;
        };

    int x = cal(b);
    int y = cal(s);
    if (x == y) {
        cout << "Draw\n";
    } else if (x > y) {
        cout << "Bodya\n";
    } else {
        cout << "Sasha\n";
    }
}

E. Cells Arrangement

给你一个整数 $n$ 。您在网格 $n \times n$ 中选择 $n$ 单元格 $(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{n}, y_{n})$ ， $1 \leq x_{i}, y_{i} \leq n$

假设 $H$ 是任意一对单元格之间不同的曼哈顿距离集合。你的任务是最大化 $H$ 的大小。

Solution

构造

当 $n \geq 4$ 时， $H$ 就是 $[0, 2 n - 2]$ 的集合。

void solve() {
    int n;cin >> n;
    if (n == 2) {
        cout << "1 1\n1 2\n";return;
    }
    if (n == 3) {
        cout << "2 1\n2 3\n 3 1\n";return;
    }
    cout << "1 1\n1 2\n4 2\n4 4\n";
    for (int i = 5;i <= n;i++)cout << i << ' ' << i << '\n';
}

这里当 $n = 4$ 时， $H_{1} = 0, 1, 2, 3, 4, 5, 6 = [0, 6]$ ,刚好满足条件
当 $n \geq 5$ 时， $n$ 每递增一次， $H$ 最大值只会增加 2

每次在对角线上添加一个时，每个数字都可以增加 2，即 $H_{2} = (H_{1} + 2) + H_{1} = [0, 2 n - 2]$

F. Equal XOR Segments

如果可以将一个数组分成个数组，我们就称它为 $x_{1}, \dots, x_{m}$ 个有趣的数组。

k>1 个部分，使得每个部分的值的 bitwise XOR 都相等，那么这个数组就是有趣的数组。

更正式地说，你必须把数组 $x$ 分成 $k$ 个连续的部分， $x$ 中的每个元素都必须完全属于*** $1$ 个部分。设 $y_{1}, \dots, y_{k}$ 分别是各部分元素的 XOR。那么 $y_{1} = y_{2} = \dots = y_{k}$ 必须满足。

例如，如果是 $x = [1, 1, 2, 3, 0]$ ，可以将其拆分如下： $[1], [1], [2, 3, 0]$ .事实上是 $1 = 1 = 2 \oplus 3 \oplus 0$ 。

给你一个数组 $a_{1}, \dots, a_{n}$ 。你的任务是回答 $q$ 个查询：

对于固定的 $l$ ， $r$ ，判断子数组 $a_{l}, a_{l + 1}, \dots, a_{r}$ 是否有趣。

Solution

位运算

有 $\oplus$ 的性质：若有奇数个区间异或和相等，那么这所有的异或和与之前分别的异或和值相等。

在本题中，若有三个以上的区间异或和是相等的，则这三个区间可以合并成一个区间，且异或和与之前一样。

由于本题要求 $k > 1$ ，则本题 $k$ 的范围只有 $k = 2 or k = 3$ 。若 $k > 3$ ，则一定可以通过上面的方法使得 $k \leq 3$

$s_{i}$ 代表前缀异或和

当 $k = 2$ 时，则可以将该区间分为异或和相等的两部分 $[l, m], [m + 1, r]$ ,则 $s_{m} \oplus s_{l - 1} = s_{m + 1} \oplus s_{r} ⟹ s_{l - 1} = s_{r}$

当 $k = 3$ 时，则将区间分为 $[l, t], [t + 1, m], [m + 1, r]$ ,则 $s_{t} \oplus s_{l - 1} = s_{m} \oplus s_{t} and s_{m} \oplus s_{t} = s_{r} \oplus s_{m}$

$⟹$ $s_{m} = s_{l - 1} and s_{r} = s_{t}$ $(t < m)$

要使得满足这个条件，就得让得到的 $t$ 尽可能小， $m$ 尽可能大，在值相等的前提下，让 $t$ 为 $\geq l$ 的最小下标， $m$ 为 $< r$ 的最大下标

这里我记反了，lower_bound 是第一个大于等于的元素，uppper_bound 是第一个大于的元素

void solve() {
    int n, q;cin >> n >> q;vector<int> a(n + 1), s(n + 1);
    map<int, vector<int>>mp;
    mp[0].push_back(0);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];s[i] = s[i - 1] ^ a[i];
        mp[s[i]].push_back(i);
    }

    while (q--) {
        int l, r;cin >> l >> r;
        if (s[r] == s[l - 1]) {
            cout << "Yes\n";
        } else {
            auto t = *lower_bound(mp[s[r]].begin(), mp[s[r]].end(), l);
            auto m = *--lower_bound(mp[s[l - 1]].begin(), mp[s[l - 1]].end(), r);
            if (t < m) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
        }
    }
    cout << '\n';
}

G. Division + LCP

给你一个字符串 $s$ 。对于固定的 $k$ ，考虑将 $s$ 恰好分成 $k$ 个连续的子串 $w_{1}, \dots, w_{k}$ 。设 $f_{k}$ 是所有分割中最大可能的 $L C P (w_{1}, \dots, w_{k})$ 。

$L C P (w_{1}, \dots, w_{m})$ 是字符串 $w_{1}, \dots, w_{m}$ 的最长公共前缀的长度。

例如，如果 $s = a b a b a b c a b$ 和 $k = 4$ ，可能的除法是 $a b a b a b c a b$ 。由于 $a b$ 是这四个字符串的最长公共前缀，所以 $L C P (a b, a b, a b c, a b)$ 就是 $2$ 。请注意，每个子串都由一段连续的字符组成，每个字符都属于**个子串。

您的任务是找出 $f_{l}, f_{l + 1}, \dots, f_{r}$ 。

easy： $l = r$
hard： $l \leq r$

Solution

Z 算法(扩展 KMP 算法)+二分/字符串算法/LCP

字符串算法我觉得可以放一下

(待更 $\dots$ )