官方题解 | 巅峰赛24题解

hopebetter

2025-08-18 10:24:35

发布于：浙江

313阅读

0回复

0点赞

赛纲介绍

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

题目编号	题目名称	题目难度
T1	压缩字符串	入门
T2	汉明距离Ⅰ	入门
T3	拼图	普及-
T4	汉明距离	普及/提高-
T5	导线	普及/提高-
T6	打工	普及+/提高

T1

模拟

题目大意

按照题意模拟，判断两个相邻的字符是否是相同的

题解思路

每次输入一个字符压缩，判断和之前的字符压缩的字符是否是一样的。

复杂度分析

$O(n)$

参考代码

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

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int k;
    cin >> k;
    char a = ' ';
    int _;
    for (int i = 1; i <= k; i++) {
        char t;
        int __;
        cin >> t >> __;
        if (t == a) {
            cout << "No" << endl;
            return 0;
        }
        a = t, _ = __;
    }
    cout << "Yes" << endl;
}

T2

模拟

题目大意

汉明距离代表两个数二进制位的不同的位置的数目。我们需要计算所有的 ( $x, y$ ),( $0 \le x<y\le n$ ), $x,y$ 之间汉明距离的和

题解思路

对于每一个 $n$ ，直接枚举所有可能的 ( $x, y$ ),( $0 \le x<y\le n$ )。对于每一对之间计算他们的汉明距离的和即可。

复杂度分析

O( $t\times n^2 \log V$ )

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
 
const int INF = 1e18 + 10;
const int N = 200010, M = 1000010;
const int mod = 998244353;
 

bool check(int a, int b,int k) {
    int res = 0;
    for (int i = 0; i <= 30; i++) {
        if (((a >> i) & 1) != ((b >> i) & 1)) res++;
    }
    return res <= k;
}

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


    int res = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (check(i, j, k)) res++;
        }
    }
    cout << res << endl;
}

signed main() {
    //init();//Prime();
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

T3

模拟

题目大意

现在我们有两种矩形，分别为 $1\times 4$ 与 $2\times 3$ 的矩形，矩形可以任意选择，问，能否拼成 $n \times m$ 的矩形。

题解思路

生成矩形的面积有什么性质。应该为偶数,接下来我们考虑 n , m 的取值；

我们定义 $n \le m$

当 $n = 1$ 时， $m$ 应该满足是 $4$ 的倍数。 (情况1)
当 $n = 2$ 时，我们注意到 $m \ge 6$ 时，所有的数都可以转换为 $a \times 4 + b\times 3$ 。那么我们考虑 $m = 2,3,4,5$
的情况，其中 $m=2,m=5$ 两个情况不可以。 (情况2)
当 $n= 3$ 时，因为 $n \times m$ 是偶数， $m$ 是偶数。一定可以。 (情况3)
当 $n \mod 4 = 0$ 时，可以用 $1\times 4$ 的拼出。 (情况4)
当 $n \ge 6 且 n \mod 4 =2$ ， $m \ge 6$ ， $n = 4 \times a + 2$ 可以将图变成情况4 和情况 2 的组合，一定可以。
当 $n\ge 5 且 n \mod 2 =1$ ， $m$ 是偶数 , $m \ge 6$ ， $n = 2 \times a +3$ ,可以将图变成情况3 和情况 2 的组合，一定可以。

复杂度分析

$O(t)$

参考代码

#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

void solve() {
    int n, m;
    cin >> n >> m;
    if (n > m) swap(n, m);
    if (n * m % 2 == 1) {
        cout << "No" << endl;
    } else if (n == 1) {
        if (m % 4 == 0) {
            cout << "Yes" << endl;
        } else cout << "No" << endl;
    } else if (n == 2) {
        if (m == 2 || m == 5) cout << "No" << endl;
        else cout << "Yes" << endl;
    } else {
        cout << "Yes" << endl;
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

T4

组合数,dp

题目大意

题解思路

我们定义 $f[i][j]$ 为小于等于 $i$ 的数中，与 $i$ 相差位数为 $j$ 的情况数。我们设 $i$ 二进制位数为 $t$ 位，我们可以将小于 $i$ 的数看做是两类，

第 $t$ 位不为 $1$ ,那么前 $t-1$ 位如何选择这个数都比 $i$ 小，那么就可以在（ $t- 1$ ）位中选择 $k-1$ 位作为不同的位置。
第 $t$ 位为 $1$ , 那么第 $t$ 位相同，需要在前 $t -1$ 位找到 $k$ 位不同，且小于 $i$ 的数，起值等于 f[i - (1 << t)][j]

之后进行前缀和操作统计相应的答案。

复杂度分析

$O(n \log n )$

参考代码

#include "bits/stdc++.h"

using namespace std;

#ifndef ONLINE_JUDGE
#include "test.h"
#else
#define debug(...) 42
#define debug_assert(...) 42
#endif


#define IOS ios::sync_with_stdio(0),cin.tie(0)

using ll = long long;
using ull = unsigned long long;

#define endl '\n'
#define int ll

using VI = vector<int>;
using VII = vector<VI>;
using PII = pair<int, int>;
const int inf = 1e18;
const int mod = 998244353;
// #define  lowbit(x) (x&(-x))
const int maxn = 1e6 + 7;

int qpow(int a, int b) {
    int ans = 1;
    while (b) {
        // debug(b);
        if (b & 1) {
            ans *= a;
            ans %= mod;
        }
        a *= a;
        a %= mod;
        b /= 2;
    }
    return ans;
}

vector<int> fac;
vector<int> infac;
//vector<vector<int>> f;
int f[maxn][21];
int C(int n, int m) {
    if (n - m < 0) return 0;
    if (m == 0 || n == 0 || m - n == 0)return 1;
    return fac[n] * infac[m] % mod * infac[n - m] % mod;
}

void init() {
    fac.resize(maxn);
    infac.resize(maxn);
    //    f.resize(maxn, vector<int>(21));
    fac[0] = 1;
    for (int i = 1; i < maxn; i++) {
        fac[i] = i * fac[i - 1];
        fac[i] %= mod;
    }
    infac[0] = 1;
    infac[maxn - 1] = qpow(fac[maxn - 1], mod - 2);
    for (int i = maxn - 2; i; i--) {
        infac[i] = (i + 1) * infac[i + 1];
        infac[i] %= mod;
    }
    int k = 21;

    f[0][0] = 1;
    int maxs = 1;
    // int sums = 0;
    for (int i = 1; i < maxn; i++) {
        if ((1 << maxs) <= i) {
            maxs++;
        }
        f[i][0] = 1;
        int jj = (i - (1 << (maxs - 1)));
        for (int j = 1; j < k; j++) {
            f[i][j] = C(maxs - 1, j - 1) + f[jj][j];
            // sums += f[i][j];
        }
    }
    for (int i = 1; i < maxn; i++) {
        for (int j = 2; j < k; j++) {
            f[i][j] += f[i][j - 1];
        }
    }
    for (int i = 2; i < maxn; i++) {
        for (int j = 1; j < k; j++) {
            f[i][j] += f[i - 1][j];
            f[i][j] %= mod;
        }
    }
}


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

    cout << f[n][k] << endl;
}

signed main() {
    IOS;
    init();
    // debug(1);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

T5

题目大意

有 $n$ 个水平线段和 $m$ 个垂直线段，每个线都有一个颜色，开始横竖导线之间是绝缘的，你可以执行如下的操作，让一次横着的导线和竖着的导线之间导电，问最少经过多少次操作，相同颜色的线缆之间会导电。问最少经过多少次操作，会让所有的的颜色想相同的导线之间导电，在最少的操作次数下，有多少种可能的操作方法。

题解思路

问题一：单色焊接

问题描述：
有 $n$ 个水平线段和 $m$ 个垂直线段，所有线段颜色相同。需要多少次焊接才能将所有线段连接成一个整体？有多少种不同的焊接方案？

分析：

焊接次数：

每次焊接可以连接一个水平线段和一个垂直线段。初始时有 $n$ 个水平线段和 $m$ 个垂直线段，最终需要连接成一个整体（即 1 个连通块）。
每次焊接减少 1 个独立线段（因为焊接是将两个线段连接，相当于减少 1 个独立单位）。
初始独立线段数为 $n + m$ ，最终为 1，因此需要 $(n + m) - 1 = n + m - 1$ 次焊接。

焊接方案数：

焊接顺序可以建模为一个路径问题：从 $(0, 0)$ 到 $(n, m)$ ，每次选择焊接一个水平线段（向右走）或一个垂直线段（向上走）。
总步数为 $n + m$ ，其中 $n$ 步向右， $m$ 步向上。
因此方案数为组合数 $\binom{n + m}{n}$ 。
但焊接是从第一个焊接开始的，所以实际路径是从 $(1, 1)$ 到 $(n, m)$ ，步数为 $(n - 1) + (m - 1) = n + m - 2$ ，方向为 $n - 1$ 右和 $m - 1$ 上。
因此方案数为 $\binom{n + m - 2}{n - 1}$ 。

结论：

焊接次数： $n + m - 1$ 次。
方案数： $\binom{n + m - 2}{n - 1}$ 。

问题二：双色焊接

问题描述：
现在有两种颜色的线段（颜色 $a$ 和 $b$ ）：

颜色 $a$ 的覆盖范围为左上角 $(x_1, y_1)$ 到右下角 $(x_2, y_2)$ 。
颜色 $b$ 的覆盖范围为左上角 $(x_3, y_3)$ 到右下角 $(x_4, y_4)$ 。
需要将两种颜色的线段分别连通。问如何焊接？如果两种颜色的范围有重叠，如何处理？

分析：

无重叠情况：

如果颜色 $a$ 和 $b$ 的矩形区域不重叠（即 $x_2 < x_3$ 或 $x_4 < x_1$ 或 $y_2 < y_3$ 或 $y_4 < y_1$ ），则可以完全独立处理。
分别对颜色 $a$ 和 $b$ 使用问题一的思路。

有重叠情况：

如果颜色 $a$ 和 $b$ 的矩形区域重叠，那么他们的焊接路径一定会有冲突。那么我们可以将两个颜色当成一个颜色，这样就可以多通过一次操作避免冲突。

因此本题就是看不同颜色的区间范围是否存在冲突，存在冲突的点则当成一个颜色来连接。

复杂度分析

O（ $\max(n,m)$ ）

参考代码

#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

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);
    int n, m;
    Comb::init(4e6);
    cin >> n >> m;
    vector<int> cx(n + 1), cy(m + 1);
    vector<int> fx(1e6 + 1, 1e9), tx(1e6 + 1, 1e9), fy(1e6 + 1), ty(1e6 + 1);
    for (int i = 1; i <= n; i++) {
        cin >> cx[i];
        fx[cx[i]] = min(i, fx[cx[i]]);
        tx[cx[i]] = i;
    }
    for (int i = 1; i <= m; i++) {
        cin >> cy[i];
        fy[cy[i]] = min(fy[cy[i]], i);
        ty[cy[i]] = i;
    }
    auto run = [&]() -> pair<i64, i64> {
        int i = 1, j = 1;
        i64 t = 0, sums = 1;
        while (i <= n && j <= m) {
            int fxx = i, txx = max(tx[cx[i]], tx[cy[j]]);
            int fyy = j, tyy = max(ty[cx[i]], ty[cy[j]]);
            int a = 0, b = 0;
            while (i < txx || j < tyy) {
                while (i < txx) {
                    a++;
                    i++;
                    txx = max(tx[cx[i]], txx);
                    tyy = max(ty[cx[i]], tyy);
                }
                while (j < tyy) {
                    b++;
                    j++;
                    txx = max(txx, tx[cy[j]]);
                    tyy = max(tyy, ty[cy[j]]);
                }
            }
            t += a + b + 1;
            sums = mul(sums, Comb::C(a + b, a));
            i++, j++;
        }
        return {t, sums};
    };
    auto [a , b] = run();

    cout << a << "\n" << b << endl;
}

T6

虚树

题目大意

现在有一颗树，树上有一些节点，我们可以待在某个节点一段时间 $t_i$ ，最终赚得一定的钱数 $p_i$ ，同时在一条边上移动会花费1个单位时间，求在一个定时间 $w_i$ 最多会赚多少钱。

题解思路

问题一

当树的节点比较小的时候，我们可以通过什么方法来解决这个问题。
很明显我们可以通过一个背包来解决这个问题。
在树上我们根据花费多少模拟背包操作，之后将背包中的信息整合，对父节点进行背包操作。
但是节点数似乎很多，直接背包容易tle，

优化

现在树上一共有 $n$ 个点,在这 $n$ 个节点上进行背包 $dp$ ,维护会发生超时，那么我们可以怎么做呢？首先，我们发现可以赚钱的节点很少 $m$ ，我们沿着这些节点往上走，我们发现，最多会有 $m$ 次相遇，也就意味着，不同的背包最多合并 $m$ 次。那么我们是否只要在这些需要合并的点上进行记录就可以了？
我们叫这些合并的点叫做虚点。
这些虚点我们可以通过 $lca$ 求得。

关于求 $lca$ 可以实现树剖或者倍增预处理并实现，之后在新树上进行dp

复杂度分析

O( $n + m\log n + m\times W^2$ )

参考代码


 #include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ull = unsigned long long;

#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define endl "\n"
#define int ll

//点 工作 总时间
const int maxn = 5e5+10;
int n, m, w;
vector<int> mp[maxn];
unordered_map<int, int> tim;
unordered_map<int, int> we;
int fa[maxn], top[maxn], son[maxn], dfn[maxn], dep[maxn], siz[maxn];
int tot = 1;
vector<array<int, 3> > v;
set<int> mp2[maxn];

void dfs1(int now) {
    siz[now] = 1;
    for (auto c: mp[now]) {
        dep[c] = dep[now] + 1;
        dfs1(c);
        siz[now] += siz[c];

        if (siz[c] > son[siz[now]]) {
            son[now] = c;
        }
    }
}

void dfs2(int now) {
    dfn[now] = tot++;
    if (son[fa[now]] == now) {
        top[now] = top[fa[now]];
    } else {
        top[now] = now;
    }
    if (son[now]) {
        dfs2(son[now]);
    }
    for (auto i: mp[now]) {
        if (i == son[now])continue;
        dfs2(i);
    }
}

int lca(int p,int q) {
    while (top[q] != top[p]) {
        //            cerr<<dep[top[q]]<<" "<<dep[top[p]]<<endl;
        if (dep[top[q]] < dep[top[p]])
            swap(q, p);
        q = fa[top[q]];
    }
    if (dep[q] < dep[p])swap(q, p);
    return p;
}

int cost(int u,int v) {
    return 2 * abs(dep[u] - dep[v]);
}

void build_virtual_tree() {
    sort(v.begin(), v.end(), [&](array<int, 3> a, array<int, 3> b) {
        return dfn[a[0]] < dfn[b[0]];
    });
    vector<int> a;
    for (int i = 0; i < m; ++i) {
        a.emplace_back(v[i][0]);
        a.emplace_back(lca(v[i][0], v[i + 1][0]));
    }
    a.emplace_back(v[m][0]);
    sort(a.begin(), a.end(), [&](int a1, int b1) {
        return dfn[a1] < dfn[b1];
    });
    int sizs = a.size();
    for (int i = 0; i < sizs - 1; i++) {
        int lc = lca(a[i], a[i + 1]);
        if (lc == a[i + 1])continue;
        mp2[lc].emplace(a[i + 1]);
        mp2[a[i + 1]].emplace(lc);
    }
}

vector<int> dp(int f, int t) {
    vector<int> fas(w + 10);
    fas[tim[t]] = we[t];
    for (auto c: mp2[t]) {
        if (c == f)continue;
        vector<int> v1 = dp(t, c);
        int mul = cost(t, c);
        for (int i = max(w - 2 * dep[t], 0ll); i >= 0; i--) {
            for (int j = 0; j <= w; j++) {
                if (i - mul - j < 0)break;
                fas[i] = max(fas[i], v1[j] + fas[i - mul - j]);
            }
        }
    }
    return fas;
}

void solve() {
    //7 3 10
    cin >> n >> m >> w;

    v.resize(m + 1);

    v[0] = {1, 0, 0};


    siz[0] = 0;
    dep[0] = 0;
    for (int i = 2; i <= n; i++) {
        int f;
        cin >> f;
        mp[f].emplace_back(i);
        fa[i] = f;
    }
    for (int i = 1; i <= m; i++) {
        cin >> v[i][0] >> v[i][1] >> v[i][2];
        tim[v[i][0]] = v[i][1];
        we[v[i][0]] = v[i][2];
    }

    dfs1(1);
    dfs2(1);
    build_virtual_tree();
    vector<int> aa = dp(0, 1);
    int maxs = -1;
    for (int i = 0; i <= w; i++) {
        maxs = max(maxs, aa[i]);
    }
    cout << maxs << endl;
}


signed main() {
    IOS
    int t = 1;
    //    cin >> t;
    while (t--)solve();
}

本题可以在分组背包中进行一定的剪枝通过，如过深的节点忽略，将原理数组背包转换为离散化背包，可以大量优化计算的过程，

有帮助，赞一个

去预览

0/2000

全部评论 5

.云志.(〃'▽'〃)
《入门》《普及/提高-》

2025-08-18 来自辽宁
5
- viex
  回复
  .云志.(〃'▽'〃)
  第五题就一个人做出来标一个《普及/提高-》
  
  2025-08-20 来自江苏
  1
- viex
  回复
  viex
  出题人小号给我点赞了？？？！！！
  
  2025-08-21 来自江苏
  0
- cjdst
  回复
  viex
  这题确实是黄题啊
  
  2025-08-21 来自广东
  0
一个不是人类的人类👀
mc交流社招人啦！！！

您好，我是mc交流社的管理员，我现在创立的这个团队急需成员，我都是在和我的世界有关的团队里拉的人。
您肯定玩过mc，哪怕现在不玩了也没关系。
现在团队刚刚创立，没有什么人，如果您想要当可以直接来找我，如果您喜欢清静，可以静静的在团队列表之中
看在我关注您的份上，希望您可以加入我的团队，mc交流社永远是您的家，不会背叛您
如果您想要加入请复制这个网址加入，我真的由衷的感谢您
https://www.acgo.cn/application/1955878250943008768
如果您确实不想加入那我真的很抱歉打扰到你了，对不起

2025-08-20 来自广东
0
Grapher
老师T4题目是不是打错了

2025-08-18 来自浙江
0
- Grapher
  回复
  Grapher
  是汉明距离二
  
  2025-08-18 来自浙江
  0
dream92143
不是巅峰赛吗

2025-08-18 来自浙江
0
- hopebetter
  回复
  dream92143
  已修改
  
  2025-08-18 来自浙江
  0
cjdst
老师T4双老哥能过

2025-08-18 来自浙江
0
- cjdst
  回复
  cjdst
  绷
  
  2025-08-18 来自浙江
  0
- hopebetter
  回复
  cjdst
  没特意卡 ,下次注意，这次所有的题时限都比较宽
  
  2025-08-18 来自浙江
  0
- Grapher
  回复
  cjdst
  为什么你和文明个一样抽象了
  
  2025-08-18 来自浙江
  0