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

个人难度评级

签到:$ABCHI$

简单:$DFG$

中等:$J$

困难:$E$

A 本场比赛灵感来源于树状数组出题组

按照数字从小到大检查即可,注意是其他数字,记得 $-1$ 。

void solve() {
    int n;
    cin >> n;
    map<int, int> cnt;
    for (int i = 0, x; i < n; ++i)
        cin >> x, cnt[x]++;
    int s = 0, ans = 0;
    for (auto [u, v] : cnt) {
        s += v;
        if (s - 1 >= 1.0 * (n - 1) * 0.8)
            ans += v * u;
    }
    cout << ans << endl;
}

B 构造部落

记录每个首领在位的年份计算即可。

void solve() {
    int n, q, s;
    cin >> n >> q >> s;
    vector<int> a(n);

    a[0] = s;
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        if (i + 1 < n)
            a[i + 1] = a[i] + x;
    }
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << a[x - 1] + y - 1 << endl;
    }
}

C 墨提斯的排列

在一组数的编码中,若任意两个相邻的代码只有一位二进制数不同,则称这种编码为格雷码

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < (1 << n); ++i) {
        cout << (i ^ (i >> 1)) << " ";
    }
    cout << endl;
}

D 东风谷早苗与博丽灵梦

求解 $a\cdot c_1 + s\cdot c_2 = x$ ,且 $max(c_1,c_2)$ 最小。

首先存在解的充要条件是 $\gcd(a,s)|x$ 。我们先用扩展欧几里得求出 $u,v$ 使得 $au+sv = g = gcd(a,s)$ 。然后令 $k=\frac{x}{g}$ 得到一组通解
$$c1 = u\cdot k + \frac{s}{g}t,\quad c2 = v\cdot k – \frac{a}{g}t$$
由于非负,得到 $t$ 的取值范围为 $[\lceil-\frac{u\cdot k}{\frac{s}{g}}\rceil,\lfloor\frac{v\cdot k}{\frac{a}{g}}\rfloor]$ 。由于 $max(c_1,c_2)$ 关于 $t$ 是凸的,因此最优点在使两者尽量接近的位置附近,检查一下即可。

注意中间乘法可能超过 $64$ 位,所以用 $\text{int128}$ 。

template <class T>
T exgcd(T a, T b, T &x, T &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    T d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

i128 flr(i128 a, i128 b) {
    if (a >= 0)
        return a / b;
    return -((-a + b - 1) / b);
}
i128 cl(i128 a, i128 b) {
    if (a >= 0)
        return (a + b - 1) / b;
    return -((-a) / b);
}

ostream &operator<<(ostream &os, __int128 n) {
    if (n == 0)
        return os << 0;
    if (n < 0) {
        os << '-';
        n = -n;
    }
    string s;
    while (n > 0) {
        s += char('0' + n % 10);
        n /= 10;
    }
    reverse(s.begin(), s.end());
    return os << s;
}

void solve() {
    ll x, a, s;
    cin >> x >> a >> s;
    ll u, v, g = exgcd(a, s, u, v);
    if (x % g != 0) {
        cout << "No" << endl;
        return;
    }
    i128 k = (i128)(x / g), c10 = (i128)u * k, c20 = (i128)v * k;
    i128 s1 = (i128)(s / g), s2 = (i128)(a / g);

    i128 tmin = cl(-c10, s1), tmax = flr(c20, s2);
    if (tmin > tmax) {
        cout << "No" << endl;
        return;
    }

    i128 t0 = flr(c20 - c10, s1 + s2);

    vector<i128> cand = {tmin, tmax, t0 - 1, t0, t0 + 1};
    sort(all(cand));
    cand.erase(unique(all(cand)), cand.end());

    bool ok = false;
    i128 C1 = 0, C2 = 0, mx = ((i128)1 << 120);
    for (i128 t : cand) {
        if (t < tmin || t > tmax)
            continue;
        i128 c1 = c10 + s1 * t, c2 = c20 - s2 * t;
        if (c1 < 0 || c2 < 0)
            continue;
        i128 cur = c1 > c2 ? c1 : c2;
        if (cur < mx) {
            mx = cur;
            C1 = c1;
            C2 = c2;
            ok = true;
        }
    }
    if (!ok) {
        cout << "No" << endl;
        return;
    }
    cout << "Yes" << endl;
    cout << C1 << " " << C2 << endl;
}

E 立希的扫雷构造

总危险值等价于网格图中连接空地和地雷的边的总数量,是一个典型的最大割问题,我们需要将 $n\times m$ 个点划分为两个集合(大小分别为 $k$ 和 $n\times m−k$​ ),使得两个集合之间的连边数量最大。

由于数据范围 $n,m\leq 9$ ,直接暴搜复杂度 $2^{81}$ 显然不行。但宽度很小,可以用状压 $\text{DP}$ 。因为涉及 $8$ 连通,我们需要维护一个轮廓线来确定当前格子与已处理格子的连通情况。当处理到第 $p$ 个格子时,轮廓线需要覆盖从 $p−1$(左)到 $p−m−1$(左上)的范围。因此,我们需要一个长度为 $m+1$ 的二进制掩码来记录。也就是 $dp[p][mask][k]$ 为处理完第 $p$ 个格子,轮廓线状态为 $mask$ ,已放置 $k$ 个地雷时的最大贡献值。只有空地和地雷相邻的时候才有贡献,所以状态转移方程为
$$ndp[nmask][nj]=max(ndp[nmask][nj],dp[mask][j]+\sum\limits(neighbor\oplus v))$$
题目中 $T\leq 10^4$ ,如果对每个询问都跑一遍 $DP$ 会超时。注意到 $n,m\leq 9$ ,所以我们可以缓存每种尺寸 $(n,m)$​ 的计算结果。对于新的询问,如果该尺寸已计算过,直接查表并回溯构造答案即可。

bool vis[10][10];
vector<int> mans[10][10], mend[10][10], mtr[10][10];

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

    bool sw = false;
    if (n < m) {
        swap(n, m);
        sw = true;
    }
    if (!vis[n][m]) {
        int len = n * m, lim = 1 << (m + 1), sz = lim * (len + 1);

        mtr[n][m].resize(len * sz);
        mans[n][m].assign(len + 1, -1);
        mend[n][m].assign(len + 1, -1);

        vector<int> dp(sz, -1);
        dp[0] = 0;

        auto id = [&](int s, int k) {
            return s * (len + 1) + k;
        };

        for (int p = 0; p < len; ++p) {
            int r = p / m, c = p % m;
            vector<int> ndp(sz, -1);
            int base = p * sz;

            bool hl = c > 0;
            bool htl = r > 0 && c > 0;
            bool ht = r > 0;
            bool htr = r > 0 && c < m - 1;

            for (int s = 0; s < lim; ++s) {
                for (int j = 0; j <= p; ++j) {
                    if (dp[id(s, j)] == -1)
                        continue;

                    for (int v = 0; v < 2; ++v) {
                        int nj = j + v;

                        int add = 0;
                        if (hl)
                            add += ((s >> 0) & 1) ^ v;
                        if (htl)
                            add += ((s >> m) & 1) ^ v;
                        if (ht)
                            add += ((s >> (m - 1)) & 1) ^ v;
                        if (htr)
                            add += ((s >> (m - 2)) & 1) ^ v;

                        int ns = ((s << 1) & (lim - 1)) | v;
                        int val = dp[id(s, j)] + add;
                        int nidx = id(ns, nj);

                        if (val > ndp[nidx]) {
                            ndp[nidx] = val;
                            int drop = (s >> m) & 1;
                            mtr[n][m][base + nidx] = (drop << 1) | v;
                        }
                    }
                }
            }
            dp = move(ndp);
        }

        for (int s = 0; s < lim; ++s) {
            for (int j = 0; j <= len; ++j) {
                int val = dp[id(s, j)];
                if (val > mans[n][m][j]) {
                    mans[n][m][j] = val;
                    mend[n][m][j] = s;
                }
            }
        }
        vis[n][m] = true;
    }

    cout << mans[n][m][k] << endl;
    vector<string> g(n, string(m, '.'));
    int cs = mend[n][m][k], ck = k;
    int len = n * m, lim = 1 << (m + 1), sz = lim * (len + 1);

    auto id = [&](int s, int k) {
        return s * (len + 1) + k;
    };

    for (int p = len - 1; p >= 0; --p) {
        int info = mtr[n][m][p * sz + id(cs, ck)];

        int v = info & 1;
        int drop = (info >> 1) & 1;

        if (v)
            g[p / m][p % m] = '*';

        cs = (cs >> 1) | (drop << m);
        ck -= v;
    }

    if (sw) {
        for (int j = 0; j < m; ++j) {
            for (int i = 0; i < n; ++i)
                cout << g[i][j];
            cout << endl;
        }
    } else {
        for (int i = 0; i < n; ++i)
            cout << g[i] << endl;
    }
}

F 爱音的01串构造

$$score = 2\cdot T_{01} + 1\cdot T_0 + 0\cdot T_1$$

所以我们要最小化 $T_0 + 2T_1$ 。

因此我们应把 $0$ 和 $1$ 分成尽可能多的短块来减小各自的 “只含单一字符子串” 的贡献;但由于 $T_1$ 权重为 $2$ ,比 $T_0$ 更重要,所以优先把 $1$ 分成尽可能多的块(数量上限为 $a+1$ )。同样 $0$ 也要尽量分成多块(上限为 $b+1$ )。

所以策略:

  • 设要把 $b$ 个 $1$ 分成 $r_1=\min(b,\;a+1)$ 个块,把 $a$ 个 $0$ 分成 $r_0=\min(a,\;b+1)$ 个块;
  • 把每种字符尽量均匀分配到对应的块(大小差 $\leq 1$ );
  • 若 $r_1\ge r_0$ 则从 ‘$1$’ 开始交替,否则从 ‘$0$’ 开始交替。
void solve() {
    int a, b;
    cin >> a >> b;
    if (a == 0) {
        cout << string(b, '1') << endl;
        return;
    }
    if (b == 0) {
        cout << string(a, '0') << endl;
        return;
    }
    int r0 = min(a, b + 1), r1 = min(b, a + 1);

    vector<int> A(r0, a / r0);
    for (int i = 0; i < a % r0; ++i)
        A[i]++;
    vector<int> B(r1, b / r1);
    for (int i = 0; i < b % r1; ++i)
        B[i]++;

    string ans = "";
    bool f = (r1 >= r0);
    int i1 = 0, i0 = 0;
    while (i1 < r1 || i0 < r0) {
        if (f) {
            if (i1 < r1) {
                ans.append(B[i1], '1');
                ++i1;
            }
            if (i0 < r0) {
                ans.append(A[i0], '0');
                ++i0;
            }
        } else {
            if (i0 < r0) {
                ans.append(A[i0], '0');
                ++i0;
            }
            if (i1 < r1) {
                ans.append(B[i1], '1');
                ++i1;
            }
        }
    }
    cout << ans << endl;
}

G 真白的幻觉

使用 $dfs$ 搜索即可,为了避免重复计算,我们只需要搜索数字非递减的序列。

map<ll, int> memo;

struct res {
    ll num, f, g;

    bool operator<(const res &other) const {
        if (g != other.g) {
            return g > other.g;
        }
        return num < other.num;
    }
};

vector<res> cand;

void solve() {
    auto calc = [&](ll x) {
        ll res = 1;
        for (auto v : to_string(x))
            res *= isdigit(v) * (v - '0');
        return res;
    };
    function<int(ll)> get = [&](ll x) {
        if (x < 10)
            return 0;
        if (memo.count(x))
            return memo[x];

        ll nxt = calc(x);
        return memo[x] = 1 + get(nxt);
    };
    function<void(int, ll, ll, int)> dfs = [&](int len, ll cur, ll prod, int lst) {
        if (len > 0) {
            int p = 0;
            if (cur < 10)
                p = 0;
            else
                p = 1 + get(prod);

            cand.pb({cur, prod, p});
        }

        if (len == 18)
            return;

        for (int d = lst; d <= 9; d++) {
            dfs(len + 1, cur * 10 + d, prod * d, d);
        }
    };
    for (int i = 2; i <= 9; i++) {
        dfs(1, i, i, i);
    }
    sort(all(cand));

    res A = cand[0];
    res B = {0, 0, -1};

    for (int i = 1; i < cand.size(); i++) {
        if (cand[i].f != A.f) {
            B = cand[i];
            break;
        }
    }
    cout << A.num << " " << B.num << endl;
}

一组合法的解为

277777788888899 27777789999999999

H 时不时使使用玉米加农炮掩饰害羞的邻座艾莉同学

暴力更新,维护最大堆来快速取当前全局最大覆盖和,对于每次对某个中心的增量,我们把新的 $(sum, idx)$ 压入堆,查询时不断弹出堆顶直到堆顶记录与当前 $sum$ 一致。

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

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<ll>> g(n, vector<ll>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> g[i][j];

    vector<ll> sum(n * m);

    auto id = [&](int x, int y) {
        return x * m + y;
    };

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

    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < m; ++y) {
            if (g[x][y] == 0)
                continue;
            ll v = g[x][y];
            for (int k = 0; k < 13; ++k) {
                int nx = x + dx[k], ny = y + dy[k];
                if (check(nx, ny)) {
                    sum[id(nx, ny)] += v;
                }
            }
        }
    }
    priority_queue<PLL> pq;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            pq.emplace(sum[id(i, j)], id(i, j));

    while (q--) {
        int x, y;
        ll z;
        cin >> x >> y >> z;
        x--, y--;
        g[x][y] += z;
        for (int k = 0; k < 13; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (check(nx, ny)) {
                sum[id(nx, ny)] += z;
                pq.emplace(sum[id(nx, ny)], id(nx, ny));
            }
        }
        while (!pq.empty()) {
            auto [v, id] = pq.top();
            if (sum[id] == v) {
                cout << id / m + 1 << " " << id % m + 1 << endl;
                break;
            } else
                pq.pop();
        }
    }
}

I 初华的扭蛋机

不要赌博就是从这来的,怎么下注都是亏。

令 $K\sim B(3,\frac{1}{6})$ , $E(x) = 2x\cdot P(K=1)+3x\cdot P(k=2)+10x\cdot P(k=3)$
$P(K=1) = \binom{3}{1}(\frac{1}{6})(\frac{5}{6})^2=\frac{25}{72}\\P(K=2) = \binom{3}{2}(\frac{1}{6})^2(\frac{5}{6})=\frac{5}{72}\\P(K=3) = (\frac{1}{6})^3=\frac{1}{216}\\E(x) = x\cdot (2\cdot \frac{25}{72} + 3\cdot\frac{5}{72}+10\cdot\frac{1}{216}) = \frac{205}{216}x$
设下注总筹码 $S = \sum x_i$ ,$E = h+\sum E(x_i)=(6-S)+S\cdot \frac{206}{216} = 6-S\cdot \frac{11}{216}$ ,单调递减。

######

J 立希坐地铁

并不是网格上所有的点都需要作为图的节点。我们只关心起点、终点以及换乘站。这些点是我们可能停下来、换乘或结束旅程的地方。在每个关键点,我们可能处于不同的线路/方向上。一共有 $6$ 种线路方向:

  • 水平东行
  • 水平西行
  • 竖直南行
  • 竖直北行
  • 环线顺时针
  • 环线逆时针

因此,对于每个关键点 $u$,我们建立 6 个图节点,表示“位于点 $u$ 且正处于/准备乘坐某方向的线路”。记为 $(u,dir)$ 。此外,为了处理换乘,对于每个换乘站 $u$ ,我们还要引入一个虚拟的站厅节点 $H$ 。

对于普通的行驶边,我将所有关键点按照它们所在的线路分组,在同一条线路上相邻的两个关键点 $u,v$ 之间连权值为 $2\times \text{距离}$ 的边。如果是单向线路,则连单向边;如果是双向线路,则分别建立对应的单向边。在换乘站,我们就先连一条到 $H$ 的权值为 $0$ 的边,再连一条从 $H$ 到具体的节点的权值为 $1$ 的边。

然后再图上跑 $\text{Dijkstra}$ ,初始 $6$ 个方向 $\text{dist}$ 均为 $0$ ,取终点处 $6$ 个方向的最小值即可。

constexpr ll INF = 4e18;

struct Pt {
    int x, y;
    bool tr;
};

void solve() {
    int n, m;
    cin >> n >> m;
    int sx, sy, ex, ey;
    cin >> sx >> sy >> ex >> ey;

    vector<Pt> pts;
    map<PII, int> pid;

    auto get = [&](int x, int y) {
        if (pid.find({x, y}) == pid.end()) {
            pid[{x, y}] = pts.size();
            pts.pb({x, y, false});
        }
        return pid[{x, y}];
    };

    int sid = get(sx, sy), eid = get(ex, ey);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        int id = get(u, v);
        pts[id].tr = true;
    }

    int k = pts.size(), virt = 6 * k, tot = 7 * k;
    vector<vector<PLL>> g(tot);

    for (int i = 0; i < k; ++i) {
        if (pts[i].tr) {
            int vn = virt + i;
            for (int d = 0; d < 6; ++d) {
                g[i * 6 + d].pb({vn, 0});
                g[vn].pb({i * 6 + d, 1});
            }
        }
    }

    vector<vector<PII>> rs(n + 1), cs(n + 1);
    vector<vector<PLL>> rgs(n / 2 + 1);

    for (int i = 0; i < k; ++i) {
        rs[pts[i].x].pb({pts[i].y, i});
        cs[pts[i].y].pb({pts[i].x, i});

        int k = min({pts[i].x, n - pts[i].x + 1, pts[i].y, n - pts[i].y + 1});
        ll s = n - 2 * k + 1;
        ll pos = 0;
        if (pts[i].x == k)
            pos = pts[i].y - k;
        else if (pts[i].y == n - k + 1)
            pos = s + (pts[i].x - k);
        else if (pts[i].x == n - k + 1)
            pos = 2 * s + (n - k + 1 - pts[i].y);
        else
            pos = 3 * s + (n - k + 1 - pts[i].x);
        rgs[k].pb({pos, i});
    }

    for (int i = 1; i <= n; ++i) {
        sort(all(rs[i]));
        for (int j = 0; j + 1 < rs[i].size(); ++j) {
            int u = rs[i][j].se, v = rs[i][j + 1].se;
            ll d = 2ll * (rs[i][j + 1].fi - rs[i][j].fi);
            g[u * 6 + 0].pb({v * 6 + 0, d});
            g[v * 6 + 1].pb({u * 6 + 1, d});
        }
    }
    for (int i = 1; i <= n; ++i) {
        sort(all(cs[i]));
        for (int j = 0; j + 1 < cs[i].size(); ++j) {
            int u = cs[i][j].se, v = cs[i][j + 1].se;
            ll d = 2ll * (cs[i][j + 1].fi - cs[i][j].fi);
            g[u * 6 + 2].pb({v * 6 + 2, d});
            g[v * 6 + 3].pb({u * 6 + 3, d});
        }
    }
    for (int k = 1; k <= n / 2; ++k) {
        if (rgs[k].empty())
            continue;
        sort(all(rgs[k]));
        ll len = 4LL * (n - 2 * k + 1);
        int sz = rgs[k].size();
        for (int i = 0; i < sz; ++i) {
            int u = rgs[k][i].se;
            int v = rgs[k][(i + 1) % sz].se;
            ll d = (rgs[k][(i + 1) % sz].fi - rgs[k][i].fi + len) % len;
            if (d == 0 && len > 0)
                d = len;
            g[u * 6 + 4].pb({v * 6 + 4, 2 * d});
            g[v * 6 + 5].pb({u * 6 + 5, 2 * d});
        }
    }

    priority_queue<PLL, vector<PLL>, greater<PLL>> pq;
    vector<ll> dist(tot, INF);
    vector<int> par(tot, -1);
    for (int d = 0; d < 6; ++d) {
        dist[sid * 6 + d] = 0;
        pq.push({0, sid * 6 + d});
    }

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u])
            continue;
        for (auto &[v, w] : g[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                par[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    ll ans = INF;
    int edn = -1;
    for (int d = 0; d < 6; ++d) {
        if (dist[eid * 6 + d] < ans) {
            ans = dist[eid * 6 + d];
            edn = eid * 6 + d;
        }
    }

    if (ans == INF) {
        cout << "Impossible!" << endl;
        return;
    }

    cout << ans << endl;

    vector<int> path;
    for (int u = edn; u != -1; u = par[u])
        path.pb(u);
    reverse(all(path));

    string ss = "EWSNCI";
    vector<pair<char, int>> segs;
    int cd = path[0] % 6;

    for (int i = 0; i < path.size(); ++i) {
        if (path[i] >= virt) {
            int u = path[i - 1] / 6;
            segs.pb({ss[cd], u});
            if (i + 1 < path.size())
                cd = path[i + 1] % 6;
        }
    }
    segs.pb({ss[cd], path.back() / 6});

    cout << segs.size() << endl;
    cout << sx << " " << sy << endl;
    for (auto [u, v] : segs) {
        cout << u << endl;
        cout << pts[v].x << " " << pts[v].y << 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;
}
暂无评论

发送评论 编辑评论


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