官方题解|巅峰赛23

hopebetter

2025-07-21 12:09:09

发布于：浙江

236阅读

0回复

0点赞

赛纲介绍

本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目名称	题目难度
T1	奇怪的数组	入门
T2	取与得	普及-
T3	机器人Ⅰ	普及-
T4	下凸子数组	普及/提高-
T5	最短路	普及+/提高
T6	机器人	普及+/提高

奇怪的数组

题目大意

现在你存在一种操作，让数组中的两个位置 $i$ , $j$ ,让第 $i$ 个数 $-1$ , 第 $j$ 个数 $+1$ 。求最少可以通过多少次操作可以让数组中的每一个数相同。

题解思路

经过一次操作，数组中的数的总和不变，如果数组中的每一个数最终相同， $\sum^n_{i=1} a_i \mod n =0$ ,因此我们确认这个数是否可行就可以了。最小次数我们只需要考虑比平均值大的数与平均数的差的和是多少。

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
using i128 = __int128;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<i64> arr(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    i64 sums = 0;
    for (int i = 1; i <= n; i++) {
        sums += arr[i];
    }
    if (sums % n != 0) {
        cout << -1 << endl;
    } else {
        i64 ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += max(arr[i] - (sums / n), 0ll);
        }
        cout << ans << endl;
    }
}

取与得

题目大意

你可以任意删除并且重新排列原数组，让生成的数组的总权值最大。

题解思路

大的数一定放在前面。
在数组后面添加一个数，本质上总权值加上数组前面一段数的和。

因此本题在排序完进行两次前缀和后找到数组中的最大值即可

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
using i128 = __int128;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<i64> arr(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin() + 1, arr.end() ,greater<i64>());
    vector<i64> pre(n + 1);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + arr[i];
    }
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + pre[i];
    }
    i64 ms = -1e18;
    for (int i = 1; i <= n; i++) {
        ms = max(pre[i], ms);
    }
    cout << ms << endl;
}

机器人Ⅰ

题目大意

现在机器人有一种移动方式，问机器人从某一个起点到达 $l_i$ $r_i$ 位置。

题解思路

问题 $1$ 我们现在机器人从 $p_0$ 开始,走了一圈到达 $p_1$ ，那么 $p_1$ 的位置会在哪里？
我们设白色节点的数目为 $t$ ,那么我们可以到达 $(p_0 + t) \mod n$ 位置。因为这次的移动，本质上是相当与 $robot$ 顺时针走了 $t$ 步。

问题 $2$ 现在我们机器人最终到达了 $l_j , r_j$ ,那么对于 $l_j 和 r_j$ 有什么限制?
其中一个节点应该是最后一步走到的，我们设最后一步走的是顺时针，那么 $r_j$ , 这个点似乎就相当于未生效。这样我们可以找到这一圈的起始点 $p_1$ 。
只后，我们可以从 $p_1$ 开始模拟，机器人是否可以到底 $l_j, r_j$ 。

时间复杂度 O( $n \times m$ )

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
int vis[3002];

int dis(int f, int to, int n, int t) {
    memset(vis, 0, sizeof vis);
    int now = 0;
    int x = 3002;
    while (f != to && x--) {
        f = (f + t) % n;
        now += n;
    }
    if (x <= 0) return -1;
    return now;
}

pair<int, int> run(int l, int r, int L, int R, int n, string &s) {
    int p = l;
    if (l != r) {
        int k = 0;
        int l_t = l;
        while (l_t != r) {
            if (s[l_t] == '0') k++;
            l_t = (l_t + 1) % n;
        }
        if (s[l_t] == '0') k++;
        p = (L + k) % n;
    }
    l = r = p;
    int step = n;
    int tt = 0;
    int las = l;

    while (step--) {
        if (l == L && r == R) {
            return {p, tt};
        }
        if (s[las] == '1') {
            r++;
            r %= n;
            las = r;
        } else {
            l--;
            l = (l + n) % n;
            las = l;
        }
        tt++;
    }
    return {-1, -1};
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    int t = 0;
    for (auto i: s) if (i == '1') t++;


    for (int i = 1; i <= m; i++) {
        int p_i, l_i, r_i;
        cin >> p_i >> l_i >> r_i;
        p_i--, l_i--, r_i--;
        if (l_i == r_i) {
            cout << dis(p_i, l_i, n, t) << endl;
        } else {
            //最后一步是向左走
            auto [pp,tt] = run((l_i + 1) % n, r_i, l_i, r_i, n, s);
            int z = -1;
            if (pp != -1) {
                int dis2 = dis(p_i, pp, n, t);
                if (dis2 != -1) {
                    z = dis2 + tt;
                }
            }
            auto [pp1,tt1] = run((l_i) % n, (r_i - 1 + n) % n, l_i, r_i, n, s);
            if (pp1 != -1) {
                int dis2 = dis(p_i, pp1, n, t);
                if (dis2 != -1) {
                    if (z == -1) {
                        z = dis2 + tt1;
                    } else {
                        z = min(z, dis2 + tt1);
                    }
                }
            }
            cout << z << endl;
        }
    }
}

下凸子数组

题目大意

现在需要我们生成一个单调递增的数组，并且数组的增量单调不降，数组的首项为1，末尾为 $k$ 。

题解思路

我们设增量为 $d_i$ , 问题可以转化为存在多少种不同的数组，使得 $\sum^p_{i=1}{d_i} = k-1$ ，问题可以转换为一个完全背包问题。

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
using i128 = __int128;

namespace myMath {
    i64 mod = 998244353;

    i64 add(i64 x, i64 y) {
        x += y;
        if (x > mod) x -= mod;
        return x;
    }

    i64 sub(i64 x, i64 y) {
        x -= y;
        if (x < 0)x += mod;
        return x;
    }

    i64 mul(i64 x, i64 y) {
        x *= y;
        x -= x / mod * mod;
        return x;
    }

    i64 qpow(i64 x, i64 y) {
        i64 res = 1;
        while (y) {
            if (y & 1) res = mul(res, x);
            y >>= 1;
            x = mul(x, x);
        }
        return res;
    }

    i64 inv(i64 x) {
        return qpow(x, mod - 2);
    }

    i64 qdiv(i64 x, i64 y) {
        return mul(x, inv(y));
    }

    void set_mod(i64 x) {
        mod = x;
    }

    namespace Comb {
        int n;
        vector<i64> fa;
        vector<i64> ifa;

        void init(int _n) {
            n = _n;
            fa.assign(n + 1, 1), ifa.assign(n + 1, 1);
            for (int i = 1; i <= n; i++) fa[i] = mul(fa[i - 1], i);
            ifa[n] = inv(fa[n]);
            for (i64 i = n - 1; i; i--) {
                ifa[i] = mul(ifa[i + 1], i + 1);
            }
        }

        i64 C(int i, int j) {
            return mul(fa[i], mul(ifa[j], ifa[i - j]));
        }
    }

    //线性求逆元

    vector<i64> get_inv(int k) {
        vector<i64> in(k + 1, 1);
        for (int i = 2; i <= k; i++) {
            in[i] = mul(in[mod % i], sub(mod, mod / i));
        }
        return in;
    }
}

using namespace myMath;


int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    vector<i64> f(5000 ,0 );
    f[0] = 1;
    for (int i = 1; i <= 5000; i++) {
        for (int j = i ; j <= 5000; j++) {
            f[j] = add(f[j], f[j - i]);
        }
    }

    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        int x;
        cin >> x;
        cout << f[x - 1 ] << endl;
    }
}

最短路

题目大意

存在 $n$ 个节点， $m$ 次操作，每次操作或者查询两个节点之间的距离，或者删除一个节点，并且删除一个点，并让其邻域的点两两之间连上一条边。

题解思路

题目分析

我们可以将删除操作的本质理解为：对于所有经过该节点的最短路径，其距离长度将减少 $1$ 。基于这一观察，可以将问题转化为以下形式：

初始状态下，所有节点的权值均为 $1$ 。操作1对应将指定节点的权值修改为 $0$ ，而操作2则转化为查询两个节点之间最短路径上权值为 $1$ 的节点数量。

这种转化使得问题可以通过树链剖分技术高效解决。具体而言，我们可以：

建立树链剖分数据结构来维护节点权值
实现单点修改操作（将节点权值从1改为0）
通过路径查询统计两个节点间最短路径上权值为1的节点数量

时间复杂度 O( $n\log^2 n$ )

参考代码

#include <bits/stdc++.h>
using namespace std;

class Tree {
    int n;
    vector<int> dfn, top, fa, son, sz, dep, ys;
    vector<vector<int> > edge;
    vector<int> fiw;
    int tot = 0;

public:
    int lowbit(int x) {
        return x & -x;
    }

    void modify(int x, int y) {
        while (x <= n) {
            fiw[x] += y;
            x += lowbit(x);
        }
    }

    int query(int x) {
        int sums = 0;
        while (x) {
            sums += fiw[x];
            x -= lowbit(x);
        }
        return sums;
    }

    int sum(int l, int r) {
        return query(r) - query(l - 1);
    }

    Tree(int n) : dfn(n + 1), top(n + 1), fa(n + 1), son(n + 1), sz(n + 1), dep(n + 1), ys(n + 1), fiw(n + 1, 1),
                  edge(n + 1), n(n) {
        for (int i = 1; i <= n; i++) {
            if (i + lowbit(i) <= n) fiw[i + lowbit(i)] += fiw[i];
        }
    }

    void add_edge(int x, int y) {
        edge[x].emplace_back(y);
        edge[y].emplace_back(x);
    }

    void dfs1(int u, int p) {
        sz[u] = 1;
        fa[u] = p;
        dep[u] = dep[p] + 1;
        for (auto i: edge[u]) {
            if (i == p) continue;
            dfs1(i, u);
            sz[u] += sz[i];
            if (sz[son[u]] < sz[i]) son[u] = i;
        }
    }

    void dfs2(int u, int t) {
        dfn[u] = ++tot;
        ys[tot] = u;
        top[u] = t;
        if (son[u]) {
            dfs2(son[u], t);
        }
        for (auto i: edge[u]) {
            if (i == fa[u] || i == son[u])continue;
            dfs2(i, i);
        }
    }

    void init() {
        dfs1(1, 0);
        dfs2(1, 1);
    }

    void delete_node(int q) {
        modify(dfn[q], -1);
    }

    int lca(int u, int v) {
        int _sums = 0;
        while (top[u] != top[v]) {
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            _sums += sum(dfn[top[u]], dfn[u]);
            u = fa[top[u]];
        }
        if (dep[u] > dep[v]) swap(u, v);
        _sums += sum(dfn[u], dfn[v]);
        return _sums;
    }
};

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    Tree tree(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree.add_edge(u, v);
    }
    tree.init();
    for (int i = 1; i <= m; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            tree.delete_node(x);
        } else {
            int u, v;
            cin >> u >> v;
            cout << tree.lca(u, v) - 1 << endl;
        }
    }
}

机器人

题目大意

现在机器人有一种移动方式，问机器人从某一个起点到达 $l_i$ $r_i$ 位置。

题解思路

思考一 $n$ 个点, $n$ 条边的图是什么图？很明显这是一个基环树。这样我们在求解距离的时候似乎可以转换为环上的两点之间的距离，这样通过一系列离线的操作，可以在 O(n)的时间下求出来。

思考二现在我们从 $p_0$ 出发，走到 $l_i, r_i$ ,这会有什么性质，

首先出去最后一次移动到的位置，其他的位置都产生了相应的影响。这样我们可以找到开始位置 $p_1$
还有没有其他性质？设最后一步是向右走，那么 $l_i$ 位置一定是白色的。最后一步是向左走 $r_i$ 的位置一定是黑色。
$l_i \sim p_1$ 这个位置每一个向右的位置相当于一次转向。在 $p_i \sim r_i$ 的位置也是类似。那这个有什么性质呢？我们定 $p_i$ 有一个初始方向 $a_0$ ,结束的方向为 $a_1$ ,如果两个方向相反，那么可以说明左区间的右转向和右区间的左转向数目相同。如果两个方向相同，最终向右走，那么左区间的右转向比右区间的左转向多一个，向左走也类似。

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
#ifndef ONLINE_JUDGE
#include "test.h"
#else
#define debug(...) 42
#define debug_assert(...) 42

#endif
i64 dis1(int l, int r, int n, vector<pair<i64, i64> > &mp, vector<vector<i64> > &node) {
    if (l >= n) l -= n;
    if (r >= n) r -= n;
    if (mp[l].first != mp[r].first) return -1;
    i64 ll = mp[l].second, rr = mp[r].second;
    if (ll > rr) {
        ll -= node[mp[l].first].size();
    }
    return (rr - ll) * n;
}

i64 get_w(int l, int r, vector<i64> &w) {
    if (l > r) return 0;
    if (l == 0) return w[r];
    return w[r] - w[l - 1];
};

i64 get_b(int l, int r, vector<i64> &b) {
    if (l > r) return 0;
    if (l == 0) return b[r];
    return b[r] - b[l - 1];
};

i64 get(int l, int r, int tp, vector<i64> &w, vector<i64> &b) {
    if (tp == 1) {
        return r - get_w(l, r, w) + 1;
    }
    return l + get_b(l, r, b) - 1;
};

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    i64 n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    s += s;
    vector<i64> w(2 * n + 10), b(n * 2 + 100);
    for (i64 i = 0; i < n; i++) {
        if (s[i] == '1') {
            w[i]++;
            w[i + n]++;
        } else {
            b[i]++;
            b[i + n]++;
        }
    }
    for (i64 i = 1; i <= 2 * n; i++) {
        w[i] += w[i - 1];
        b[i] += b[i - 1];
    }

    i64 t = w[n - 1];
    vector<vector<i64> > node(n + 1);
    vector<pair<i64, i64> > mp(n + 1);
    vector<i64> vis(n + 1);
    i64 tt = 0;
    for (i64 i = 0; i < n; i++) {
        if (vis[i]) continue;
        i64 tmp = i;
        while (!vis[tmp]) {
            vis[tmp] = 1;
            node[tt].emplace_back(tmp);
            mp[tmp] = {tt, node[tt].size()};
            tmp = (tmp + t) % n;
        }
        tt++;
    }
    debug(node);
    for (int i = 1; i <= m; i++) {
        int p_j, l_j, r_j;
        cin >> p_j >> l_j >> r_j;
        p_j--, l_j--, r_j--;
        if (l_j > r_j) r_j += n;
        if (l_j == r_j) {
            cout << dis1(p_j, l_j, n, mp, node) << endl;
        } else {
            i64 ans = -1;
            i64 p1 = get(l_j, r_j, 1, w, b);

            if (get_b(p1, r_j, b) == get_w(l_j, p1 - 1, w) && s[l_j] == '1') {
                i64 dd = dis1(p_j, p1, n, mp, node);
                if (dd != -1) {
                    ans = dd + r_j - l_j;
                }
            }
            int p2 = get(l_j, r_j, 0, w, b);
            if (get_b(p2 + 1, r_j, b) == get_w(l_j, p2, w) && s[r_j] == '0') {
                i64 dd = dis1(p_j, p2, n, mp, node);
                if (dd != -1) {
                    if (ans == -1) {
                        ans = dd + r_j - l_j;
                    } else {
                        ans = min(dd + r_j - l_j, ans);
                    }
                }
            }
            cout << ans << endl;
        }
    }
    //
}

有帮助，赞一个

去预览

0/2000

全部评论 7

复仇者_帅童
老师树链剖分不是蓝吗

1周前来自湖南
2
- dream_陆军展览
  回复复仇者_帅童
  zc
  
  1周前来自江苏
  0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复复仇者_帅童
  是紫
  
  1周前来自上海
  1
- 复仇者_帅童
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  ？你咋看的
  
  1周前来自湖南
  0
༺ཌༀཉི༒白·羊༒༃ༀད༻
T5暴力+快读快写95分

1周前来自上海
1
- 复仇者_帅童
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  我在审核的过程中，发现了一个时间复杂度 $O(n^2)$ 的代码，里面本应用树链剖分求 LCA 的部分被替换成了暴力跳求 LCA，但是他依然通过了该题。
  
  1周前来自湖南
  0
AAA混泥土批发ppl哥
依旧码风清奇

1周前来自浙江
0
- AAA混泥土批发ppl哥
  回复AAA混泥土批发ppl哥
  老师后面几题的代码是不是忘了格式化，为什么要空一格？还是不是在 IDE 里遍的？
  
  1周前来自浙江
  0
- hopebetter
  回复AAA混泥土批发ppl哥
  排版问题
  
  1周前来自浙江
  0
AAA水泥批發白哥
%%%%%%%%%%%%%%%%%%%

1周前来自北京
0
AAA水泥批發白哥
好吧T5真和我猜的一样（可惜我没打）

1周前来自北京
0
复仇者_帅童

1周前来自湖南
0
Welcome24ever

1周前来自浙江
0