练习赛 Round 150 题解

由于牛客的渲染问题，你可以点此链接进入我的博客查看

A 奇偶争锋

模拟即可，用优先队列维护一下两队的石头。

void solve() {
    int n;
    cin >> n;
    priority_queue<int> a, b;
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        if (x & 1)
            a.push(x);
        else
            b.push(x);
    }
    ll A = a.empty() ? 0 : a.top(), B = b.empty() ? 0 : b.top();
    vector<ll> ans(1, max(A, B));
    for (int i = 0; i < n - 1; ++i) {
        if (a.size())
            B += a.top(), a.pop();
        else
            B = 0;
        if (b.size())
            A += b.top(), b.pop();
        else
            A = 0;
        ans.pb(max(A, B));
    }
    for (auto v : ans) cout << v << " ";
    cout << endl;
}

B 数论迷城

如果有任意一个区间大小 ，必然能够选出 ，使得最大公因数为 。

如果所有区间大小均为 ，直接计算所有数字的最大公因数即可。

void solve() {
    int n;
    cin >> n;
    ll g = 0;
    bool f = 1;
    for (int i = 0; i < n; ++i) {
        ll l, r;
        cin >> l >> r;
        if (l == r) {
            g = gcd(g, l);
        } else {
            f = 0;
        }
    }
    if (f)
        cout << g << endl;
    else
        cout << 1 << endl;
}

C 乘鲨破浪

先让几个会开船的把所有人都送过去 ，然后再找一组不冲突的船长把其他所有船长保过去 。

：会开船的人为 ，他对应的不会开船的人为 。 两个人先过去，再 船长自己回来，这样就可以把不会开船的人送过去。

：设不冲突的一组船长为 。 两个人先过去， 把船开回来，再任意一个船长 过去， 再把船开回来，这样就可以把任意一个船长送过去，且船仍停留在 岸。

void solve() {
    int n, m, k, cnt = 0;
    cin >> n >> m >> k;
    vector<int> a(n + 1), b(m + 1);
    vector<bool> vis(n + 1);
    unordered_map<int, vector<int>> pr;
    auto check = [&](int a, int b) { return a % b == k || b % a == k; };
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) cin >> b[i], vis[b[i]] = 1, cnt++;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (!vis[i] && !check(a[i], a[b[j]])) {
                pr[b[j]].pb(i), cnt++;
                break;
            }
        }
    }

    if (cnt != n) {
        cout << "NO" << endl;
        return;
    }

    vector<PII> ans;
    for (int i = 1; i <= m; ++i) {
        for (auto v : pr[b[i]]) {
            ans.pb({b[i], v});
            ans.pb({b[i], b[i]});
        }
    }

    if (m == 1) {
        ans.pb({b[1], b[1]});
    } else {
        int X, Y;
        bool f = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = i + 1; j <= m; ++j) {
                if (!check(a[b[i]], a[b[j]])) {
                    X = b[i], Y = b[j], f = 1;
                    break;
                }
            }
            if (f) break;
        }
        if (!f) {
            cout << "NO" << endl;
            return;
        }
        for (int i = 1; i <= m; ++i) {
            if (b[i] == X || b[i] == Y) continue;
            ans.pb({X, Y});
            ans.pb({X, X});
            ans.pb({b[i], b[i]});
            ans.pb({Y, Y});
        }
        ans.pb({X, Y});
    }

    cout << "YES" << endl;
    cout << ans.size() << endl;
    for (auto [u, v] : ans) {
        cout << u << " " << v << endl;
    }
}

D 异或疑惑

让 和 同时异或上 ，我们可以把它看成，在 和 之间连了一条权值为 的边，最终这 个顶点会被划分为若干个连通块。那么操作数就等于 。

那为什么要按连通块思考？因为在连通块内，异或和是一定的。设某个连通块初始的异或和为 ，最终的和为 ，就有：

也就是说， ， 是某个非负整数。

那么既然只要在连通块内，异或和就守恒，那我们是不是能变出任意合法的加法和呢？

• 连通块大小为 ，操作不了。
• 联通块大小为 ，只有两个数字 和 ，有 ，所以有 。
• 连通块大小为 ，可以操作出任意和。

所以我们直接用 检查划分方式，如果有大小为 的集合，就能操作出任意数字，直接通过。否则使用数位 检查即可。

void solve() {
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> a(n);
    ll tot = 0;
    for (int i = 0; i < n; i++) cin >> a[i], tot ^= a[i];

    if ((k & 1) != (tot & 1)) {
        cout << -1 << endl;
        return;
    }

    int ans = 100;
    vector<ll> X;
    vector<int> sz;

    function<void(int, ll, int)> dfs = [&](int u, ll sum, int f) {
        int m = X.size();
        if (n - m >= ans) return;

        if (u == n) {
            if (sum <= k) {
                ll E = (k - sum) / 2;
                bool ok = f;

                if (!ok) {
                    vector<ll> P;
                    for (int i = 0; i < m; i++)
                        if (sz[i] == 2) P.pb(X[i]);
                    int dp = 1;
                    for (int b = 0; b < 62; b++) {
                        int cb = 0, nxt = 0, e = (E >> b) & 1;
                        for (auto x : P)
                            if (!((x >> b) & 1)) cb++;
                        for (int c = 0; c < 6; c++) {
                            if ((dp >> c) & 1) {
                                for (int v = 0; v <= cb; v++) {
                                    if (((c + v) & 1) == e) nxt |= 1 << ((c + v) >> 1);
                                }
                            }
                        }
                        if (!(dp = nxt)) break;
                    }
                    ok = dp & 1;
                }
                if (ok) ans = min(ans, n - m);
            }
            return;
        }

        X.pb(a[u]);
        sz.pb(1);
        dfs(u + 1, sum + a[u], f);
        sz.pob();
        X.pob();

        for (int i = 0; i < m; i++) {
            ll old = X[i];
            X[i] ^= a[u];
            sz[i]++;
            dfs(u + 1, sum - old + X[i], f + (sz[i] == 3));
            sz[i]--;
            X[i] = old;
        }
    };

    dfs(0, 0, 0);
    cout << (ans == 100 ? -1 : ans) << endl;
}

E 似数佳对

题目要求我们对每个 ，找到一个最大的 ，使得存在一个 满足“好的下标对”条件，即 。如果找不到这样的 ，则 。

在计算 时，我们需要考察所有已经处理过的下标 。对每一个这样的 ，我们需要判断它是否满足条件。

我们定义 。那么在计算 时，我们要找的就是满足 的所有 中，对应的 的最大值。对于任意一个固定的 ，有：

利用 ​ ，我们可以得到：

根据上面的递推关系，在计算 时，我们需要对所有 完成以下操作：

• 全体更新：对于每个 ，都将其关联的检查值 更新为 。
• 查询：在所有更新后的值中，找到满足 的那些 ，并求出它们对应的 的最大值。
• 插入：处理完 之后，需要将下标 的信息 加入数据集合，以备后续的计算。

所以我们使用以 为键值的 来维护。

为了执行更新操作 ，我们不仅需要存储当前的 值，还需要存储原始的 值。因此， 的每个节点需要维护以下信息：

• : 存储 的值。
• : 存储 的值。

如果多个 拥有相同的 ，它们会对应到 中的同一个键。对于查询 来说，只要这些 中有一个满足条件即可。因此，对于一个键 ，我们只需要关心所有 的下标中，那个拥有最小 值的 。所以，节点中存储的应该是：

• : 对于键为 的节点，存储 。
• : 对于键为 的节点，存储 。

为了支持子树查询，每个内部节点还需要维护其子树中 和 的最小值，记为 和 。

• : 子树中所有 的最小值。
• : 子树中所有 的最小值。

我们的全体更新操作是 。这可以被一个懒标记实现。懒标记 存一个值 ，表示要对子树中所有节点的 执行 的操作。当标记下传时，子节点的 和 都会相应更新。 在第 步 ：

1. 更新: 在 的根节点打上一个值为 的懒标记。这个标记的含义是，对于树中所有节点，执行 。通过懒标记的机制，这个更新会被高效地应用到全树。此时，所有节点的 值就从 更新成了 。
2. 查询: 我们需要在 中查找满足 的最大键值 。这可以在平衡树上高效地完成：从根节点开始，优先向右子树搜索。如果右子树的 ，则答案一定在右子树中；否则，检查当前节点是否满足 ；如果还不满足，再向左子树搜索。这个过程可以找到最大的满足条件的 值。这个值就是 。
3. 插入: 将当前下标 的信息插入 。创建一个键为 的新节点。其初始值为 (因为对于下标 自身而言， ）。如果树中已经存在键为 的节点，则更新该节点的 和 为原有值与新值之间的较小者。

constexpr ll INF = 2e18;

mt19937 rng((unsigned)std::chrono::steady_clock::now().time_since_epoch().count());

template <class Int>
struct Tag {
    static constexpr Int INF = numeric_limits<Int>::max();
    Int v = numeric_limits<Int>::max();
    void operator+=(const Tag<Int> &o) { v = min(v, o.v); }
    bool check() const { return v != INF; }
};

template <class Int>
struct Info {
    static constexpr Int INF = numeric_limits<Int>::max();
    Int sa = INF, sb = INF, ma = INF, mb = INF;
    Info() = default;

    static Info make_leaf(Int a, Int b) {
        Info t;
        t.sa = a;
        t.sb = a + b;
        t.ma = t.sa;
        t.mb = t.sb;
        return t;
    }

    void operator+=(const Tag<Int> &tg) {
        if (!tg.check()) return;
        sb = min(sb, sa + tg.v);
        mb = min(mb, ma + tg.v);
    }

    Info operator+(const Info<Int> &o) const {
        Info res;
        res.ma = min(ma, o.ma);
        res.mb = min(mb, o.mb);
        res.sa = INF;
        res.sb = INF;
        return res;
    }

    bool check() const { return sa != INF; }
};

template <class Int>
class Treap {
   private:
    static constexpr Int INF = numeric_limits<Int>::max();
    struct Node {
        int key;
        ui pr;
        Node *L = nullptr, *R = nullptr;
        Info<Int> info;
        Tag<Int> tag;
        Node(int k, ui p, Info<Int> inf) : key(k), pr(p), info(inf), tag() {}
    };

    Node *root = nullptr;

    void push(Node *t) {
        if (!t) return;
        if (!t->tag.check()) return;
        t->info += t->tag;
        if (t->L) {
            t->L->info += t->tag;
            t->L->tag += t->tag;
        }
        if (t->R) {
            t->R->info += t->tag;
            t->R->tag += t->tag;
        }
        t->tag = Tag<Int>();
    }

    void pull(Node *t) {
        if (!t) return;
        ll ma = INF, mb = INF;
        if (t->info.sa != INF) ma = t->info.sa;
        if (t->info.sb != INF) mb = t->info.sb;
        if (t->L) {
            ma = min(ma, t->L->info.ma);
            mb = min(mb, t->L->info.mb);
        }
        if (t->R) {
            ma = min(ma, t->R->info.ma);
            mb = min(mb, t->R->info.mb);
        }
        t->info.ma = ma;
        t->info.mb = mb;
    }

    void split(Node *t, int key, Node *&a, Node *&b) {
        if (!t) {
            a = b = nullptr;
            return;
        }
        push(t);
        if (t->key <= key) {
            a = t;
            split(t->R, key, a->R, b);
            pull(a);
        } else {
            b = t;
            split(t->L, key, a, b->L);
            pull(b);
        }
    }

    Node *merge(Node *a, Node *b) {
        if (!a || !b) return a ? a : b;
        if (a->pr < b->pr) {
            push(a);
            a->R = merge(a->R, b);
            pull(a);
            return a;
        } else {
            push(b);
            b->L = merge(a, b->L);
            pull(b);
            return b;
        }
    }

    int ask(Node *t, ll c) {
        if (!t || t->info.mb > c) return 0;
        push(t);
        if (t->R && t->R->info.mb <= c) return ask(t->R, c);
        if (t->info.sb <= c) return t->key;
        return ask(t->L, c);
    }

   public:
    Treap() : root(nullptr) {}

    void apply(const Tag<Int> &tg) {
        if (!root) {
            return;
        }
        root->info += tg;
        root->tag += tg;
    }
    void insert(int d, ll a, ll b) {
        Node *x, *y, *z;
        split(root, d, x, z);
        split(x, d - 1, x, y);
        if (!y) {
            ui pr = (ui)rng();
            Info<Int> base = Info<Int>::make_leaf(a, b);
            y = new Node(d, pr, base);
        } else {
            push(y);
            y->info.sa = min(y->info.sa, a);
            y->info.sb = min(y->info.sb, a + b);
        }
        root = merge(merge(x, y), z);
    }

    int ask(ll c) { return ask(root, c); }
};

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

    Treap<ll> tr;
    int pa = 0;
    for (int k = 1; k <= n; ++k) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a ^= pa, b ^= pa, c ^= pa, d ^= pa;

        tr.apply({b});
        pa = tr.ask(c);
        tr.insert(d, a, b);
        cout << pa << " ";
    }
    cout << endl;
}

F 集逆态没

“好”的集合 定义为：集合中每个元素 ，并且所有元素的按位或包含于 。这意味着 中所有的元素都是 的子集。 是集合 中所有元素的按位与，设 。对于合法的 ，必定满足：

• 。
• 。
• 集合 不能是空集，并且其按位与的值必须恰好等于 。

要使得按位与的结果恰好是 ，对于 中的每一个比特位 （即 且 ），必须在 中至少存在一个元素 满足 。换句话说，将

强制在第 位赋 0 得到的集合也必须与 有交集。

对于给定的 和约束上限，由于 ，寻找最大合法元素相当于寻找在某一比特位 首次脱离 （即 但 ）的情况下可构造的最大值。我们将这些分歧点 的最大生成值预处理出来称为 ，并计算出每个符合条件的 能掩盖到哪些比特位 。

用数位 进行维护即可。

ll memo[62][2][2][62][2];

void solve() {
    ll n, k, l, r;
    cin >> n >> k >> l >> r;

    bool f = 0;
    vector<bool> flag(62), lw(62);
    vector<int> mb(62, -1);

    int bad = -1;
    for (int j = 60; j >= 0; --j) {
        if (((r >> j) & 1) > ((k >> j) & 1)) {
            bad = j;
            break;
        }
    }

    for (int d = 60; d >= max(-1, bad); --d) {
        if (d == -1 || ((r >> d) & 1)) {
            ll v = (d == -1) ? r : (((r >> (d + 1)) << (d + 1)) | (d > 0 ? (k & ((1ll << d) - 1)) : 0));
            if (v >= (ll)l) {
                if (d == -1)
                    f = 1;
                else {
                    flag[d] = 1;
                    for (int x = d - 1; x >= 0; --x) {
                        if ((1ll << x) <= v - l) {
                            mb[d] = x;
                            break;
                        }
                    }
                }
            }
        }
    }

    for (int b = 0; b <= 60; ++b) {
        lw[b] = f;
        for (int j = 0; j < b; ++j) {
            if (flag[j]) {
                lw[b] = 1;
                break;
            }
        }
    }

    memset(memo, -1, sizeof(memo));

    function<ll(int, int, int, int, int)> dfs = [&](int b, int ls, int lk, int mx, int req) {
        if (b == -1) return req ? (f && !lk) : 1ll;

        if (memo[b][ls][lk][mx][req] != -1) return memo[b][ls][lk][mx][req];

        ll res = 0;
        int nb = (n >> b) & 1, kb = (k >> b) & 1, rb = (r >> b) & 1, m = mx - 1;

        for (int ub = 0; ub <= 1; ++ub) {
            if (kb == 0 && ub == 1) continue;
            if (!ls && ub > nb) continue;

            int nls = ls | (ub < nb), nlk = lk, nmx = m, nreq = req;

            if (ub == 1) {
                if (rb == 0) nlk = 1;
                if (nlk && nreq) continue;
            } else {
                bool isc = flag[b] && !nlk;
                if (isc) nreq = 0, nmx = max(nmx, mb[b]);

                if (kb == 1) {
                    bool cov = (m >= b) || isc;
                    if (!cov) {
                        if (rb == 1 || !lw[b] || nlk) continue;
                        nreq = 1;
                    }
                }
            }
            res += dfs(b - 1, nls, nlk, nmx + 1, nreq);
        }
        return memo[b][ls][lk][mx][req] = res;
    };

    cout << dfs(60, 0, 0, 0, 1) << endl;
}

头文件

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define endl "\n"
using namespace std;

using ll = long long;
using ld = long double;
using ui = unsigned;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;

void init() {
}

void solve() {
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    init();

    int t = 1;
    cin >> t;
    cout << fixed << setprecision(15);
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }

    return 0;
}