官方题解 | 巅峰赛#36

NoonMaple

2026-07-20 09:51:06

发布于：浙江

186阅读

0回复

0点赞

巅峰赛36 题解

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

题目编号	题目标题	难度
T1	午枫的传话游戏	普及/提高-
T2	午枫的教室路线	普及/提高-
T3	午枫的数字替换	普及/提高-
T4	午枫的课堂笔记	普及/提高-
T5	午枫的自习时间	普及+/提高
T6	午枫的涂色方案	普及+/提高

T1 午枫的传话游戏

题意简述

有 $n$ 个同学，每人有一个数字 $a_i$ 。若两数绝对差为 $1$ 则可直接传话，传话关系具有传递性。求最少添加多少对直接传话关系，使得整个图连通（任意两人可互相传话）。

解题思路

将数字视为节点，值相等的同学共享同一节点（他们之间差值为 $0$ ，需要额外处理）。先对数组排序去重分析连续段：如果两个相邻数值相差为 $1$ ，则它们天然有边相连；若相差 $>1$ ，则这两段之间需要添加一条边来连通。因此，数值轴上会形成若干个由差值为 $1$ 的连续段构成的连通块。

对于同一数值有多人的情况：这些人内部没有直接边（差值 $0$ ），他们必须借助相邻数值才能连通。如果一个连通块中只有一个数值（左右均断），那么该数值内的 $t$ 个同学需要 $t-1$ 条边才能内部连通，并且还需与外部块连接。当连通块有多个数值时，块内的所有同学可通过链式结构自然连通，只需向外连边时添加一条边。

边数最少为 $\max(0, \text{连通块数} - 1) + \sum(\text{孤立数值内部人数} - 1)$ 。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a.begin(), a.end());
        
        int cnt = 0, l = 0, r = -1, t = 0;
        for (int x : a) {
            if (x > r + 1) {
                cnt += (l == r) ? t : 1;
                l = x;
                t = 0;
            }
            r = x;
            t++;
        }
        cnt += (l == r) ? t : 1;
        cout << cnt - 2 << endl;
    }
    return 0;
}

T2 午枫的教室路线

题意简述

有一个 $H \times W$ 的网格，从 $(1,1)$ 走到 $(H,W)$ ，每次只能向下或向右。给定一个长度为 $H+W-2$ 的字符串 $S$ ，其中 D 表示这一步必须向下，R 表示必须向右，? 表示可以自由选择向下或向右。对于每一种合法的路径，我们把该路径经过的所有格子（包括起点和终点）标记为已访问。问在所有合法路径中，最多能有多少个不同的格子被至少一条路径访问到。

解题思路

令必须向下的步数为 $D_{fix}$ ，必须向右的步数为 $R_{fix}$ ，自由步中需选 $n = H-1-D_{fix}$ 步为向下、 $m = W-1-R_{fix}$ 步为向右。问题等价于求有多少格子 $(i,j)$ 存在一种 ? 的赋值，使得路径经过该格。

考虑格子 $(i,j)$ ，到达它需要 $k = i+j-2$ 步，其中向下 $i-1$ 步。设前 $k$ 步中必须向下 $d_k$ 步、必须向右 $r_k$ 步、自由 $s_k$ 步。后 $L = H+W-2-k$ 步中必须向下 $d'_L$ 步、自由 $s'_L$ 步。存在合法路径经过 $(i,j)$ 当且仅当存在整数 $x$ （前 $k$ 步中选择向下的自由步数）满足：

$i-1 = d_k + x$ ，即 $x = i-1-d_k$
$0 \le x \le s_k$ ，且 $x \le n$
$H-i = d'_L + (n-x)$ ，即 $n-x = H-i-d'_L$
$0 \le n-x \le s'_L$

消去变量后，固定 $k$ 时 $i$ 的取值范围为：

$\max(d_k+1,\; k - \min(s_k, m) - r_k + 1) \le i \le \min(\min(s_k, n) + d_k + 1,\; k - r_k + 1)$

其中 $n = H-1-D_{fix}$ ， $m = W-1-R_{fix}$ 。每个 $i$ 对应格子 $(i, k+2-i)$ 。

遍历 $k = 0$ 到 $H+W-2$ ，累加每个 $k$ 对应的合法 $i$ 的个数，即为答案。起点 $k=0$ 和终点 $k=H+W-2$ 自动包含在内。

参考代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int N = 400010;
int d[N], r[N], s[N];
string S;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int h, w;
        cin >> h >> w;
        cin >> S;
        S = " " + S;
        
        int len = h + w - 2;
        for (int i = 1; i <= len; i++) {
            d[i] = d[i-1] + (S[i] == 'D');
            r[i] = r[i-1] + (S[i] == 'R');
            s[i] = s[i-1] + (S[i] == '?');
        }
        
        int total_d = d[len];
        int total_r = r[len];
        int n = h - 1 - total_d;
        int m = w - 1 - total_r;
        
        long long ans = 0;
        for (int k = 0; k <= len; k++) {
            int L = max(d[k] + 1, k - min(s[k], m) - r[k] + 1);
            int R = min(min(s[k], n) + d[k] + 1, k - r[k] + 1);
            if (L <= R) {
                ans += R - L + 1;
            }
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}

T3 午枫的数字替换

题意简述

给定一个长度为 $N$ 的数字串 $S$ 和一个长度为 $M$ 的数字串 $T$ ，按顺序进行 $M$ 次操作，第 $k$ 次操作可以将 $S$ 的任意一个位置替换为 $T$ 的第 $k$ 个字符。每次替换会覆盖原有数字。问经过全部 $M$ 次操作后，得到的 $S$ 作为整数值最大是多少，输出这个字符串。

解题思路

我们依次进行 $M$ 次替换，每次可以选任意位置。最后一次操作特别重要，因为它不会被后续操作覆盖。如果我们把某个数字放在最后一次操作中，它就会永远留在最终字符串的那个位置上。

为了使得最终字符串的字典序最大，我们希望前面的字符尽可能大。因此，一个直观的贪心策略是：除了最后一次操作的数字以外，前面的 $M-1$ 次操作我们可以自由选择用哪些数字去替换哪些位置。我们把这 $M-1$ 个数字从大到小排序，然后从左到右扫描 $S$ 的每个位置，如果当前最大的可用数字比 $S$ 这个位置上的数字大，就进行替换，然后这个数字被消耗掉，继续看下一个位置。这样可以保证在前面的位置上尽量使用大的数字。

接下来考虑最后一次操作的数字 $T_M$ 。它必须被用到某个位置上。如果在前面的贪心过程中， $T_M$ 已经被当作一个较大的数字使用过了（即它已经被换到了某个位置上），那就不用再额外处理。如果没有被使用过，说明 $T_M$ 比 $S$ 中所有未被替换过的位置上的数字都小（因为贪心过程中只有遇到更大的数字才会替换）。此时，我们只能把它放在某个位置上，为了对整个字符串的字典序影响最小，应该把它放在最后一位。因为放在任何更前面的位置都会使得那个位置变小，从而让整个字符串变小，而放在末尾只会影响最后一位，前面的大数字结构保持不变。

这样操作后，得到的字符串就是最大的可能结果。

参考代码

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

int n, m, it;
string s, t;
char last_char;
bool used;

int main() {
    cin >> n >> m;
    cin >> s >> t;
    s = " " + s;
    t = " " + t;

    last_char = t[m];
    sort(t.begin() + 1, t.end());

    it = m;
    for (int i = 1; i <= n; i++) {
        if (it > 0 && t[it] > s[i]) {
            s[i] = t[it];
            it--;
        }
    }

    used = false;
    for (int i = 1; i <= n; i++) {
        if (s[i] == last_char) {
            used = true;
            break;
        }
    }

    if (!used) {
        s[n] = last_char;
    }

    for (int i = 1; i <= n; i++) {
        cout << s[i];
    }
    cout << endl;

    return 0;
}

T4 午枫的课堂笔记

题意简述

按顺序处理 $N$ 个数，对每个数必须恰好执行一次操作：要么写入到笔记板末尾，要么删除笔记板末尾的一个数（板为空时不能删除）。操作结束后，笔记板中剩余数的和即为结果。求最大可能和。

解题思路

定义 $f[i][0]$ 表示处理完前 $i$ 个数且第 $i$ 步执行删除操作时，当前栈中数字和的最大值； $f[i][1]$ 表示第 $i$ 步执行写入操作时的最大值。

若第 $i$ 步是删除，则它必须删除上一步刚写入的数，因此第 $i-1$ 步必须是写入，删除后状态回到第 $i-2$ 步之后的状态，故 $f[i][0] = \max(f[i-2][0], f[i-2][1])$ 。

若第 $i$ 步是写入，则直接加上 $A_i$ ，可以从第 $i-1$ 步的任意状态转移来，即 $f[i][1] = \max(f[i-1][0], f[i-1][1]) + A_i$ 。

初始条件 $f[1][0]$ 不合法（第一步不能删除），设为负无穷； $f[1][1] = A_1$ 。最终答案为 $\max(f[N][0], f[N][1])$ 。

参考代码

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

typedef long long ll;
const int MAXN = 2e5 + 5;
const ll INF = 0xc0c0c0c0c0c0c0c0;

ll n, a[MAXN];
ll f[MAXN][2];

int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    
    f[1][0] = INF;
    f[1][1] = a[1];
    
    for (int i = 2; i <= n; i++) {
        f[i][0] = max(f[i-2][0], f[i-2][1]);
        f[i][1] = max(f[i-1][0], f[i-1][1]) + a[i];
    }
    
    printf("%lld\n", max(f[n][0], f[n][1]));
    
    return 0;
}

T5 午枫的自习时间

题意简述

给定一个长度为 $N$ 的字符串 $S$ ，由 o 和 x 组成。将 $S$ 重复 $M$ 次得到字符串 $T$ （长度为 $N \times M$ ）。你可以将 $T$ 中恰好 $K$ 个 x 改为 o。问修改后最长的连续 o 子串长度最大是多少。

解题思路

设 $S$ 中 x 的总数为 $cnt$ 。由于 $M$ 可能很大（ $10^9$ ），不能直接构造 $T$ 。考虑分情况讨论。

首先，如果 $M = 1$ 或 $M = 2$ ，可以直接构造出 $T$ （长度最多 $2N \le 6\times 10^5$ ），然后用双指针（滑动窗口）求最多包含 $K$ 个 x 的最长区间即可。

当 $M \ge 3$ 时，考虑在完整的若干个 $S$ 块中，每块有 $cnt$ 个 x。设 $num = \lfloor K / cnt \rfloor$ ，即可以完全填满的块数。分三种情况：

若 $num \ge M$ ，则所有 $M$ 个块都可以完全填成 o，答案为 $N \times M$ 。
若 $num = M-1$ ，则前 $M-1$ 个完整的块可以全部填满，剩下 $K' = K - (M-1) \times cnt + cnt$ 次调整机会（注意这里 STD 中写的是 k = k % cnt + cnt，相当于先消耗掉 $M-1$ 个整块，剩下的 $k$ 可能小于 $cnt$ ，但为了充分利用，实际上是在两个块中寻找最长的区间，最后加上 $(M-2) \times N$ 作为中间已填满的块的长度）。
若 $num \le M-2$ ，则中间有 $num$ 个完整填满的块，剩下的 $K' = K \% cnt$ 次调整机会用于在前后两个块中跨越拼接。同样用双指针在 $S+S$ 上找最多包含 $K'$ 个 x 的最长区间，然后加上 $num \times N$ 作为中间完整块的长度。

关键点在于：当 $M$ 很大时，最优解一定由若干完整填满的 o 块加上两端部分块内扩展得到的连续区间组成。通过在 $S+S$ 上运行滑动窗口（最多包含 $K \% cnt$ 或 $K \% cnt + cnt$ 个 x），可以求出跨越两个块边界时的最大长度，再加上中间完整块的总长度即可。

参考代码

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

using ll = long long;

void solve() {
    ll n, m, k;
    cin >> n >> m >> k;
    string s;
    cin >> s;
    
    ll cnt = 0;
    for (char c : s) {
        if (c == 'x') cnt++;
    }
    
    if (m == 1) {
        string t = " " + s;
        int l = 1, r = 1, sum = 0, res = 0;
        while (r <= n) {
            while (r <= n) {
                if (t[r] == 'x') sum++;
                if (sum > k) break;
                r++;
            }
            res = max(res, r - l);
            while (l <= r) {
                if (t[l] == 'x') sum--;
                l++;
                if (sum <= k) break;
            }
            r++;
        }
        cout << res << '\n';
        return;
    }
    
    if (m == 2) {
        string t = " " + s + s;
        int l = 1, r = 1, sum = 0, res = 0;
        while (r <= 2 * n) {
            while (r <= 2 * n) {
                if (t[r] == 'x') sum++;
                if (sum > k) break;
                r++;
            }
            res = max(res, r - l);
            while (l <= r) {
                if (t[l] == 'x') sum--;
                l++;
                if (sum <= k) break;
            }
            r++;
        }
        cout << res << '\n';
        return;
    }
    
    ll num = k / cnt;
    if (num >= m) {
        cout << n * m << '\n';
        return;
    }
    
    string t = " " + s + s;
    ll res = 0;
    
    if (num == m - 1) {
        ll rem = k % cnt + cnt;
        int l = 1, r = 1, sum = 0;
        while (r <= 2 * n) {
            while (r <= 2 * n) {
                if (t[r] == 'x') sum++;
                if (sum > rem) break;
                r++;
            }
            res = max(res, (ll)(r - l));
            while (l <= r) {
                if (t[l] == 'x') sum--;
                l++;
                if (sum <= rem) break;
            }
            r++;
        }
        res += (num - 1) * n;
        cout << res << '\n';
    } else {
        ll rem = k % cnt;
        int l = 1, r = 1, sum = 0;
        while (r <= 2 * n) {
            while (r <= 2 * n) {
                if (t[r] == 'x') sum++;
                if (sum > rem) break;
                r++;
            }
            res = max(res, (ll)(r - l));
            while (l <= r) {
                if (t[l] == 'x') sum--;
                l++;
                if (sum <= rem) break;
            }
            r++;
        }
        res += num * n;
        cout << res << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

T6 午枫的涂色方案

题意简述

一排 $N$ 个座位，初始状态第 $i$ 个座位上的数字为 $i \bmod 2$ ，即 $1,0,1,0,\dots$ 交替。每次操作可以选择两个位置 $l$ 和 $r$ 满足 $l+1<r$ ，且 $l$ 和 $r$ 上的数字相同，而 $(l,r)$ 内的所有数字都与 $l$ 不同，然后将 $(l,r)$ 内所有数字改为 $l$ 上的数字。给定目标状态 $A_1,\dots,A_N$ ，问有多少种不同的操作序列（操作次数不同或某一步的 $(l,r)$ 不同都算不同）能从初始状态变成目标状态，答案对 $998244353$ 取模。

解题思路

首先无解条件： $A_1$ 必须为 $1$ （位置 $1$ 永远不会被修改）， $A_N$ 必须等于 $N \bmod 2$ （位置 $N$ 也不会被修改）。否则答案为 $0$ 。

将初始序列视为 $N$ 个长度为 $1$ 、颜色交替的连续段。一次操作选择三个连续段（左、中、右），其中左右颜色相同、中间相反，操作后三段的中间段变为左右颜色，三段合并为一段。因此操作只合并相邻的相同颜色段，且每次减少两个段。

最终目标 $A$ 划分成若干连续同色段。每个段的长度必须为奇数（因为每次合并三个奇数长度段得到奇数长度段，从 $1$ 开始只能得到奇数）。若任何一段长度为偶数，答案为 $0$ 。

对于长度为 $L=2k+1$ 的段，它由 $2k+1$ 个初始段合并而成，需要 $k$ 次操作。其内部合并方案数为 $f(k) = (2k-1)!! = \prod_{i=1}^{k} (2i-1)$ 。

设最终有 $c$ 个段，半长度分别为 $k_1,\dots,k_c$ （即段长为 $2k_i+1$ ），总操作数 $K = \sum k_i$ 。不同段之间的操作可以任意交错，穿插方案数为多重组合数 $\frac{K!}{\prod k_i!}$ 。

因此总方案数为：

$\left(\prod_{i=1}^{c} f(k_i)\right) \times \frac{K!}{\prod k_i!}$

预处理阶乘、逆元及 $f(k)$ 即可 $O(N)$ 计算。

参考代码

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

const int N = 2e5 + 5;
const int P = 998244353;

long long f[N], fac[N], inv[N], fac_inv[N];
int a[N], n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    if (a[1] != 1 || a[n] != (n % 2)) {
        cout << 0 << endl;
        return 0;
    }
    
    f[0] = f[1] = 1;
    fac[0] = fac[1] = 1;
    inv[1] = 1;
    fac_inv[0] = fac_inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        f[i] = f[i-1] * (2 * i - 1) % P;
        fac[i] = fac[i-1] * i % P;
        inv[i] = (P - P / i) * inv[P % i] % P;
        fac_inv[i] = fac_inv[i-1] * inv[i] % P;
    }
    
    long long ans = 1;
    int total_k = 0;
    int len = 1;
    
    for (int i = 2; i <= n + 1; i++) {
        if (i <= n && a[i] == a[i-1]) {
            len++;
        } else {
            if (len % 2 == 0) {
                cout << 0 << endl;
                return 0;
            }
            int k = len / 2;
            total_k += k;
            ans = ans * fac_inv[k] % P * f[k] % P;
            len = 1;
        }
    }
    
    ans = ans * fac[total_k] % P;
    cout << ans << endl;
    
    return 0;
}