Codeforces Round 1028 Div.1ABD / Div.2CDF

2115A / 2116C - Gellyfish and Flaming Peony

先做出一个 GCD，再将其它数变成 GCD。

看到 5000 考虑$\mathcal O(n^{2})$ 的 DP。设$f_{i,x}$ 表示前$i$ 个数中至少需要选出几个数才能组合出 GCD 等于$x$。复杂度$\mathcal O(nV\log V)$，$V=5000$，能过。

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

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ulll = unsigned __int128;

constexpr ll inf = 0x3f3f3f3f3f3f3f3f;

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

    vector<int> a(n);
    int d = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i]; 
        d = gcd(d, a[i]); 
    }

    int cnt = 0;
    int has_one = 0;
    for (int i = 0; i < n; i++) {
        cnt += a[i] != d;
        if (a[i] == d) has_one = 1;
    }

    const int N = 5001;
    vector<int> f(N, inf);
    for (int i = 0; i < n; i++) {
        auto nf = f;
        nf[a[i]] = 0;
        for (int j = 1; j < N; j++) {
            nf[gcd(j, a[i])] = min(nf[gcd(j, a[i])], f[j] + 1);
        } 
        f = nf;
    }
    cout << (f[d] + cnt - 1 + has_one) << endl;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    for (int t = (cin >> t, t); t--; )
        solve();

    return 0;
}

2115B / 2116D - Gellyfish and Camellia Japonica

大概想法是先找出必要条件，再验证充分性。

倒着求出每个数的下界（$a_{x} \geqslant a_z,\ a_{y} \geqslant a_{z}$），取$a$ 为这个下界，再验证构造出的这个$a$ 是否合法。复杂度$\mathcal O(n+q)$。

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

void solve() {
    int n, q;
    cin >> n >> q;

    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    vector<array<int, 3>> que(q);
    for (auto& [x, y, z] : que) {
        cin >> x >> y >> z;
        x--, y--, z--;
    }
    reverse(que.begin(), que.end());

    auto a = b;
    for (auto& [x, y, z] : que) {
        a[y] = max(a[y], a[z]);
        a[x] = max(a[x], a[z]);
        if (z != x && z != y) {   // 特别注意这个判断 
            a[z] = 0;
        }
    }

    reverse(que.begin(), que.end());
    auto c = a;
    for (auto& [x, y, z] : que) {
        c[z] = min(c[x], c[y]);
    }

    if (b != c) {
        cout << -1 << endl;
        return;
    }

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    for (int t = (cin >> t, t); t--; )
        solve();

    return 0;
}

2115D / 2116F - Gellyfish and Forget-Me-Not - UPSOLVE

这题方法应该不少，写一个相对好理解的。

先置$a_{i}:=a_{i}\oplus b_{i},\mathrm{res}:=\mathrm {res}\oplus b_{i}$，这样相当于每个人可以选择要不要$a_{i}$。

考虑$a$ 只有 01 怎么做：最后一个拿到$a =1$ 的人有决定权，可以改成他想要的数。因此检查最后一个$a =1$ 的位置，如果是$c=1$，那么答案为 1，否则答案为 0。

如果有多位，就要知道每一个二进制位的决定权在谁手上。倒序遍历（因为要找最后一个位置）$a$ 并插入线性基，设将$a_{i}$ 插入线性基后的最高位为$2^{d}$，那么$d$ 的决定权就在$c_{i}$ 手上。

现在，从高到低遍历每个二进制位，这一位$d$ 的决定权在谁手上，这个人就能把这一位变成他想要的数（$c=1$ 则变成 1，否则变成 0）。

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

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ulll = unsigned __int128;

constexpr int B = 60;

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

    vector<ull> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ull res = 0;
    for (int i = 0; i < n; i++) {
        ull x;
        cin >> x;
        a[i] ^= x;
        res ^= x;
    }
    string c;
    cin >> c;

    array<ull, B> h{};   // 线性基 
    array<bool, B> op{};
    for (int i = n - 1; i >= 0; i--) {
        auto& x = a[i];
        for (int bit = B - 1; bit >= 0; bit--) {
            if (x >> bit & 1) {
                if (!h[bit]) {
                    op[bit] = c[i] - '0';
                    h[bit] = x;
                    break;
                } else {
                    x ^= h[bit];
                }
            }
        }
    }
    for (int bit = B - 1; bit >= 0; bit--) {
        if (op[bit] ^ (res >> bit & 1)) {
            res ^= h[bit];
        }
    }
    cout << res << endl;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    for (int t = (cin >> t, t); t--; )
        solve();

    return 0;
}