02-07 18:55 已编辑因循村数据分析师发布于浙江

关注

题解 | 2026牛客寒假算法基础集训营 3

宙天

https://ac.nowcoder.com/acm/contest/120563/A

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

个人难度评级

签到： $ABGHJ$

简单： $CEFI$

中等： $D$

A 宙天

因为如果有 $n\times(n+1) = x$ ，就必然有 $t = sqrt(x)$ 满足 $n< t< n+1$ ，所以有 $n = \lfloor t\rfloor$ 。

void solve() {
    int x;
    cin >> x;
    int t = sqrt(x);
    if (t * (t + 1) == x)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

B Random

看到那串加黑加粗就应该想到， $[1,10^9]$ 内满足 $\gcd>1$ 的概率是很小的，我们检查前几个（我检查了前 $200$ 个）是否存在 $\gcd>1$ 即可。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < min(200, n); ++i) {
        for (int j = i + 1; j < min(200, n); ++j) {
            if (gcd(a[i], a[j]) != 1) {
                cout << a[i] << " " << a[j] << endl;
                return;
            }
        }
    }
    cout << -1 << endl;
}

C Inverted World

我觉得这道题应该会有一个很优雅的做法，但是我没想到。

最终的字符串一定为 $0101...$ 或 $1010...$ ，我们检查一下即可。

如果新的字符是能放到已经存在的链的末尾（不同），就直接放，否则新开一条链，贪心检查即可。

void solve() {
    int n;
    string s;
    cin >> n >> s;
    auto ssolve = [&](int st) {
        int e0 = 0, e1 = 0;
        for (int i = 0; i < n; ++i) {
            char nxt = ((i & 1) ? (st ? '0' : '1') : (st ? '1' : '0'));
            if (s[i] == nxt)
                continue;
            if (s[i] == '0') {
                if (e1 > 0) {
                    --e1;
                }
                ++e0;
            } else {
                if (e0 > 0) {
                    --e0;
                }
                ++e1;
            }
        }
        return e0 + e1;
    };
    cout << min(ssolve(0), ssolve(1)) << endl;
}

D 系ぎて

感觉是乱搞搞过去的。

我们先找 $1-1$ 的路径，然后再找 $2-2$ 的路径。为了避免 $1-1$ 把 $2-2$ 占用了，我们尝试 $4$ 种查找的优先方向（相当于让 $1-1$ 尽可能贴着边界走，把位置空出来），然后再找 $2-2$ 。如果这样找不出来，就先 $2-2$ 再 $1-1$ 。

struct Point {
    int x, y;
    bool operator==(Point other) {
        return x == other.x && y == other.y;
    }
    bool operator!=(Point other) {
        return !(*this == other);
    }
};

int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    vector<Point> p1, p2;
    for (int i = 0; i < n; ++i) {
        cin >> g[i];
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == '1')
                p1.pb({i, j});
            else if (g[i][j] == '2')
                p2.pb({i, j});
        }
    }

    auto check = [&](int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    };

    auto bfs = [&](Point st, Point end, vector<string> cur, char op, vector<Point> &path, vector<int> order) {
        vector<vector<Point>> pa(n, vector<Point>(m, {-1, -1}));
        vector<vector<bool>> vis(n, vector<bool>(m));
        queue<Point> q;

        q.push(st);
        vis[st.x][st.y] = true;

        bool found = false;
        while (!q.empty()) {
            Point u = q.front();
            q.pop();

            if (u == end) {
                found = true;
                break;
            }

            for (int i : order) {
                int nx = u.x + dx[i], ny = u.y + dy[i];

                if (check(nx, ny) && !vis[nx][ny]) {
                    char c = cur[nx][ny];
                    if (c != '#' && (c == '0' || c == op)) {
                        vis[nx][ny] = true;
                        pa[nx][ny] = u;
                        q.push({nx, ny});
                    }
                }
            }
        }

        if (found) {
            Point curr = end;
            while (curr != st) {
                path.pb(curr);
                curr = pa[curr.x][curr.y];
            }
            path.pb(st);
            return true;
        }
        return false;
    };

    vector<vector<int>> orders = {
        {0, 2, 3, 1},
        {1, 2, 3, 0},
        {2, 0, 1, 3},
        {3, 0, 1, 2}};

    for (auto ord : orders) {
        vector<Point> path1;
        if (bfs(p1[0], p1[1], g, '1', path1, ord)) {
            vector<string> tmp = g;
            for (auto p : path1) {
                tmp[p.x][p.y] = '#';
            }

            vector<Point> path2;
            if (bfs(p2[0], p2[1], tmp, '2', path2, {0, 1, 2, 3})) {
                cout << "YES" << endl;
                return;
            }
        }
    }

    for (auto ord : orders) {
        vector<Point> path2;
        if (bfs(p2[0], p2[1], g, '2', path2, ord)) {
            vector<string> tmp = g;
            for (auto [r, c] : path2) {
                tmp[r][c] = '#';
            }

            vector<Point> path1;
            if (bfs(p1[0], p1[1], tmp, '1', path1, {0, 1, 2, 3})) {
                cout << "YES" << endl;
                return;
            }
        }
    }
    cout << "NO" << endl;
}

E 躯树の墓守

这玩意以前造数据的时候写过，改改直接能用了。

因为是最小生成树，我们选择 $n-1$ 条边作为树边 $T$ ，剩下 $m-n+1$ 条为非树边，显然我们会想到先去构造一条链，用 $t_{i}$ 连接第 $i$ 和第 $i+1$ 个点，把树边都放进去。然后对于权值大于 $t[i]$ 的非树边，我们可以把他分配给任意 $u<i$ 和 $i$ 的边（因为已经通过权值更小的 $t_i$ 连接了，具体见 $\text{Kruskal}$ 算法的详解）

然后我们希望权值和为 $k$ ，下界显然就是 $1,2,...,n$ 。对于上界，对于第 $i$

小的树边 $t_i$ （连接 $i$ 和 $i+1$ ），在它之前必须有足够的“空间”容纳所有小于 $t_i$ 的非树边。小于 $t_i$ 的非树边数量为 $(t_i−1)−(i−1)=t_i−i$ 。这些边必须连接 $1,…,i$ 之间的节点。该部分节点最多能容纳 $\binom{i}{2}$ 条边，其中 $i−1$ 条是树边，故能容纳 $\binom{i}{2}-(i-1)$ 条非树边，也就是 $t_i\leq \binom{i}{2}+1$ ，同时还需要满足， $t_i$ 后面的数有空间放置，即 $t_i\leq m−(n−1−i)$ 。这样就能得到上界了。

然后我们从 $t_i=i$ 开始，从 $i=n−1$ 到 $1$ 贪心地增加 $t_i$ 以凑足总和 $k$ 即可。

void solve() {
    int n;
    ll m, k;
    cin >> n >> m >> k;

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

    ll flr = 1ll * n * (n - 1) / 2;
    if (k < flr) {
        cout << "NO" << endl;
        return;
    }

    vector<ll> lim(n);
    for (int i = 1; i < n; ++i) {
        lim[i] = min(1ll * i * (i - 1) / 2 + 1, 1ll * m - (n - i - 1));
    }

    vector<ll> T(n);
    T[n - 1] = lim[n - 1];
    for (int i = n - 2; i >= 1; --i) {
        T[i] = min(lim[i], T[i + 1] - 1);
        if (T[i] < i) {
            cout << "NO" << endl;
            return;
        }
    }

    ll cl = 0;
    for (int i = 1; i < n; ++i)
        cl += T[i];
    if (k > cl) {
        cout << "NO" << endl;
        return;
    }

    vector<ll> t(n);
    for (int i = 1; i < n; ++i)
        t[i] = i;

    ll cur = flr, rem = k - cur;
    for (int i = n - 1; i >= 1; --i) {
        if (rem == 0)
            break;
        ll u = T[i];
        if (i < n - 1)
            u = min(u, t[i + 1] - 1);

        ll add = min(rem, u - t[i]);
        t[i] += add;
        rem -= add;
    }

    cout << "YES" << endl;
    vector<bool> flg(m + 2);
    for (int i = 1; i < n; ++i) {
        cout << i << " " << i + 1 << " " << t[i] << endl;
        if (t[i] <= m)
            flg[t[i]] = 1;
    }

    vector<int> nxt(n + 1, 1);
    queue<int> q;
    int ptr = 1;

    for (ll w = 1; w <= m; ++w) {
        if (w <= m && flg[w])
            continue;

        while (ptr < n && t[ptr] < w) {
            q.push(ptr + 1);
            ptr++;
        }

        while (q.size()) {
            int u = q.front();
            if (nxt[u] < u - 1) {
                cout << nxt[u] << " " << u << " " << w << endl;
                nxt[u]++;
                break;
            } else {
                q.pop();
            }
        }
    }
}

F Energy Synergy Matrix

可以打表直接看出来规律。

大致的博弈如下：

小红：在自己回合尽量在当前区块内补强顶排的连续通道或底排的连续通道，保证在任意时间点，每个 $5$ 列区块内至少保留一个长度为 $4$ 的连通路段（从该区块左端到右端在不走回头的情况下能用至多 $4$ 步穿过局部），从而紫方不能在区块内制造出同时堵顶和堵底使得局部必须多走超过 $1$ 的情形
小紫：在自己的回合在区块内选择一个配对格子（同一列的另一行或相邻列）放置障碍，使得在该区块内顶部连续直通被破坏并且底部可绕过的短路也被控制，结果是任何穿过这个区块的最短路径要比不受阻时多 $1$ 。

感觉还是打表靠谱。

void solve() {
    int n;
    cin >> n;
    cout << n - 1 + n / 5 << endl;
}

G スピカの天秤

相等拿一个就能直接破坏，不等就多的那个从大到小贪心拿。

void solve() {
    int n, m;
    ll Sa = 0, Sb = 0;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; ++i)
        cin >> a[i], Sa += a[i];
    for (int i = 0; i < m; ++i)
        cin >> b[i], Sb += b[i];
    sort(all(a));
    sort(all(b));
    if (Sa == Sb) {
        cout << 1 << endl;
    } else if (Sa > Sb) {
        int cnt = 0;
        while (Sa > Sb) {
            Sa -= a.back();
            a.pob();
            cnt++;
        }
        cout << cnt << endl;
    } else {
        int cnt = 0;
        while (Sb > Sa) {
            Sb -= b.back();
            b.pob();
            cnt++;
        }
        cout << cnt << endl;
    }
}

H Tic Tac DREAMIN’

三角形 $A(x_a,y_a),B(x_b,y_b),O(x,0)$ 的面积为

\frac{1}{2}|(x_a-x)y_b-(x_b-x)y_a| = \frac{1}{2}|(x_ay_b-x_by_a+x(y_a-y_b)|

记 $C = x_ay_b - x_by_a$ ，面积为 $2$ 就需要 $|C+x(y_a-y_b)| = 4$ 。

如果 $y_a=y_b$ ，那么 $C$ 就必须等于 $4$ ，任意 $x$ 均满足，否则构造一下 $x = \frac{4-C}{y_a-y_b}$ 即可。

自己关注一下精度，如果经常忘了考虑精度就直接写到板子里。

void solve() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int c = x1 * y2 - x2 * y1;
    if (y1 == y2) {
        if (abs(c) == 4)
            cout << 0.0 << endl;
        else
            cout << "no answer" << endl;
    } else {
        cout << 1.0 * (4 - c) / (y1 - y2) << endl;
    }
}

I BenzenE

看到几个数字取异或和会很自然地想到用线性基。

令 $x_i = a_i\oplus b_i$ ，若初始都选 $a_i$ 的异或为 $S=\bigoplus a_i$ ，选取下标集合 $T$ 改用 $b_i$ 后 $S' = S\oplus \bigoplus\limits_{i\in T} x_i$ ，也就是我们要找到 $T$ 使得 $\bigoplus\limits_{i\in T} x_i = S$ 。

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

    LB<ll> lb;
    for (int i = 0; i < n; ++i) {
        if (x[i] != 0)
            lb.insert(x[i], i);
    }

    auto [f, mask] = lb.check(S);
    if (!f) {
        cout << -1 << endl;
        return;
    }
    vector<int> vis(n);
    for (auto v : lb.choose(mask))
        vis[v] = 1;
    for (int i = 0; i < n; ++i) {
        cout << (vis[i] ? b[i] : a[i]) << " ";
    }
    cout << endl;
}

J Branch of Faith

完全二叉树上深度为 $d$ 的节点编号范围是 $[2^d,\,2^{d+1}-1]$ 。

void solve() {
    ll n;
    int q;
    cin >> n >> q;
    while (q--) {
        ll x;
        cin >> x;
        int d = 63 - __builtin_clzll(x);
        ll L = 1ll << d, R = min((1ll << (d + 1)) - 1, n);
        cout << R - L + 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>;
using TIII = tuple<int, int, int>;
using TLLL = tuple<ll, 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;
}

线性基

template <class T>
struct LB {
    using ull = unsigned long long;
    static constexpr int BASE = sizeof(T) * 8 - 1;
    vector<T> d, p;
    int cnt, flag;
    vector<ull> mask;
    vector<int> rep;

    LB() {
        d.assign(BASE + 1, 0);
        p.assign(BASE + 1, 0);
        mask.assign(BASE + 1, 0);
        cnt = flag = 0;
    }
    bool insert(T val, int idx) {
        ull cur = 0;
        for (int i = BASE - 1; i >= 0; i--) {
            if (val & (1ll << i)) {
                if (!d[i]) {
                    d[i] = val;
                    mask[i] = cur | (1ull << rep.size());
                    rep.push_back(idx);
                    return true;
                }
                val ^= d[i];
                cur ^= mask[i];
            }
        }
        flag = 1;
        return false;
    }
    pair<bool, ull> check(T val) {
        ull res = 0;
        for (int i = BASE - 1; i >= 0; --i) {
            if (val & (1ll << i)) {
                if (!d[i])
                    return {false, 0ull};
                val ^= d[i];
                res ^= mask[i];
            }
        }
        return {true, res};
    }
    ll ask_max() {
        ll res = 0;
        for (int i = BASE - 1; i >= 0; i--) {
            if ((res ^ d[i]) > res)
                res ^= d[i];
        }
        return res;
    }
    ll ask_min() {
        if (flag)
            return 0;
        for (int i = 0; i <= BASE - 1; i++) {
            if (d[i])
                return d[i];
        }
    }
    void rebuild() {
        for (int i = BASE - 1; i >= 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if (d[i] & (1ll << j))
                    d[i] ^= d[j];
            }
        }
        for (int i = 0; i <= BASE - 1; i++) {
            if (d[i])
                p[cnt++] = d[i];
        }
    }
    ll kthquery(ll k) {
        if (flag)
            k--;
        if (!k)
            return 0;
        ll res = 0;
        if (k >= (1ll << cnt))
            return -1;
        for (int i = BASE - 1; i >= 0; i--) {
            if (k & (1LL << i))
                res ^= p[i];
        }
        return res;
    }
    void Merge(const LB &b) {
        for (int i = BASE - 1; i >= 0; i--) {
            if (b.d[i]) {
                insert(b.d[i]);
            }
        }
    }
    vector<int> choose(ull mask) {
        vector<int> res;
        for (int i = 0; i < rep.size(); ++i) {
            if (mask & (1ull << i)) {
                res.pb(rep[i]);
            }
        }
        return res;
    }
};