官方题解| 巅峰赛#20

hopebetter

2025-04-28 15:24:16

发布于：浙江

39阅读

0回复

0点赞

本场巅峰赛的所有题目的难度评级为：

题目编号	题目标题	难度
T1	deepseek	入门
T2	染色	普及-
T3	竞赛	普及+/提高-
T4	偶数Ⅰ	普及+/提高-
T5	捉迷藏	普及+/提高
T6	偶数Ⅱ	普及+/提高

T1

A - deepseek

模拟，循环

首先，程序需要读入一个给定的字符串。在对该字符串进行遍历的过程中，当遇到字符 '|' 时，便开始输出 '|' 之后的那部分字符串内容。

时间复杂度 O（n）

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

int main() {
    string s;
    cin >>s;
    bool f = false;
    for(auto i : s){
        if(f) cout << i;
        if(i=='|') f= true;
    }
}

T2

B - 染色

模拟，分支

首先对于本题，我们发现对于 n = 1 时，因为 $Bob$ 可以将唯一的位置进行设置， $Alice$ 无法将全部的点变成黑色。

接下来我们考虑如果有一个无限的空间，你有 $k$ 次染色的机会，最多会有多少位置会被染色。

根据题面，只有一个点的四联通的位置有至少两个黑色的点，这个点可以被被动染色。

我们设两个黑色点的坐标分别为 $(x_1, y_1)$ $(x_2 , y_2)$ , 中间的点的坐标为 $(x_3,y_3)$ ,那么很容易证明 $min(x_1 ,x_2) \le x_3 \le max(x_1 , x_2),min(y_1 ,y_2) \le y_3 \le max(y_1 , y_2)$ 。

因此我们设被染色的点的最大的横坐标为 $x_{max}$ ，最小的横坐标为 $x_{min}$ ,最大的纵坐标为 $y_{max}$ ,最小的纵坐标为 $y_{min}$ ,所有被染色点的坐标 $(x_i ,y_i)$ , 满足 $x_{min} \le x_i \le x_{max}$ , $y_{min} \le y_i \le y_{max}$ 。

因此最好的情况似乎是沿着一个对角线进行染色，这样可以染成一个 $k \times k$ 的矩形。当 $n \gt k$ 时，无法将所有的矩阵染成黑色。

还有另外一种证明，如果一个点被相邻的两个点给染色，这几个点所构成的周长不会增加，因此 $k$ 次操作，最大染色后的图像，周长为 $4\times k$ ,最大组成一个边长为 $k$ 的正方形。

对于剩下的情况判断经过 $n$ 次染色，将整个矩阵染成黑色。可以分别按照奇偶性进行考虑，是可以构造的

时间复杂度 0（1）

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

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int n , k;
    cin >> n >>k;
    if( n == 1)cout <<"No"<<endl;
    else if( n > k )cout <<"No"<<endl;
    else cout <<"Yes" <<endl;
}

T3

C-竞赛

我们设目前比分为 $(a_1, b_1)$ , 下一次的比分为 $(a_2,b_2)$ ，两个时间点之间可能平局的局数有多少。

首先我们思考一下，最早的平局的分数应该是多少？应该是 $( \max(a_1 , a_2) ,\max(a_1,a_2))$ ,同理，最后一次可以的平局可能是多少？应该是 $( \min(b_1 , b_2) ,\min(b_1,b_2))$ 。这样我们只需要统计两个点之间的局数就可以了。

此外有一些特殊情况，比如连续三局的分数为 $(0,0)$ , $(1,1)$ , $(2,2)$ ,现在有多少种可能的平局？

针对上述两种情况处理完成，便可以完成本次的题目。

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


int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    i64 a1 = 0, b1 = 0;
    i64 t = 1;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        i64 x, y;
        cin >> x >> y;

        i64 a = max(a1, b1);
        if (a1 == b1) a++;
        i64 b = min(x, y);
        if (a <= b) { t += b - a + 1; }
        a1 = x;
        b1 = y;
    }
    cout << t << endl;
}

T4

D - 偶数Ⅰ

数学，枚举

首先，观察方程 $f(a,b,c)=\left | a^c - b^c \right |$ 。通过对该式子进行因式分解（例如，当 $c$ 为正奇数时，根据公式 $x^c - y^c = (x - y)(x^{c - 1} + x^{c - 2}y + \cdots + xy^{c - 2} + y^{c - 1})$ ），我们不难发现，在研究该方程的某些性质时， $c$ 的具体取值并不会对问题的本质产生实质性的影响。也就是说，在当前的问题背景下， $c$ 这一变量是冗余的。因为 $a - b$ 是偶数，后面的表达式是奇数。那么最终表达式的结果的末尾的二进制零的个数其实等于 $a-b$ 的末尾的二进制数零的个数。

基于上述分析，我们可以将原问题进行转化，即通过枚举变量 $a$ 和 $b$ 的取值，来计算式子 $\left | a - b \right |$ 的贡献值。

对于这个方法，在线是比较困难的，我们考虑离线先计算完每一个的结果。然后对每一次询问之间查表。

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

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

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]));
        }

        i64 iC(int i, int j) {
            return mul(ifa[i], mul(fa[j], fa[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;

vector<i64> ans;


void init(int t) {
    ans.resize(t + 1);
    for (int i = 2; i <= t; i++) {
        ans[i] = add(ans[i - 1], ans[i]);
        for (int j = 1; j < i; j++) {
            i64 z = 2 * i - 2 * j;
            ans[i] = add(ans[i], log2(z & -z));
        }
    }
    for (int i = 2; i <= t; i++) {
        ans[i] = qdiv(ans[i], (i) * (i - 1) / 2);
    }
}


int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    init(1e3 + 100);
    int t = 0;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        int x;
        cin >> x;
        cout << ans[x] << endl;
    }
}

T5

E-捉迷藏

模拟

本题聚焦于地图变换与连通块划分问题，目标是判断能否借助特定的行、列交换操作，将给定地图分割为两个或更多的连通块。

存在行列均含障碍物的点的情形：若地图中存在某个点，其所在行与列均包含障碍物，处理过程相对简单。可以先将需要分隔的物品移动至地图的四个角落，随后利用这些障碍物将物品包围起来，以此实现地图的分隔。
不存在行列均含障碍物的点的情形：当不存在满足上述条件的点时，经推导可知，所有障碍点能够通过一定的移动，组合形成一个矩形。在此情况下，核心任务转变为判断能否借助这个矩形，将地图中的空白点分割成两个或更多的连通块。

可以证明对于 1 情况，最多移动 4 次，对于 2 情况，最多移动 2 次。

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
vector<pair<int, int> > dd = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> s(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = " " + s[i];
    }
    vector<int> r(n + 2), l(m + 2);
    iota(r.begin(), r.end(), 0);
    iota(l.begin(), l.end(), 0);

    vector<tuple<char, int, int> > op;
    auto get_x_y = [&](int x, int y) {
        x = r[x];
        y = l[y];
        return s[x][y];
    };
    auto swapr = [&](int x, int y) {
        if (x == y) return;
        op.emplace_back('r', x, y);
        swap(r[x], r[y]);
    };
    auto swapl = [&](int x, int y) {
        if (x == y) return;
        op.emplace_back('l', x, y);
        swap(l[x], l[y]);
    };
    auto run = [&]() {
        int xx, yy;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (get_x_y(i, j) == 'X') xx = i, yy = j;
            }
        }
        vector<vector<int> > vis(n + 1, vector<int>(m + 1));
        auto can_reach = [&](int x, int y) {
            return x > 0 && x <= n && y > 0 && y <= m && get_x_y(x, y) == '.' && !vis[x][y];
        };
        queue<pair<int, int> > q;
        q.emplace(xx, yy);
        while (!q.empty()) {
            auto [x,y] = q.front();
            q.pop();
            vis[x][y] = 1;
            for (auto [dx , dy]: dd) {
                int ddx = dx + x, ddy = dy + y;
                if (can_reach(ddx, ddy)) {
                    q.emplace(ddx, ddy);
                    vis[ddx][ddy] = 1;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (get_x_y(i, j) == '.' && !vis[i][j]) {
                    cout << "Yes" << endl;
                    cout << op.size() << endl;
                    for (auto [c , x , y]: op) {
                        cout << c << " " << x << " " << y << endl;
                    }
                    cout << i << " " << j << endl;
                    return;
                }
            }
        }
        cout << "No" << endl;
    };
    auto rz = [&](int x, int y) {
        swapl(1, y);
        swapr(1, x);
        for (int k = 1; k <= n; k++) {
            if (get_x_y(k, 1) == '#') {
                swapr(2, k);
                break;
            }
        }
        for (int k = 1; k <= m; k++) {
            if (get_x_y(1, k) == '#') {
                swapl(2, k);
                break;

            }
        }
        run();
    };

    vector<int> rr(n + 1), ll(m + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (get_x_y(i, j) == '#') {
                rr[i]++, ll[j]++;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if ((get_x_y(i, j) == '.' || get_x_y(i, j) == 'X') && ll[j] && rr[i]) {
                rz(i, j);
                return;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (get_x_y(i, j) == 'X') {
                rz(i, j);
                return;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

T6

F-偶数Ⅱ

我们定义 $f[j]$ 为对于所有 $i \in \{1 \sim j - 1\}$ ，第 $j$ 个奇数与第 $i$ 个奇数组合后所产生的贡献值。例如， $f[2] = 1$ ，这是因为第一个奇数是 $1$ ，第二个奇数是 $3$ ，两数相减为 $2$ ， $2$ 会产生一点贡献。依此类推。

方法一

接着，我们思考表达式 $\left | a - b \right |$
的本质，它实际上是在求数轴上两点之间的距离。那么，最终结果所产生的贡献值是否可以转化为到 $j$ 点距离为 $2$
的点的数量加上到 $j$ 点距离为 $4$ 的点的数量，以此类推。

由此，我们推测 $f[j + 1]$ 可以转化为 $j + \lfloor\frac{j}{2} \rfloor + \lfloor\frac{j}{4} \rfloor + \cdots$

进而得到 $f[j + 1] - f[\lfloor \frac{j}{2} + 1 \rfloor] = j$

基于此，我们可以通过线性动态规划来计算每一个 $f[j]$ 。

方法二

我们思考，表达式 $\left | a - b \right | =\left | a + 2 - b + 2 \right |$

那么对于每一个 $f[j - 1 ]$ 向 $f[j]$ 递推的时候。其实可以递推为 $f[j]=f[j-1] + \log(2 *j)$ .

然后，结合前缀和以及相应的逆元操作，即可解决本题。

时间复杂度O（ $n+ q$ ）

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

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]));
        }

        i64 iC(int i, int j) {
            return mul(ifa[i], mul(fa[j], fa[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;

vector<i64> ans;


void init(int t) {
    Comb::init(t + 10);
    ans.resize(t + 10);
    for (int i = 1; i <= t; i++) {
        ans[i + 1] = add(ans[i / 2 + 1], i);
    }
    for (int i = 1; i <= t; i++) {
        ans[i] = add(ans[i], ans[i - 1]);
    }
    for (i64 i = 3; i <= t; i++) {
        ans[i] = mul(ans[i], Comb::iC(i, 2));
    }
}


int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    init(1e6 + 100);
    int t = 0;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        int x;
        cin >> x;
        cout << ans[x] << "\n";
    }
}

有帮助，赞一个

去预览

0/2000

全部评论 1

dream_陆军展览
普及+/提高-是什么

1小时前来自江苏
0

T1

T2

T3

T4

T5

T6

方法一

方法二

全部评论 1

热门讨论