牛客练习赛145 组题人题解

由于牛客各个页面使用的 CSS 不同，建议您在我的博客中打开本题解，以获得最优质的阅读体验，点击可跳转。

2025.11.01 01:41 更新

C 题原「非常规解」被 hack，数据与题解更新。感谢牛客用户 MorningstarSunset 的补充。

2025.10.31 22:01 更新

B 题新增证明，感谢群友 @w ww.com 的补充。

2025.10.30 17:04 更新

初始化。

总览

题号 题目名 知识点 Author 预估难度
A 别笑，你来了也过不了第二关 模拟 西行寺幽幽子 1000
B Del 贪心、字符串、排序 WIDA 1200
C 丢手绢 枚举、前缀和、思维 ikun_ac 1600
D 这是一场豪赌 概率dp、博弈论、数论 Kros.Mario 1900
E 小C的等差数列 构造、思维 yxh03 2300
F 最大深度 可持久化线段树、树形dp、分治 bandiaoz 2500

A.别笑，你来了也过不了第二关

知识点：模拟。

预估难度：1000。

为了通过尽可能多的关卡，对于每一项属性，必须满足所有已通过关卡中对该属性的最高要求。维护一个长度为 的数组，记录当前已通过关卡中，每一项属性的最高要求。每尝试通过一关，就更新这个数组，并计算新的属性总和。如果新的属性总和超过了 ，则无法通过当前关卡，停止闯关。否则，继续尝试下一关。最终通过的关卡数即为答案。

时间 ；空间 。

参考代码 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    long long x;
    cin >> n >> m >> x;

    vector<int> a(m);
    for (int i = 0; i < n; i++) {
        long long s = 0;
        for (int j = 0; j < m; j++) {
            int k;
            cin >> k;
            a[j] = max(a[j], k);
            s += a[j];
        }
        if (s > x) {
            cout << i << '\n';
            return 0;
        }
    }
    cout << n << '\n';

    return 0;
}

B.Del

Author: WIDA
Prepared by ikun_ac & WIDA

知识点：贪心、字符串、排序。

预估难度：1200。

从左到右遍历字符串，如果当前字符比下一个字符大，则删除当前字符；如果遍历到字符串末尾都没有找到这样的字符，则删除最后一个字符。将操作后的字符串塞入一个新的数组中。

随后排序，采用经典的贪心策略：对于任意两个字符串 和 ，如果 ，则 应该排在 的前面。

哦，对了，注意到字符串长度可能为 了吗，这样的串串操作后会成为空串，不能放入新的数组中，否则排序时会出错。

UPD：附原因，来自群友 @w ww.com：

严格弱序需满足如下条件（ 用于表示严格弱序）：

反自反性： 必须不成立。

非对称性：若 ，则 必须不成立。

传递性：若 ，则 必须成立。

不可比性的传递性：若 同时不成立，则 也必须同时不成立。

在本题中，不满足 ，也不满足 ，所以 了。

时间 ；空间 。

参考代码 
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    int n;
    cin >> n;

    vector<string> in;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        
        for (int i = 0; i < s.size(); i++) {
            if (s[i] > s[i + 1] || i == s.size() - 1) {
                s.erase(i, 1);
                break;
            }
        }
        
        if (s.size()) in.push_back(s);
    }
    
    sort(in.begin(), in.end(), [&](auto s, auto t) {
        return s + t < t + s;
    });

    string ans;
    for (auto &s : in) {
        ans += s;
    }
    cout << ans << "\n";
}

C.丢手绢

Author: ikun_ac
Prepared by ikun_ac

知识点：枚举、前缀和、思维。

预估难度：1600。

【常规解：思维】

关键的观察是，最优解中必然包含全局最大值点，记位置为 ，对应权值即 。固定其作为四点之一。问题转化为寻找另外三个点 ，使得 在环上交替出现，且 最大。

不妨固定点 ，那么 和 应当分别位于 到 的两条弧上，且分别取各自弧上的最大值。通过预处理以 为起点的顺时针和逆时针方向的前缀最大值数组（或使用稀疏表等数据结构无脑实现），可以在 时间内查询任意弧上的最大值。

此时，遍历 点，计算并更新最大价值即可。

时间 ；空间 。

【非常规解】

为了最大化两条线段权值的乘积，可以推断出最优解的四个元素必然是原数组中值最大的若干个元素。

猜测数据无法造的极端强，直接四重循环暴力枚举所有可能的四个点。可以发现，当取前 个元素时，可以稳定的得到答案。

证明不详，欢迎补充。我们真的尽力造数据了qwq。

UPD：该做法已被 hack，详情请见 该处，感谢牛客用户 MorningstarSunset 的补充，数据已同步更新，此处保留仅作展示。

参考代码 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        rotate(a.begin(), max_element(a.begin(), a.end()), a.end());

        vector<int> suf(n + 1, -1E9);
        for (int i = n - 1; i >= 0; i--) {
            suf[i] = max(a[i], suf[i + 1]);
        }

        long long res = 0;
        int mx = 0;
        for (int i = 2; i + 1 < n; i++) {
            mx = max(mx, a[i - 1]);
            res = max(res, 1LL * (a[0] + a[i]) * (mx + suf[i + 1]));
        }
        cout << res << '\n';
    }

    return 0;
}

// 该做法已被 hack，此处保留仅作展示。
#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n), b(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        iota(b.begin(), b.end(), 0);
        sort(b.begin(), b.end(), [&](int i, int j) { 
            return a[i] > a[j]; 
        });
        
        int mx = min(14, n);
        vector<int> id(b.begin(), b.begin() + mx);
        sort(id.begin(), id.end());
        long long ans = 0;
        for (int i = 0; i + 3 < mx; i++) {
            for (int j = i + 1; j + 2 < mx; j++) {
                for (int k = j + 1; k + 1 < mx; k++) {
                    for (int l = k + 1; l < mx; l++) {
                        ans = max(ans, 1LL * (a[id[i]] + a[id[k]]) * (a[id[j]] + a[id[l]]));
                    }
                }
            }
        }
        cout << ans << '\n';
    }
}

D.这是一场豪赌

Author: Kros.Mario
Prepared by Kros.Mario & WIDA

知识点：概率dp、博弈论、数论。

预估难度：1900。

【常规解】

设 为在普通游戏中，当前有 个盒子，且轮到当前玩家选择时，当前玩家获胜的概率。 分析普通游戏（无特权）：

若 ，当前玩家获胜概率为 （直接选中礼物）；

若 ，当前玩家获胜概率为 （选中礼物则胜，选中空盒则对方胜）。

若 ，当前玩家有 概率直接获胜。有 概率选中空盒，移除后剩 个盒子，轮到对方。对方获胜概率为 ，则当前玩家在对方回合失败的概率为 。因此 。

通过递推关系可以发现，当 为偶数时，小张获胜概率为 ；当 为奇数时，小张获胜概率为 。

特权阶段是一个蒙特霍尔问题的变种，最优策略是小张先选择一个盒子，小徐移除一个空盒后，小张一定选择换盒子。则：

换盒子后直接获胜：最初选对的概率是 ，选错的概率是 。如果换盒子，获胜的条件是最初选错了，并且从剩下 个盒子中选对了礼物。因此，概率是 。

换盒子后失败：此时概率为 ，场上剩下 个盒子，轮到小樊，特权已用。

通过数学推导和比较，发现当 时使用特权最优， 时保留特权（即不使用特权）最优。对于 和 的情况进行特殊处理。最终，根据 的奇偶性和是否使用特权，推导出小张获胜概率的通项公式。

时间 ；空间 。

【非常规解】

本题规律并不复杂，直接打表观察也是个不错的解决方案。

参考代码 
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
const int mod = 1e9 + 7;

i64 inv(i64 a, i64 b = mod - 2, i64 m = mod) {
    i64 r = 1;
    while (b) {
        if (b & 1) r = (r * a) % m;
        a = (a * a) % m;
        b /= 2;
    }
    return r;
}

int main() {
    i64 n;
    cin >> n;

    if (n == 2) {
        cout << inv(2) << '\n';
    } else if (n % 2) {
        cout << (n + 1) * inv(2 * n % mod) % mod << '\n';
    } else {
        cout << (n * 2 + 3) * inv(4 * n % mod) % mod << '\n';
    }

    return 0;
}

E.小C的等差数列

Author: yxh03
Prepared by yxh03

知识点：思维、构造。

预估难度：2300。

这是个人差异很大的一题，主要的难点在于有没有灵机一动。

对于 为偶数的情况，构造 和 即可；

对于 为奇数的情况，记首项 和公差 ， 和 。

其中一种最短构造方法为，利用 作为公差的倍数，使得乘积的因子可以相互抵消，从而达到乘积相等：选择 、、、，可以构造：

时间 ；空间 。

参考代码 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    long long l = n;
    long long r = n * (1LL << n);
    
    for (int i = 0; i < n; i++) {
        cout << (l + (r - l) / n * i) * 2 << " \n"[i == n - 1];
    }
    for (int i = 1; i <= n; i++) {
        cout << l + (r - l) / n * i << " \n"[i == n];
    }
    return 0;
}

F.最大深度

Author: bandiaoz
Prepared by bandiaoz & glazecat

知识点：可持久化线段树、树形dp、分治。

预估难度：2500。

核心思路是 dfs 遍历树，在遍历过程中维护从根节点到当前节点路径上所有可购买饮料的价格信息。对于每个节点，计算其到达的最小花费。由于购买饮料总是选择价格最低的，因此需要一个数据结构来高效地支持：

插入一个饮料价格；

查询并移除（逻辑上） 个最小价格的饮料并计算其总 。

首先考虑是一条链的情形，按顺序处理，先将价格放入小根堆中，然后按需从栈顶取就是最小 。

注意到这个过程也等价于懒更新线段树单点加一，二分前缀找最少要的数量，求前缀和 ，再将前缀中用到的置零。

回归到树上，我们考虑 dfs 过程，那么向下就等价于前述过程，向上等价于撤销所有修改，采用可持久化线段树或者手动栈式回溯存储更改前的线段树的节点，恢复即可。

这样我们就得到了所有节点的 ，然后再对同层的取个 ，每个询问对 二分求出答案。

时间 ；空间 。

参考代码 
#include <bits/stdc++.h>
using namespace std;

using i64 = int64_t;
using u64 = uint64_t;

constexpr int MAXN = 1e5, N = MAXN + 4, MOD = 998244353, INF = 0x3f3f3f3f, AMX = 1e9;

template<typename T = int> class PST {
    struct info {
        int x = 0;
        int cost = 0;
        void does(int v) {
            ++x;
            cost = min(INF, cost + v);
        }
        int operator-(const info &o) const noexcept {
            return x - o.x;
        }
    };
    struct Node {
        int l, r;
        info data;
    };
    const T LL, RR;
    vector<Node> tr;
    vector<int> tt;
    void ins(T v, int u, T L, T R) {
        tr.push_back(tr[u]);
        tr.back().data.does(v);
        if (L == R) return;
        T mid = L + R >> 1;
        if (v <= mid) {
            tr.back().l = tr.size();
            ins(v, tr[u].l, L, mid);
        } else {
            tr.back().r = tr.size();
            ins(v, tr[u].r, mid + 1, R);
        }
    }
    int dl(int u, T v, T L, T R) {
        tr.push_back(tr[u]);
        if (tr.back().data.x < v) return INF;
        tr.back().data.x -= v;
        if (L == R) {
            tr.back().data.cost = min<i64>(INF, (i64)tr.back().data.x * L);
            return min<i64>(INF, (i64)v * L);
        }
        T mid = L + R >> 1;
        auto &U = tr.back();
        if (tr[tr[u].l].data.x >= v) {
            U.l = tr.size();
            int res = min(INF, dl(tr[u].l, v, L, mid));
            U.data.cost = min(INF, tr[U.l].data.cost + tr[U.r].data.cost);
            return res;
        }
        if (tr[tr[u].l].data.cost > AMX) return INF;
        int res = tr[tr[u].l].data.cost;
        U.l = 0, U.r = tr.size();
        res = min(INF, res + dl(tr[u].r, v - tr[tr[u].l].data.x, mid + 1, R));
        U.data.cost = min(INF, tr[U.l].data.cost + tr[U.r].data.cost);
        return res;
    }

  public:
    PST(int n, T L, T R) : LL(L), RR(R) {
        tt.resize(n + 1);
        tr.reserve(n * (std::__lg(R - L + 1) + 4) + 1);
        tr.resize(1);
    }
    void push(T v, int u, int last) {
        tt[u] = tr.size();
        ins(v, tt[last], LL, RR);
    }
    int del(T v, int u, int last) {
        tt[u] = tr.size();
        return dl(tt[last], v, LL, RR);
    }
};

int X[N], C[N], A;
array<int, 2> Q[N];
vector<int> G[N];
struct S {
    int X, cost, dep;
} cx[N];

void dfs(int u, int f, PST<int> &t, int d = 1) {
    t.push(C[u], u * 2 - 1, f * 2);
    if (cx[f].X >= X[u]) {
        cx[u] = cx[f];
        t.del(0, u * 2, u * 2 - 1);
    } else {
        int z = t.del((X[u] - cx[f].X - 1) / A + 1, u * 2, u * 2 - 1);
        cx[u].cost = cx[f].cost + z;
        if (cx[u].cost > AMX) {
            return;
        }
        cx[u].X = cx[f].X + ((X[u] - cx[f].X - 1) / A + 1) * A;
    }
    cx[u].dep = d++;
    for (auto v : G[u]) {
        if (v != f) {
            dfs(v, u, t, d);
        }
    }
}

signed main() {
    int n, k, q;
    cin >> n >> k >> A;
    for (int i = 1; i <= n; ++i) {
        cin >> X[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> C[i];
    }
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    memset(cx, 0x7f, sizeof cx);
    cx[0] = {k, 0, 0};
    PST<int> t(n * 2, 1, 1e9);
    dfs(1, 0, t);
    
    cin >> q;
    for (int i = 0; i < q; ++i) {
        cin >> Q[i][0], Q[i][1] = i;
    }
    sort(Q, Q + q);
    sort(cx, cx + n + 1, [](const auto &a, const auto &b) -> bool {
        return a.cost < b.cost;
    });
    int ans = 0, now = 0;
    for (int i = 0; i < q; ++i) {
        while (now <= n && cx[now].cost <= Q[i][0]) {
            ans = max(ans, cx[now++].dep);
        }
        Q[i][0] = ans;
    }
    sort(Q, Q + q, [](const auto &a, const auto &b) -> bool {
        return a[1] < b[1];
    });
    for (int i = 0; i < q; ++i) {
        cout << Q[i][0] << '\n';
    }
}

趣闻

内测 B 题人均 WA 三次，最终通过率 17/94。让我们期待一下，谁会成为正赛首个无伤过 B 的选手呢？

组题协调员：WIDA。

出题组：笨蛋少女剑士、西行寺幽幽子、WIDA、ikun_ac、Kros.Mario、yxh03、bandiaoz、glazecat。

审题人：superguymj。

感谢内测同学：

验题组 A（VIP）：撤云、thisislike_fan、ikun_ac、glazecat、StarSilk、Tobo、重生之我要当分子、_fs。

验题组 B：爆炸电台 , Ldh1315109 , 流萤染夏 , Anoth3r , cmy415 , 123hh2 , SherwayLi , convie , KEY.L , DAYXX , wwwwcom , 小七爱英语 , LSU杨楠 ,

验题组 C（AI验题）：WIDA。