题解 | 练习赛 Round 150
|
34
|
0
|
牛客,练习赛,题解

2650 字
|
34 分钟

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 数论迷城

如果有任意一个区间大小 $\geq 2$ ，必然能够选出 $l\leq x\leq x+1\leq r$ ，使得最大公因数为 $1$ 。

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

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 乘鲨破浪

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

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

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

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 异或疑惑

让 $a_i$ 和 $a_j$ 同时异或上 $x$ ，我们可以把它看成，在 $i$ 和 $j$ 之间连了一条权值为 $x$ 的边，最终这 $n$ 个顶点会被划分为若干个连通块。那么操作数就等于 $n-\text{连通块数量}$ 。

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

  • $Sum\geq X$
  • $Sum\equiv X\pmod 2$

也就是说， $Sum = X + 2E$ ，$E$ 是某个非负整数。

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

  • 连通块大小为 $1$ ，操作不了。
  • 联通块大小为 $2$ ，只有两个数字 $a_1$ 和 $a_2$ ，有 $X=a_1\oplus a_2, a_1+a_2 = X+2E$ ，所以有 $a_1 \& a_2 = E$ 。
  • 连通块大小为 $3$ ，可以操作出任意和。

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

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 似数佳对

题目要求我们对每个 $k\in[1,n]$ ，找到一个最大的 $d_i$ ，使得存在一个 $i<k$ 满足“好的下标对”条件，即 $a_i+\min\limits_{i\leq x\leq k}b_x\leq c_k$ 。如果找不到这样的 $i$ ，则 $ans_k=0$ 。

在计算 $ans_k$ 时，我们需要考察所有已经处理过的下标 $i\in [1,k−1]$ 。对每一个这样的 $i$ ，我们需要判断它是否满足条件。

我们定义 $V_{i,j}=a_i+\min\limits_{⁡x=i…j}b_x$ 。那么在计算 $ans_k$ 时，我们要找的就是满足 $V_{i,k}≤c_k$ 的所有 $i<k$ 中，对应的 $d_i$ 的最大值。对于任意一个固定的 $i<k−1$ ，有：
$$V_{i,k−1}=a_i+\min⁡(b_i,b_{i+1},…,b_{k−1})\\V_{i,k}=a_i+\min⁡(b_i,b_{i+1},…,b_{k−1},b_k)=a_i+\min⁡(\min\limits_{⁡x=i…k−1}b_x,b_k)$$
利用 $a + min(b, c) = min(a+b, a+c)$​ ，我们可以得到：
$$V_{i,k}=\min⁡(a_i+\min\limits_{⁡x=i…k−1}b_x,a_i+b_k)=min⁡(V_{i,k−1},ai+bk)$$
根据上面的递推关系，在计算 $ans_k$ 时，我们需要对所有 $i\in [1,k−1]$ 完成以下操作：

  • 全体更新：对于每个 $i$ ，都将其关联的检查值 $V_{i,k−1}$ 更新为 $V_{i,k}=\min⁡(V_{i,k−1},a_i+b_k)$ 。
  • 查询：在所有更新后的值中，找到满足 $V_{i,k}\leq c_k$ 的那些 $i$ ，并求出它们对应的 $d_i$ 的最大值。
  • 插入：处理完 $k$ 之后，需要将下标 $k$ 的信息 $(a_k,b_k,d_k)$ 加入数据集合，以备后续的计算。

所以我们使用以 $d_i$ 为键值的 $\text{Treap}$ 来维护。

为了执行更新操作 $V:=\min(V,a_i+b_k)$ ，我们不仅需要存储当前的 $V$ 值，还需要存储原始的 $a_i$ 值。因此，$\text{Treap}$ 的每个节点需要维护以下信息：

  • $sa$ : 存储 $a_i$ 的值。
  • $sb$ : 存储 $V_{i,k}$ 的值。

如果多个 $i$ 拥有相同的 $d_i$ ，它们会对应到 $\text{Treap}$ 中的同一个键。对于查询 $V_{i,k}≤c_k$ 来说，只要这些 $i$ 中有一个满足条件即可。因此，对于一个键 $d$ ，我们只需要关心所有 $d_i = d$ 的下标中，那个拥有最小 $V$ 值的 $i$ 。所以，节点中存储的应该是：

  • $sa (a_{min})$ : 对于键为 $d$ 的节点，存储 $\min\limits_{i:d_i=d}{ai}$ 。
  • $sb (V_{min})$ : 对于键为 $d$ 的节点，存储 $\min\limits_{i:d_i=d}{V_{i,k−1}}$ 。

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

  • $ma$ : 子树中所有 $sa$ 的最小值。
  • $mb$ : 子树中所有 $sb$ 的最小值。

我们的全体更新操作是 $sb_i :=\min(sb_i, sa_i + b_k)$ 。这可以被一个懒标记实现。懒标记 $tag$ 存一个值 $v$ ，表示要对子树中所有节点的 $sb$ 执行 $sb:=\min(sb, sa + v)$ 的操作。当标记下传时，子节点的 $sb$ 和 $mb$ 都会相应更新。
在第 $k$ 步 ：

  1. 更新: 在 $\text{Treap}$ 的根节点打上一个值为 $b_k$ 的懒标记。这个标记的含义是，对于树中所有节点，执行 $sb = \min(sb, sa + b_k)$ 。通过懒标记的机制，这个更新会被高效地应用到全树。此时，所有节点的 $sb$ 值就从 $V_{i,k−1}$ 更新成了 $V_{i,k}$ 。
  2. 查询: 我们需要在 $\text{Treap}$ 中查找满足 $mb <= c_k$ 的最大键值 $d$ 。这可以在平衡树上高效地完成：从根节点开始，优先向右子树搜索。如果右子树的 $mb \leq c_k$ ，则答案一定在右子树中；否则，检查当前节点是否满足 $sb \leq c_k$；如果还不满足，再向左子树搜索。这个过程可以找到最大的满足条件的 $d$ 值。这个值就是 $ans_k$ 。
  3. 插入: 将当前下标 $k$ 的信息插入 $\text{Treap}$ 。创建一个键为 $d_k$ 的新节点。其初始值为 $sa = a_k，sb = a_k + b_k$ (因为对于下标 $k$ 自身而言，$\min\limits_{x=k…k}b_x=b_k$ ）。如果树中已经存在键为 $d_k$ 的节点，则更新该节点的 $sa$ 和 $sb$ 为原有值与新值之间的较小者。
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 集逆态没

“好”的集合 $S$ 定义为：集合中每个元素 $x\in[l,r]$ ，并且所有元素的按位或包含于 $k$ 。这意味着 $S$ 中所有的元素都是 $k$ 的子集。$f(S)$ 是集合 $S$ 中所有元素的按位与，设 $f(S)=u$ 。对于合法的 $u$ ，必定满足：

  • $u\leq n$ 。
  • $u\subseteq k$ 。
  • 集合 $S(u)={x\in[l,r]∣u\subseteq x\subseteq k}$ 不能是空集，并且其按位与的值必须恰好等于 $u$ 。

要使得按位与的结果恰好是 $u$ ，对于 $\text{k}$\$\text{u}$ 中的每一个比特位 $b$（即 $u_b=0$ 且 $k_b=1$ ），必须在 $S(u)$ 中至少存在一个元素 $x$ 满足 $x_b=0$ 。换句话说，将 $k$ 强制在第 $b$ 位赋 0 得到的集合也必须与 $[l,r]$ 有交集。

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

用数位 $dp$ 进行维护即可。

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;
}
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇