官方题解| 巅峰赛#22
2025-06-23 04:09:12
发布于：浙江
赛纲介绍
本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平
| 题目编号 | 题目名称 | 题目难度 |
|---|---|---|
| T1 | 未出现的人 | 入门 |
| T2 | gcd | 普及- |
| T3 | a + b | 普及- |
| T4 | 礼物 | 普及/提高- |
| T5 | 聊天室 | 普及+/提高 |
| T6 | BFS | 普及+/提高 |
未出现的人
题目大意
题目的要求是现在有 个姓名互不相同的同学， 其中 个人出席了本场会议，求未出场本比赛的学生的名单。
题解思路
我们可以采用标记法来解决这一问题。首先，建立一个数据容器，将所有原计划参加讲座的学生姓名依次存储其中，构建完整的学生列表。接着，在记录实际出席学生的过程中，对已出现的学生姓名在列表中进行标记，以此区分出席与未出席的学生。最后，对存储学生姓名的列表进行遍历，将所有未被标记的学生姓名输出，这些学生即为缺席讲座的人员，如此便能清晰呈现缺席学生名单 。
参考代码
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
int main() {
int n, m;
cin >> n >> m;
vector<int> vis(n + 1);
map<string, int> mp;
vector<string> arr(n + 1);
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
mp[s] = i;
arr[i] = s;
}
for (int i = 1; i <= m; i++) {
string s;
cin >> s;
vis[mp[s]] = 1;
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) cout << arr[i] << endl;
}
}
gcd
题目大意
你可以选择一个任意长度的子序列 。 然后求得子序列的最大公因数 。 将子序列每一个数 变为 。之后对于整个数组求最大公因数是多少。
题解思路
思考一下gcd(x ,x+1) 是多少，答案是 ,因此，我们如果选择一个子序列的最大公因数为 ，那么我们所有因子包含 的数都要被选举，否则整个数组最终的 为 。
因此我们可以枚举自己期望求的最大公因数是多少，之后我们对所有包含期望因子的求 ,对不包含的数也求另外一组 ，之后进行相应的操作
参考代码
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
using i128 = __int128;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
int maxs = 1;
for (int i = 1; i <= 5000; i++) {
int g_1 = 0, g_2 = 0;
for (int j = 1; j <= n; j++) {
if (arr[j] % i == 0) g_1 = __gcd(arr[j], g_1);
else {
g_2 = __gcd(arr[j], g_2);
}
}
maxs = max(__gcd(g_1 + 1, g_2), maxs);
}
cout << maxs << endl;
}
a + b
题目大意
使用三个集合的数生成三个数 , , ，满足 。
题解思路
命题证明：若存在整数 满足 ，则至少存在一组解使得
证明思路
- 基于进位特性的范围收缩：通过分析加法运算中每一位的进位情况，将可能的解空间从 量级逐步缩小至两位数范围。
- 个位情况分类讨论：以个位加法是否进位作为突破口，分情况证明存在小范围解。
- 两位数等式的普适性：利用“每一位都进位”的假设，将多位数问题转化为两位数问题。
详细证明过程
假设：存在三个整数 ，满足 且 ，其中 由三个特定字符集构建。
-
个位加法的基础分析
由于 ，等式成立的必要条件是个位数字满足 （其中 表示整数 的个位数字）。- 情况一：个位无进位
若 且 ，此时取 ，显然 ，命题得证。 - 情况二：个位有进位
若 （即向十位进位），此时需进一步分析十位数字的组合情况。
- 情况一：个位无进位
-
基于进位条件的十位分析
假设个位进位为 ，若字符集 中不包含数字 ，则无法通过更高位的运算消除个位进位带来的影响，导致等式不成立。因此，若有解且个位进位，则 是必要条件。- 此时，为使等式成立，十位数字需满足 （其中 表示整数 的十位数字），等价于 。若能找到满足此条件的 ，则可构造出两位数解 ，且 。
-
多位数问题向两位数的转化
由于假设每一位加法均产生进位，对于任意长度的 ，其每一段连续两位的数字组合（首尾拼接）均需满足加法进位规则。因此，验证所有可能解的充分条件是验证所有两位数组合，即只需在 的范围内寻找解。
结论
通过对个位进位情况的分类讨论，结合多位数进位的普遍规律，证明了若存在满足 且 的整数解，则必然存在一组解使得 。此结论将解空间显著缩小，为后续算法设计提供了理论依据。
参考代码
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
using i128 = __int128;
int main() {
string a, b, c;
cin >> a >> b >> c;
auto check = [&](int x, string _x) {
vector<int> vis(19);
for (auto i: _x) {
vis[i - '0'] = 1;
}
do {
if (!vis[x % 10]) return false;
x /= 10;
} while (x);
return true;
};
for (int i = 0; i <= 100; i++) {
for (int j = 0; j <= 100; j++) {
int k = i + j;
if (check(i, a) && check(j, b) && check(k, c)) {
cout << i << " " << j << " " << k << endl;
return 0;
}
}
}
cout << "impossible" << endl;
}
礼物
题目大意
你现在有 元钱，现在有 中不同的物品。每种物品有一个花费 和幸福值 ,你每次可以购买两个不同的物品，你的朋友会收下幸福度较低的一个，问你的朋友最大可以获得多少幸福度
题解思路
我们希望找到所有幸福值大于等于自己的元素中花费最少的应该是多少，这样我们可以先按照幸福值进行排序，之后我们可以用一个类似于前缀最小值的方法找到相应的花费，活着直接枚举也可以。
问题就转换为一个 个物品， 点花费的完全背包。
参考代码
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
using i128 = __int128;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
// v_i. cost
vector<pair<i64, i64> > arr(n + 1);
for (int i = 1; i <= n; i++) {
int u, v;
cin >> u >> v;
arr[i] = {v, u};
}
sort(arr.begin() + 1, arr.end(), greater<>());
vector<pair<i64, i64> > nn;
i64 ex = arr[1].second;
for (int i = 2; i <= n; i++) {
nn.emplace_back(arr[i].first, arr[i].second + ex);
ex = min(arr[i].second, ex);
}
vector<i64> f(m + 1);
for (auto [v_i , c_i]: nn) {
for (int i = c_i; i <= m; i++) {
f[i] = max(f[i], f[i - c_i] + v_i);
}
}
cout << f[m] << endl;
}
聊天室
题目大意
一天一共有 个时刻 ，其中有 个线段，每一个线段从 开始， 到 结束。现在有 次询问，每次询问有一个 ,问已知区间有没有能和现在的区间相交为 。
题解思路
题目分析
这个问题描述了一个场景：Alice 有 m 位网友，每位网友每天在固定的时间段 内可以聊天。接下来有 q 天，每天 Alice 会在 时间段内寻找网友聊天，如果能找到一位网友可以持续聊天 d_i 时长，就能放松。我们需要判断每一天 Alice 是否能成功放松。
解题思路
-
问题转化：我们需要判断是否存在一位网友，其在线时间段 与 Alice 的查询时间段 的交集长度 。
-
关键观察：
- 交集长度 =
- 可以转化为三种情况：
-
a) 网友的右端点足够大：
-
b) 网友的左端点足够小：
-
c) 网友的在线时长足够长：
-
-
数据结构选择：
- 使用线段树（Segment Tree）来高效查询区间信息
- 分别处理上述三种情况，用三个线段树来维护
参考代码
#include<bits/stdc++.h>
using namespace std;
class STG {
public:
int n;
vector<int> arr;
STG(int n) : n(n), arr(4 * n) {
}
int query(int q, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return arr[q];
}
if (l > R || r < L || l > r) return 0;
int mid = (l + r) / 2;
return max(query(q << 1, l, mid, L, R), query(q << 1 | 1, mid + 1, r, L, R));
}
void push_up(int q) {
arr[q] = max(arr[q << 1], arr[q << 1 | 1]);
}
void modify(int q, int l, int r, int pos, int x) {
if (l == r) {
arr[q] = max(arr[q], x);
return;
}
int mid = (l + r) / 2;
if (mid >= pos) {
modify(q << 1, l, mid, pos, x);
} else modify(q << 1 | 1, mid + 1, r, pos, x);
push_up(q);
}
};
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector<pair<int, int> > arr(m + 1);
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
arr[i] = {u, v};
}
vector<int> ans(q + 1);
vector<tuple<int, int, int> > ask(q + 1);
for (int i = 1; i <= q; i++) {
int l, r, d;
cin >> l >> r >> d;
ask[i] = {l, r, d};
} {
STG s1(n + 1);
vector<vector<int> > r1(n + 1);
vector<vector<pair<int, int> > > ar1(n + 1);
for (int i = 1; i <= m; i++) {
r1[arr[i].first].emplace_back(arr[i].second);
}
for (int i = 1; i <= q; i++) {
auto [l, r ,d] = ask[i];
ar1[l].emplace_back(l + d - 1, i);
}
for (int i = 1; i <= n; i++) {
for (auto r: r1[i]) {
s1.modify(1, 1, n, r, 1);
}
for (auto [r, id]: ar1[i]) {
int t = s1.query(1, 1, n, r, n);
ans[id] |= t;
}
}
} {
STG s2(n + 1);
vector<vector<int> > l1(n + 1);
vector<vector<pair<int, int> > > al1(n + 1);
for (int i = 1; i <= m; i++) {
l1[arr[i].second].emplace_back(arr[i].first);
}
for (int i = 1; i <= q; i++) {
auto [l, r ,d] = ask[i];
al1[r].emplace_back(r - d + 1, i);
}
for (int i = n; i; i--) {
for (auto l: l1[i]) {
s2.modify(1, 1, n, l, 1);
}
for (auto [l, id]: al1[i]) {
int t = s2.query(1, 1, n, 1, l);
ans[id] |= t;
}
}
} {
STG s3(n + 1);
vector<vector<int> > lr1(n + 1);
vector<vector<pair<int, int> > > alr1(n + 1);
for (int i = 1; i <= m; i++) {
auto [l , r] = arr[i];
lr1[r - l + 1].emplace_back(l);
}
for (int i = 1; i <= q; i++) {
auto [l, r ,d] = ask[i];
alr1[d].emplace_back(r - d + 1, i);
}
for (int i = n; i; i--) {
for (auto l: lr1[i]) {
// cerr << "modify" << " " << l << " " << 1 << endl;
s3.modify(1, 1, n, l, 1);
}
for (auto [_, id]: alr1[i]) {
auto [l, r ,d] = ask[id];
int t = s3.query(1, 1, n, l, r-d +1 );
ans[id] |= t;
}
}
}
for (int i = 1; i <= q; i++) {
if (ans[i]) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
BFS
题目大意
给出一个求 序的方法，求 序的种类数。
题解思路
问题1：组合排列中的经典计数问题
给定 个完全相同的红球与 个完全相同的篮球，将它们排成一排，求不同排列情况的总数。这是一个典型的组合问题，可利用组合数公式求解。由于在总共 个位置中，只需确定 个红球的位置（篮球位置随之确定），因此排列情况数为组合数 。
问题2：树上BFS序的计数问题
对于给定的一棵树，我们的目标是计算从根节点出发，所有可能的广度优先搜索（BFS）序的数目。这里，我们采用树上动态规划的策略来解决。
动态规划过程中，假设当前已处理到节点 ，并且已经考虑了其子树的一个特定集合 。其中，集合 包含的节点总数为 ，该集合内所有节点构成的子结构可能产生的BFS序的数量为 。此时，若要将一个新的子树纳入考虑范围，该子树的节点数为 ，其自身可能的BFS序数量为 。那么，将新子树加入后形成的新集合 ，其可能的BFS序数量可通过如下方式计算：
根据分步乘法计数原理，先将原集合 的 种情况与新子树的 种情况进行组合，得到 种初步组合。进一步考虑到新子树节点与原集合节点在BFS遍历顺序中的相对位置关系，本质上是在 个位置中选择 个位置放置原集合节点（剩余位置放置新子树节点），所以最终新集合 可能的BFS序数量为 。通过这样逐步扩展子树集合，自底向上地进行动态规划计算，最终可得到从根节点出发的所有可能BFS序的数目。
问题3：换根DP实现任意节点的BFS序计数
在求解出以1号节点为根时的BFS序情况数后，为了计算以其他节点为根时的情况数，我们引入换根动态规划的方法。
具体操作上，首先针对当前根节点，将其某一棵子树的情况从原有计算结果中去除，消除该子树对当前根节点计算的影响。随后，通过精心设计的状态转移规则，将相关状态信息合理地转移到新选定的根节点上，从而实现从不同节点视角重新计算BFS序的情况数。通过遍历每个节点作为根节点，完成整个换根DP过程，即可得到树中任意节点作为根时可能的BFS序数目。
参考代码
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
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;
vector<vector<int> > edge ;
vector<i64> ans;
vector<pair<i64, i64> > f;
void dfs1(int fa, int u ) {
i64 t = 0;
i64 ff = 1;
for (auto v: edge[u]) {
if (v == fa) continue;
dfs1(u, v);
auto [s1 , j1] = f[v];
ff = mul(ff, j1);
i64 ex = Comb::C(t + s1, s1);
ff = mul(ff, ex);
t += s1;
}
t++;
f[u] = {t, ff};
}
void dfs2 (int fa, int u ) {
auto [aa, bb] = f[u];
ans[u] = bb;
for (auto v: edge[u]) {
if (v == fa)continue;;
auto t1 = f[u], t2 = f[v];
auto [x1 ,y1] = t1;
auto [x2, y2] = t2;
y1 = qdiv(y1, y2);
x1--;
y1 = qdiv(y1, Comb::C(x1, x2));
x1 -= x2;
x1++;
f[u] = {x1, y1};
y2 = mul(y1, y2);
x2--;
x2 += x1;
y2 = mul(y2, Comb::C(x2, x1));
x2++;
f[v] = {x2, y2};
dfs2(u, v);
f[u] = t1, f[v] = t2;
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
Comb::init(n * 2 + 1000);
edge.resize(n + 1), ans.resize(n + 1), f.resize(n + 1, {1,1});
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
edge[u].emplace_back(v);
edge[v].emplace_back(u);
}
dfs1(0, 1);
//
dfs2(0, 1);
for (int i = 1; i <= n; i++) {
cout << ans[i] << "\n";
}
}
有帮助，赞一个