官方题解 | 巅峰赛#36

userId_undefined
对方正在输入中…………
出道萌新时间刺客空间掌握者时空双修者进制转换师分治·分治练习生

2026-07-22 13:30:03

发布于：浙江

4阅读
0回复
0点赞

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

题目编号 题目标题 难度
T1 午枫的传话游戏 普及/提高-
T2 午枫的教室路线 普及/提高-
T3 午枫的数字替换 普及/提高-
T4 午枫的课堂笔记 普及/提高-
T5 午枫的自习时间 普及+/提高
T6 午枫的涂色方案 普及+/提高
T1 午枫的传话游戏
题意简述
有 n 个同学，每人有一个数字 a
i
​
。若两数绝对差为 1 则可直接传话，传话关系具有传递性。求最少添加多少对直接传话关系，使得整个图连通（任意两人可互相传话）。

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

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

边数最少为 max(0,连通块数−1)+∑(孤立数值内部人数−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×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≤x≤s
k
​
，且 x≤n
H−i=d
L
′
​
+(n−x)，即 n−x=H−i−d
L
′
​

0≤n−x≤s
L
′
​

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

max(d
k
​
+1,k−min(s
k
​
,m)−r
k
​
+1)≤i≤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×M）。你可以将 T 中恰好 K 个 x 改为 o。问修改后最长的连续 o 子串长度最大是多少。

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

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

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

若 num≥M，则所有 M 个块都可以完全填成 o，答案为 N×M。
若 num=M−1，则前 M−1 个完整的块可以全部填满，剩下 K
′
=K−(M−1)×cnt+cnt 次调整机会（注意这里 STD 中写的是 k = k % cnt + cnt，相当于先消耗掉 M−1 个整块，剩下的 k 可能小于 cnt，但为了充分利用，实际上是在两个块中寻找最长的区间，最后加上 (M−2)×N 作为中间已填满的块的长度）。
若 num≤M−2，则中间有 num 个完整填满的块，剩下的 K
′
=K%cnt 次调整机会用于在前后两个块中跨越拼接。同样用双指针在 S+S 上找最多包含 K
′
个 x 的最长区间，然后加上 num×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 个座位上的数字为 imod2，即 1,0,1,0,… 交替。每次操作可以选择两个位置 l 和 r 满足 l+1<r，且 l 和 r 上的数字相同，而 (l,r) 内的所有数字都与 l 不同，然后将 (l,r) 内所有数字改为 l 上的数字。给定目标状态 A
1
​
,…,A
N
​
，问有多少种不同的操作序列（操作次数不同或某一步的 (l,r) 不同都算不同）能从初始状态变成目标状态，答案对 998244353 取模。

解题思路
首先无解条件：A
1
​
必须为 1（位置 1 永远不会被修改），A
N
​
必须等于 Nmod2（位置 N 也不会被修改）。否则答案为 0。

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

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

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

设最终有 c 个段，半长度分别为 k
1
​
,…,k
c
​
（即段长为 2k
i
​
+1），总操作数 K=∑k
i
​
。不同段之间的操作可以任意交错，穿插方案数为多重组合数
∏k
i
​
!
K!
​
。

因此总方案数为：

(
i=1
∏
c
​
f(k
i
​
))×
∏k
i
​
!
K!
​

预处理阶乘、逆元及 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;

}

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论