竞赛讨论区 > 牛客练习赛 142 题解
头像
Levi_yxc
编辑于 07-12 15:50 广东
+ 关注

牛客练习赛 142 题解

A. 写轮眼

Solution

直接模拟，把整数转化为字符串，然后用 操作把所有 换成 ，再用 转回整数即可。

C++ Code

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        ans -= a;
        auto s = std::to_string(a);
        std::replace(s.begin(), s.end(), '0', '8');
        ans += std::stoi(s);
    }
    std::cout << ans << "\n";
    
    return 0;
}

B. 移植

Solution

对非负整数 做若干次 操作，到最后一定会变成 。

证明如下：

  • 若 ，显然有 ；
  • 若 ，首先有 ，然后回到第一条；
  • 若 ，一定有 ，以及 ，因为 ，，合起来就是 。形式化地，我们构造正项整数数列 ，且首项 为题目给定的 。由于 ，所以一定存在 使得 （），回到第一条。

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

int f(i64 x) {
    return __builtin_popcountll(x);
}
int g(i64 x) {
    return std::__lg(x) - __builtin_popcountll(x) + 2;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    i64 x;
    std::cin >> x;

    std::set<i64> set;
    set.insert(x);

    for (int i = 0; i < 100; i++) {
        x = g(f(x));
        if (set.contains(x)) {
            std::cout << x << "\n";
            return 0;
        }
        set.insert(x);
    }
    std::cout << -1 << "\n";
    
    return 0;
}

C. 战前准备

Solution

题中要求对 都要有 ，那么反着想就是考虑是否存在一个 ，使得 。

我们首先倍增数组 ，得到长度为 的数组 。

从右往左遍历 ，用 记录不满足要求的值 的个数，再用一个数组 记录每个值 的最新出现位置，假设遍历到了下标 ，且并未更新 的最新位置为 ，那么要考虑两种情况。

  • 若 ，那么以 为起点的循环移位数组 就会出现 ，；
  • 若 ，那么以 为起点的循环移位数组 就会出现 ，满足要求，所以应该删掉这个之前不满足、但现在满足要求的值 ，即 。

初始时，， 保持严格逆序，表示一开始所有 都是不满足要求的。

最后只需要统计 且 的下标数量。

时间复杂度

C++ Code

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(n);
    for (auto &x: a) {
        std::cin >> x;
    }
    a.insert(a.end(), a.begin(), a.end());

    std::vector<int> pos(m);
    std::iota(pos.rbegin(), pos.rend(), 2 * n);

    int ans = 0;
    for (int i = 2 * n - 2, cnt = m - 1; i >= 0; i--) {
        int v = a[i];
        if (v > 0 and pos[v - 1] < pos[v]) {
            cnt++;
        }
        if (v + 1 < m and pos[v] > pos[v + 1]) {
            cnt--;
        }
        if (i < n and cnt == 0) {
            ans++;
        }
        pos[v] = i;
    }
    std::cout << ans << "\n";
    
    return 0;
}

D. 第四次忍界大战

Solution

首先，对于 我们特殊计算，只要看 个树边 是否满足 即可。剩下的需要并查集和权值桶维护信息。

首先记录每个权值 对应的结点集合 ，然后从大到小遍历出现过的权值。

对于当前权值 ，设 ，我们遍历 的所有邻居 ，如果 的权值 ，就找到 所在连通块的祖先 ，用 记录 被累加的次数，。

设遍历完所有 后得到的块内祖先集合为 ，对于 ， 表示有 个权值为 的点会加入到连通块 中，而我们只要维护连通块使得块内所有节点的权值都是 的，就能保证这 个结点之间的简单路径都是好路径，这可以利用并查集做到。这样对于 连通块来说，贡献答案 。

时间复杂度

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

struct DSU {
    std::vector<int> f, sz;
    DSU() {}
    DSU(int n) {
        init(n);
    }
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        sz.assign(n, 1);
    }
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    int size(int x) {
        return sz[find(x)];
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        sz[x] += sz[y];
        f[y] = x;
        return true;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> w(n);
    for (auto &x: w) {
        std::cin >> x;
    }
    std::map<int, std::vector<int>> pos;
    for (int i = 0; i < n; i++) {
        pos[w[i]].push_back(i);
    }

    i64 ans = 0;
    std::vector<std::vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
        ans += (w[u] == w[v]) * 2;
    }

    DSU dsu(n);
    std::vector<int> cnt(n);
    std::vector<int> node;
    node.reserve(n);
    for (const auto &[val, p]: pos | std::views::reverse) {
        node.clear();
        for (int x: p) {
            for (int y: adj[x]) {
                if (w[y] <= w[x]) {
                    continue;
                }
                int f = dsu.find(y);
                if (cnt[f]++ == 0) {
                    node.push_back(f);
                }
            }
        }
        for (int x: node) {
            ans += cnt[x] * (cnt[x] - 1LL);
            cnt[x] = 0;
        }
        for (int x: p) {
            for (int y: adj[x]) {
                if (w[y] >= w[x]) {
                    dsu.merge(x, y);
                }
            }
        }
    }
    std::cout << ans << "\n";
    
    return 0;
}

E. 秽土斑（）

首先不考虑跨越 ，设 表示将 分成 段能得到的最大值，且 表示 不选/选 。其状态转移为

然后我们发现，如果要跨越 ，最终的选择只有一段会跨过 ，所以考虑其反面，就是从非环状数组 中选择 段，要求总和最小。

设得到的最小总和为 ，，那么这个情况的答案就是 ，这样就可以转化为：

  • 对 数组全体添负号，求得的最大和。这和上面的 是一样的。

时间复杂度

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 inf = 1E15;

template<typename T>
void chmax(T &a, T b) {
    if (a < b) {
        a = b;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<int> w(n);
    for (auto &x: w) {
        std::cin >> x;
    }

    auto calc = [&]() {
        std::vector dp(m + 1, std::array {0LL, -inf});
        for (int x: w) {
            std::vector ndp(m + 1, std::array {-inf, -inf});
            for (int j = 0; j <= m; j++) {
                ndp[j][0] = std::max(dp[j][0], dp[j][1]);
                if (j > 0) {
                    ndp[j][1] = std::max(dp[j - 1][0], dp[j][1]) + x;
                }
            }
            dp = std::move(ndp);
        }
        i64 ans = 0;
        for (int i = 0; i <= m; i++) {
            chmax(ans, std::max(dp[i][0], dp[i][1]));
        }
        return ans;
    };

    i64 ans = calc();
    for (auto &x: w) {
        x = -x;
    }
    i64 res = calc() - std::accumulate(w.begin(), w.end(), 0LL);

    chmax(ans, res);

    std::cout << std::max(ans, 0LL) << "\n";
    
    return 0;
}

F. 秽土斑（）

Solution

扩大到 时，上述的 肯定行不通了，需要将复杂度控制在单 。

而对于这种至多/恰好选 次物品最大化总价值的问题，如果收益具有凸性，可以考虑 二分。

设 为恰好选择 个不相交子段能获得的最大分数。

简单来说，题目中要求的是 的最大值，其中 属于 段中的一段，现在我们固定一个惩罚 施加于每一段，再转为求 的最大值，这样就变成了无选择次数限制的问题。通过二分 ，我们可以找到一个切点，使得该切点对应的选择次数 接近 。

模仿 中的状态定义，我们定义 为一个 ，表示（在每段的惩罚是 的情况下）将 分成 段能得到的最大值 ，且 表示 不选/选 。其中，若有多种选法可以得到 ，要求 最小。

  • 为了用到 内置的比较函数，我们令 ，即维护段数的相反数。

这样可以得到转移方程如下。

我们二分 ， 返回在当前惩罚下要最大化权值和而选择的最小段数 。

  • 若 ，说明惩罚 可能偏大，可以尝试减小 ；
  • 若 ，说明惩罚 可能偏小，可以尝试增加 。

二分到最优的 ，计算出最大价值 ，最终答案是 ，最后再和 取 。

二分的区间为 。

时间复杂度

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 inf = 1E15;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<int> w(n);
    for (auto &x: w) {
        std::cin >> x;
    }

    auto calc = [&](i64 lam) {
        std::pair dp0 {0LL, 0};
        std::pair dp1 {-inf, 0};
        for (int x: w) {
            auto ndp0 = std::max(dp0, dp1);
            auto ndp1 = std::max(std::pair {dp1.first + x, dp1.second}, std::pair {dp0.first + x - lam, dp0.second - 1});
            std::tie(dp0, dp1) = std::pair {ndp0, ndp1};
        }
        return std::max(dp0, dp1);
    };

    i64 tot = std::accumulate(w.begin(), w.end(), 0LL);

    auto search = [&]() {
        i64 lo = -1;
        i64 hi = 0;
        for (int x: w) {
            hi += std::max(x, 0);
        }
        while (lo + 1 < hi) {
            i64 mid = (lo + hi) >> 1;
            (-calc(mid).second <= m ? hi: lo) = mid;
        }
        auto [val, cnt] = calc(hi);
        return val + hi * m;
    };

    i64 ans = search();
    for (int &x: w) {
        x = -x;
    }
    i64 res = search() + tot;
    if (ans < res) {
        ans = res;
    }
    
    std::cout << std::max(ans, 0LL) << "\n";
    
    return 0;
}

G. 秽土转生解

Solution

首先用树状数组求出排列 的逆序对，设为 。

然后通过逆序对 贪心构建字典序最小排列 。

  • 贪心的策略是：设当前枚举到 ，且经过前面的构造，总的逆序对剩下 ，当前可以放置的下标区间为 ；如果后 个数完全逆序的逆序对数 ，那么就把 放到 ，然后 ，否则就把 放到 ，然后 。
  • 这样贪心正确的原因是【逆序对数组的字典序越小，原排列字典序越小】。

若 ，则输出。

否则要找到字典序恰好 的排列 ，使得 。

这可以通过逆序对数组来找。

设 表示 后面有多少个数 ， 表示 的后缀和。

我们只要找到下一个字典序更大的 即可，这是因为【逆序对数组 字典序越大，原排列字典序越大】。

这可以 寻找，即从后往前找到第一个可以使得 增大的下标 ，此时一定满足

接着不断往后按照构造字典序最小逆序对的方式贪心即可。

最后通过树状数组求第 大还原这个 对应的排列。

如果找不到 则输出 。

时间复杂度

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

template<class T>
struct Fenwick {
    int n;
    std::vector<T> a;
    Fenwick(int _n = 0) {
        init(_n);
    }
    void init(int _n) {
        n = _n;
        a.assign(n, T{});
    }
    int lowbit(int x) {
        return x & -x;
    }
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += lowbit(i)) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    void clear() {
        a.assign(n, T{});
    }
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= lowbit(i)) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    T sum(int l, int r) {
        return sum(r) - sum(l);
    }
    int kth(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n and cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

template<class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    os << v[0] + 1;
    for (size_t i = 1; i < v.size(); i++) {
        os << " " << v[i] + 1;
    }
    return os;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> p(n);
    for (auto &x: p) {
        std::cin >> x;
        x--;
    }

    Fenwick<int> fen(n);
    std::vector<int> inv(n);
    for (int i = n - 1; i >= 0; i--) {
        inv[i] = fen.sum(p[i]);
        fen.add(p[i], 1);
    }

    i64 tot = std::accumulate(inv.begin(), inv.end(), 0LL);

    std::vector<int> q(n);
    for (int i = 1, l = 0, r = n; i <= n; i++) {
        i64 s = (n - i) * (n - i - 1LL) / 2;
        if (tot <= s) {
            q[l++] = i - 1;
        } else {
            tot -= n - i;
            q[--r] = i - 1;
        }
    }

    if (p != q) {
        std::cout << q << "\n";
        return 0;
    }

    std::vector<i64> suf(n + 1);
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = suf[i + 1] + inv[i];
    }

    std::vector<int> ninv;
    for (int i = n - 1; i >= 0; i--) {
        i64 lo = std::max<i64>(inv[i] + 1, suf[i] - (n - i - 1LL) * (n - i - 2) / 2);
        i64 hi = std::min<i64>(suf[i], n - i - 1);
        if (lo > hi) {
            continue;
        }
        ninv = std::move(inv);
        ninv[i] = lo;
        i64 have = suf[i] - lo;
        for (int j = i + 1; j < n; j++) {
            i64 need = std::max(0LL, have - (n - j - 1LL) * (n - j - 2) / 2);
            ninv[j] = need;
            have -= need;
        }
        break;
    }

    if (ninv.empty()) {
        std::cout << -1 << "\n";
        return 0;
    }

    std::vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        ans[i] = fen.kth(ninv[i]);
        fen.add(ans[i], -1);
    }

    std::cout << ans << "\n";

    return 0;
}
2026最新求职资料大礼包领取
真题
历年笔试真题附答案
2023年游卡秋招研发岗笔试
【2020】自如秋招产品经理-B卷
字节跳动春招研发部分编程题汇总
全部 >
面经
面试常考问题整理
0928携程笔试题解
2022考研失败春招选手的群面攻略（适用于菜鸡互啄型）
腾讯三面已上岸
全部 >
内推
员工内推码获取
同花顺26届校招提前批内推
拼多多技术岗26届秋招速推
2026上海米哈游内推-7.31开启
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(13) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”