比赛链接

A

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; bool solve() {    int n, m, k;    cin >> n >> m >> k;    int x, y;    cin >> x >> y;    bool ok = 1;    for (int i = 1;i <= k;i++) {        int xx, yy;        cin >> xx >> yy;        ok &= abs(x - xx) + abs(y - yy) & 1;    }    if (ok) cout << "YES" << '\n';    else cout << "NO" << '\n';    return true;} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t = 1;    cin >> t;    while (t--) {        if (!solve()) cout << -1 << '\n';    }    return 0;}

B

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; vector<int> c[200007];bool solve() {    int n, k;    cin >> n >> k;    for (int i = 1;i <= k;i++) c[i].clear();    for (int i = 1;i <= k;i++) c[i].push_back(0);    for (int i = 1;i <= n;i++) {        int x;        cin >> x;        c[x].push_back(i);    }    for (int i = 1;i <= k;i++) c[i].push_back(n + 1);     int ans = n;    for (int i = 1;i <= k;i++) {        priority_queue<int> pq;        for (int j = 1;j < c[i].size();j++) pq.push(c[i][j] - c[i][j - 1] - 1);        int mx = pq.top();        if (mx) {            pq.pop();            pq.push((mx - 1) / 2);            pq.push(mx / 2);        }        ans = min(ans, pq.top());    }    cout << ans << '\n';    return true;} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t = 1;    cin >> t;    while (t--) {        if (!solve()) cout << -1 << '\n';    }    return 0;}

C

题意

给定长为 $n$ 的数组 $a,b$ ，每次操作使得 $a_i,b_i = b_i,|a_i-b_i|(1\leq i \leq n)$ 。

问是否可以通过若干次操作使得 $a_i = 0(1 \leq i \leq n)$ 。

题目

知识点：数论。

注意到，操作到最后一定能使得 $a_i = 0$ ，并进入周期为 $3$ 的循环，那么只要每个位置的数字进入循环的操作次数模 $3$ 同余即可。

模拟操作显然是不行的。注意到 $a_i \geq 2b_i$ 时，有 $(a_i,b_i) \to (b_i,a_i-b_i) \to (a_i-b_i,a_i-2b_i) \to (a_i-2b_i,b_i)$ 。因此，可以直接 $a_i \bmod 2b_i$ ，这样不影响操作次数模 $3$ 的结果。随后，执行操作一次继续上述操作。

时间复杂度 $O(n \log 10^9)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; int a[100007], b[100007];bool solve() {    int n;    cin >> n;    for (int i = 1;i <= n;i++) cin >> a[i];    for (int i = 1;i <= n;i++) cin >> b[i];     int ok = -1;    for (int i = 1;i <= n;i++) {        if (a[i] == 0 && b[i] == 0) continue;        int tmp = 0;        while (a[i]) {            if (b[i]) a[i] %= 2 * b[i];            swap(a[i], b[i]);            b[i] = abs(a[i] - b[i]);            (++tmp) %= 3;        }        if (ok == -1) ok = tmp;        else if (ok != tmp) return false;    }    cout << "YES" << '\n';    return true;} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t = 1;    cin >> t;    while (t--) {        if (!solve()) cout << "NO" << '\n';    }    return 0;}

D

题意

初始时有奖金 $s$ ，接下来可以执行 $k$ 次操作，每次操作以下的一种：

1. 奖金 $s$ 加上 $s$ 的个位数字。
2. 使用奖金 $s$ ，不会使得奖金减少，使用的奖金会累加。

问最多能使用多少奖金。

题目

知识点：数学，三分。

显然要尽可能将 $s$ 变大，再开始使用。

模拟操作1显然复杂度不行，考虑找到 $s$ 增加的循环节。

我们发现 $s \bmod 10 = 0 \text{ 或 } 5$ 时，至多操作 $1$ 次就不需要继续操作了。因此，考虑取不操作的答案和操作 $1$ 次的答案的最大值即可。

对于其他情况，至多操作 $1$ 次就会进入 $6,2,4,8$ 的循环，因此同样也记录不操作的答案和操作 $1$ 次的答案的最大值，之后可以利用循环快速计算答案。

对于一开始的贪心结论，我们很容易想到凸函数三分求极值，但样例提示这不是一个凸函数。注意到，循环节长度只有 $4$ ，若我们枚举终点在循环节中的位置，那么剩下的就是以常数 $20$ 增加，这显然是个凸函数，可以用三分。

进一步地，最后那个凸函数是个二次函数，也可以直接求抛物线对称轴得到最值。

时间复杂度 $O(\log k)$

空间复杂度 $O(1)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; bool solve() {    ll s, k;    cin >> s >> k;    ll ans = s * k;    s += s % 10;    k--;    ans = max(ans, s * k);    if (s % 10 == 0) {        cout << ans << '\n';        return true;    }     auto check = [&](ll x) {        return (s + x * 20) * (k - x * 4);    };    for (int i = 0;i < 4 && k;i++, s += s % 10, k--) {        ll l = 0, r = k / 4;        while (l <= r) {            ll mid1 = l + (r - l) / 3;            ll mid2 = r - (r - l) / 3;            if (check(mid1) <= check(mid2)) l = mid1 + 1;            else r = mid2 - 1;        }        ans = max(ans, check(r));    }    cout << ans << '\n';    return true;} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t = 1;    cin >> t;    while (t--) {        if (!solve()) cout << -1 << '\n';    }    return 0;}