官方题解 | 巅峰赛24题解

userId_undefined

hopebetter

2025-08-18 10:24:35

发布于：浙江

287阅读
0回复
0点赞

赛纲介绍

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

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

T1

模拟

题目大意

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

题解思路

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

复杂度分析

O(n)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,yx, y),(0≤x<y≤n0 \le x<y\le n), x,yx,y之间汉明距离的和

题解思路

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

复杂度分析

O(t×n2log⁡Vt\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×41\times 4 与 2×32\times 3 的矩形，矩形可以任意选择，问，能否拼成 n×mn \times m 的矩形。

题解思路

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

我们定义 n≤mn \le m

  • 当 n=1n = 1 时，mm 应该满足是 44 的倍数。 (情况1)

  • 当 n=2n = 2 时 ，我们注意到 m≥6m \ge 6 时，所有的数都可以转换为 a×4+b×3a \times 4 + b\times 3。那么我们考虑 m=2,3,4,5m = 2,3,4,5
    的情况，其中m=2,m=5m=2,m=5 两个情况不可以。 (情况2)

  • 当 n=3n= 3 时，因为 n×mn \times m 是偶数 ， mm 是偶数。一定可以。 (情况3)

  • 当 nmod  4=0n \mod 4 = 0 时，可以用 1×41\times 4 的拼出。 (情况4)

  • 当 n≥6且nmod  4=2n \ge 6 且 n \mod 4 =2 ，m≥6m \ge 6 ， n=4×a+2n = 4 \times a + 2 可以将图变成情况4 和情况 2 的组合， 一定可以。

  • 当 n≥5且nmod  2=1n\ge 5 且 n \mod 2 =1 ，mm 是偶数 , m≥6m \ge 6， n=2×a+3n = 2 \times a +3 ,可以将图变成情况3 和情况 2 的组合， 一定可以。

复杂度分析

O(t)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]f[i][j] 为小于等于 ii 的数中，与 ii 相差位数为 jj 的情况数。我们设 ii 二进制位数为 tt 位 ，我们可以将小于 ii 的数看做是两类，

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

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

复杂度分析

O(nlog⁡n)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

题目大意

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

题解思路

问题一：单色焊接

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

分析：

  1. 焊接次数：
  • 每次焊接可以连接一个水平线段和一个垂直线段。初始时有 nn 个水平线段和 mm 个垂直线段，最终需要连接成一个整体（即 1 个连通块）。
  • 每次焊接减少 1 个独立线段（因为焊接是将两个线段连接，相当于减少 1 个独立单位）。
  • 初始独立线段数为 n+mn + m，最终为 1，因此需要 (n+m)−1=n+m−1(n + m) - 1 = n + m - 1 次焊接。
  1. 焊接方案数：
  • 焊接顺序可以建模为一个路径问题：从 (0,0)(0, 0) 到 (n,m)(n, m)，每次选择焊接一个水平线段（向右走）或一个垂直线段（向上走）。
  • 总步数为 n+mn + m，其中 nn 步向右，mm 步向上。
  • 因此方案数为组合数 (n+mn)\binom{n + m}{n}。
  • 但焊接是从第一个焊接开始的，所以实际路径是从 (1,1)(1, 1) 到 (n,m)(n, m)，步数为 (n−1)+(m−1)=n+m−2(n - 1) + (m - 1) = n + m - 2，方向为 n−1n - 1 右和 m−1m - 1 上。
  • 因此方案数为 (n+m−2n−1)\binom{n + m - 2}{n - 1}。

结论：

  • 焊接次数：n+m−1n + m - 1 次。
  • 方案数：(n+m−2n−1)\binom{n + m - 2}{n - 1}。

问题二：双色焊接

问题描述：
现在有两种颜色的线段（颜色 aa 和 bb）：

  • 颜色 aa 的覆盖范围为左上角 (x1,y1)(x_1, y_1) 到右下角 (x2,y2)(x_2, y_2)。
  • 颜色 bb 的覆盖范围为左上角 (x3,y3)(x_3, y_3) 到右下角 (x4,y4)(x_4, y_4)。
    需要将两种颜色的线段分别连通。问如何焊接？如果两种颜色的范围有重叠，如何处理？

分析：

  1. 无重叠情况：
  • 如果颜色 aa 和 bb 的矩形区域不重叠（即 x2<x3x_2 < x_3 或 x4<x1x_4 < x_1 或 y2<y3y_2 < y_3 或 y4<y1y_4 < y_1），则可以完全独立处理。
  • 分别对颜色 aa 和 bb 使用问题一的思路。
  1. 有重叠情况：
  • 如果颜色 aa 和 bb 的矩形区域重叠，那么他们的焊接路径一定会有冲突。那么我们可以将两个颜色当成一个颜色，这样就可以多通过一次操作避免冲突。

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

复杂度分析

O（max⁡(n,m)\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

虚树

题目大意

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

题解思路

问题一

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

优化

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

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

复杂度分析

O(n+mlog⁡n+m×W2n + 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();
}

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

userId_undefined
去预览
0/2000

全部评论 5

热门讨论