AtCoder Beginner Contest 457 题解
AtCoder Beginner Contest 457 题解
| 项目 | 内容 |
|---|---|
| 比赛时间 | 2026-05-09 |
| 比赛链接 | https://atcoder.jp/contests/abc457 |
| 题目数量 | A–G 共 7 题 |
比赛概览
本场 A、B 是数组存取的纯热身题，C 把"重复拼接序列"转化为取模定位，D 是经典的二分答案加贪心判定。后半场的区分度明显提升：E 需要对区间覆盖做细致的分类讨论并配合预处理与二分；F 是一道思维量很大的插入型 DP 计数题（关键在于化简要记录的状态并用全局系数优化，值得反复琢磨）；G 则把"最少机器人数"通过偏序与 Dilworth 定理转化为经典的最长下降子序列问题。总体而言，F、G 是本场最值得重点掌握的两道题。
A - Array
题目链接：https://atcoder.jp/contests/abc457/tasks/abc457_a
题目大意
给定长度为 （）的整数序列 ，再给定整数 （），输出 的值。
思路
完全按题意模拟即可：依次读入 、数组 、，然后输出 。
唯一需要注意的是下标从 0 开始的语言（如 C++）：第 个元素存在 A[X-1] 里，千万不要写成 A[X]（既可能越界，也读错了元素）。这是入门题最常见的错误点。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++) cin >> A[i];
int X;
cin >> X;
cout << A[X - 1] << "\n";
return 0;
}复杂度分析
- 时间复杂度：
- 空间复杂度：
B - Arrays
题目链接：https://atcoder.jp/contests/abc457/tasks/abc457_b
题目大意
给定 （）个变长序列 ，其中第 个序列长度为 ，且 。再给定 ，输出 。
思路
题目想考察的是"变长数组"的用法。每个序列的长度 各不相同，且可能某一行的长度极大（如 ）。若用固定尺寸的 二维数组存，最坏需要 个元素，必然 MLE；而用 C++ 的 vector<vector<int>>（或 Python 的 list），每行只分配恰好 个元素，总共只需 个元素，内存完全没问题。
实现时注意输入格式：每行先给长度 ，再给 个元素；我们按需 resize(L_i) 再逐个读入即可。最后输出 A[X-1][Y-1]（两层都是 0 基索引）。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<vector<int>> A(N);
for (int i = 0; i < N; i++) {
int L;
cin >> L;
A[i].resize(L); // 只分配所需长度
for (int j = 0; j < L; j++) cin >> A[i][j];
}
int X, Y;
cin >> X >> Y;
cout << A[X - 1][Y - 1] << "\n";
return 0;
}复杂度分析
- 时间复杂度：
- 空间复杂度：
C - Long Sequence
题目链接：https://atcoder.jp/contests/abc457/tasks/abc457_c
题目大意
给定 个序列 （长度分别为 ）以及 个重复次数 。按顺序把 重复 次拼成一个总长 的序列 ，求 的值。
思路
千万不要真的构造 ：虽然 ，但 可以大到 ， 的总长可达约 ，无论是时间还是内存都不可接受。
正确做法是定位：依次考察每个序列 对应的那一大块（长度 ）。
- 若 ，说明 落在这块里。这一块就是 的 次重复，因此 等于 中的第 个元素。
- 否则把 减去 （跳过整块），继续看下一个序列。
这等价于官方题解里"找最大的 使 "，即确定 属于哪个序列块。正确性由"逐块跳过、最后落在当前块内"直接保证。
注意： 与 都可能是 量级， 用 64 位整数（long long）计算；(K-1) % L_i 也要用 64 位做取模。
参考代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
ll K;
cin >> N >> K;
vector<vector<ll>> A(N);
for (int i = 0; i < N; i++) {
int L;
cin >> L;
A[i].resize(L);
for (int j = 0; j < L; j++) cin >> A[i][j];
}
vector<ll> C(N);
for (int i = 0; i < N; i++) cin >> C[i];
for (int i = 0; i < N; i++) {
ll len = C[i] * (ll)A[i].size(); // 第 i 个序列重复 C_i 次后的总长
if (K <= len) {
cout << A[i][(K - 1) % (ll)A[i].size()] << "\n";
return 0;
}
K -= len;
}
return 0;
}复杂度分析
- 时间复杂度：
- 空间复杂度：
D - Raise Minimum
题目链接：https://atcoder.jp/contests/abc457/tasks/abc457_d
题目大意
给定长度为 （）的序列 和整数 。可以进行至多 次操作：选一个下标 （ 基），把 增加 。求操作后 的最大可能值。
思路
关键观察（单调性）：设 为用恰好/至多 次操作能达到的最大最小值，则 关于 单调不减——操作次数越多，结果只会更好。于是可以二分答案：把"求最大值"变成一系列"能否做到"的判定问题。
判定问题：给定 ，问能否用不超过 次操作使所有元素 。
对每个下标 （1 基），每操作一次 增加 。若 ，至少需要 次操作；若 则不需要。所需总操作数为
可行当且仅当 。
二分上下界：答案至少为 ；同时由于对 的每次操作只加 ，若想使最小值 就必须有 ，因此答案 。取 ，在 时折半即可。
易错点：
- 计算 用整数：（C++ 整数除法），不要用浮点
ceil，否则大数会有精度误差。 - 防溢出：、 都可到 ，全部用
long long；判定函数里累加need时，一旦超过 立即return false，既防溢出又加速。 - 二分上界 本身可能接近 ，仍在
long long范围内。
参考代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
ll K;
cin >> N >> K;
vector<ll> A(N);
for (int i = 0; i < N; i++) cin >> A[i];
// 判定：能否用不超过 K 次操作使所有元素 >= x
auto ok = [&](ll x) {
ll need = 0;
for (int i = 0; i < N; i++) {
if (A[i] < x) {
ll d = x - A[i];
need += (d + i) / (i + 1); // ceil((x - A_i) / (i+1))，下标 i 对应值 i+1
if (need > K) return false; // 提前退出，防溢出
}
}
return true;
};
ll lo = 1, hi = A[0] + K + 1; // 答案 < hi
while (hi - lo > 1) {
ll mid = (lo + hi) / 2;
if (ok(mid)) lo = mid;
else hi = mid;
}
cout << lo << "\n";
return 0;
}复杂度分析
- 时间复杂度：（判定 ，二分约 轮）
- 空间复杂度：
E - Crossing Table Cloth
题目链接：https://atcoder.jp/contests/abc457/tasks/abc457_e
题目大意
（）个格子排成一行，有 （）块布，第 块布恰好覆盖区间 。共 （）次询问，每次给 ，问能否恰好选择两块布，使它们覆盖的范围恰好是 （ 全覆盖， 之外一格都不能被覆盖）。
思路
对每个询问单独暴力枚举两块布是 ，显然不行。核心是把"合法选择"结构化地分类。
关键观察：能覆盖到格子 的布，其左端点必须恰好是 （若左端点 ，则覆盖了 左边的格子，违规）；同理，能覆盖到格子 的布，其右端点必须恰好是 。
按"是否存在恰好覆盖 的布"分两大类讨论。
情形一：存在恰好覆盖 的布。
设某块布 ，另一块布 必须满足：（否则覆盖越界），且两块布不同。于是答案为 Yes 当且仅当下面三种情况至少成立一种：
- 恰好覆盖 的布至少两块（ 也等于 ）；
- 存在一块布完全被包含在 中（ 严格在内部且左端 ）；
- 存在一块布完全被包含在 中（ 严格在内部且右端 ）。
注意情况 2、3 其实覆盖了" 严格包含于 "的全部可能：若 严格包含于 ，则要么 （归入情况 2），要么 （归入情况 3）。
预处理：令
即"左端点至少为 的布中，右端点的最小值"。从后往前递推即可：
于是"存在布包含于 " ；"存在布包含于 " 。同时用哈希表统计每种 的出现次数，情况 1 只需查 cnt[(S,T)]>=2。
情形二：不存在恰好覆盖 的布。
此时两块布 必然一块（覆盖 的那块）左端为 ，另一块（覆盖 的那块）右端为 ，且它们都不等于 。
- 对"左端为 "的布，我们总可以取右端点最大且 的那一块，记右端点为 （若存在）；
- 对"右端为 "的布，我们总可以取左端点最小且 的那一块，记左端点为 （若存在）。
两块拼接后恰好覆盖 当且仅当无缝隙：
为什么贪心取最值是对的：设任一合法选择为（左端 、右端 ）与（右端 、左端 ），其合法意味着 。而 、，于是 。所以若"贪心最优的两块"都拼不满 ，那任何选择都不可能合法；反之若贪心两块能拼满，它们本身就是一个合法选择。
如何找这两个值：对每个左端点 ，把以它为左端的布的右端点排好序存进 byL[L]；用 upper_bound 找 byL[S] 中最后一个 的元素，即 。对每个右端点 ，把以它为右端的布的左端点排好序存进 byR[R]；用 lower_bound 找 byR[T] 中第一个 的元素，即 。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<vector<int>> byL(N + 2), byR(N + 2);
vector<int> minR(N + 2, INT_MAX);
map<pair<int, int>, int> cnt; // 每种布的出现次数
for (int i = 0; i < M; i++) {
int L, R;
cin >> L >> R;
byL[L].push_back(R);
byR[R].push_back(L);
cnt[{L, R}]++;
minR[L] = min(minR[L], R);
}
for (int i = 1; i <= N; i++) {
sort(byL[i].begin(), byL[i].end());
sort(byR[i].begin(), byR[i].end());
}
// suf[i] = 左端点 >= i 的所有布中右端点的最小值
vector<int> suf(N + 3, INT_MAX);
for (int i = N; i >= 1; i--) suf[i] = min(suf[i + 1], minR[i]);
int Q;
cin >> Q;
while (Q--) {
int S, T;
cin >> S >> T;
int c = cnt.count({S, T}) ? cnt[{S, T}] : 0;
if (c > 0) { // 情形一：存在恰好覆盖 [S,T] 的布
bool ok = false;
ok |= (c >= 2); // 两块恰好都是 [S,T]
ok |= (suf[S + 1] <= T); // 存在布被包含在 [S+1,T]
ok |= (suf[S] <= T - 1); // 存在布被包含在 [S,T-1]
cout << (ok ? "Yes" : "No") << "\n";
continue;
}
// 情形二：不存在恰好覆盖 [S,T] 的布
bool ok = false;
auto& rs = byL[S]; // 左端为 S 的布的右端点
int posR = (int)(upper_bound(rs.begin(), rs.end(), T) - rs.begin()) - 1;
auto& ls = byR[T]; // 右端为 T 的布的左端点
int posL = (int)(lower_bound(ls.begin(), ls.end(), S) - ls.begin());
if (posR >= 0 && posL < (int)ls.size()) {
int r1 = rs[posR];
int l2 = ls[posL];
ok = (l2 <= r1 + 1); // 两块拼起来无缝隙
}
cout << (ok ? "Yes" : "No") << "\n";
}
return 0;
}复杂度分析
- 时间复杂度：（预处理 ，每个询问两次二分 ）
- 空间复杂度：
F - Second Gap
题目链接：https://atcoder.jp/contests/abc457/tasks/abc457_f
题目大意
求满足以下条件的 的排列 的个数（模 ）：对每个 ，设 、 分别为后缀 中最大与次大的元素，则 。
思路
插入型 DP：从后往前不断"在前端插入元素"
直接枚举排列显然不行。考虑从后往前构造：已经排好后缀 ，现在把 插到最前面，需要根据 判断这次插入是否合法。
记插入前后缀中最大值、次大值的位置分别为 （都 ）。插入 后，按 的相对大小分三种情况：
- 成为最大值：新最大在 ，新次大在 。要求 ，即 。
- 成为次大值：新最大仍在 ，新次大在 。同样要求 。
- 既非最大也非次大：最大、次大的位置 不变。此时后缀 的条件自动满足当且仅当 （因为两个后缀共享同一对 ）。
为什么不用记 ：情况 1、2 中条件只涉及 ；情况 3 中 原样保留，只要 就自动满足， 的值不参与判断。因此状态只需记住最大值所在的位置。
DP 定义与转移
设 = 后缀 的相对大小排列中，最大值位于位置 的方案数（）。
边界： 时后缀只有两个元素，最大值在 或在 ，各 1 种：
（由约束 知 必为 1，而两元素后缀的最大、次大位置差恒为 1，两种排列都合法。）
按 从大到小转移（）：
- 情况 1：；
- 情况 2：；
- 情况 3： 对所有 。系数 的来源：后缀原本有 个元素，插入 后共 个； 的相对名次可取第 名，共 种。
注意情况 3 仅在 时才合法；否则情况 3 的贡献为 0。
优化：全局系数 + 原地稀疏表
情况 3 对整张表乘同一个常数。若朴素实现，每步 ，总复杂度 ，不可接受。
优化的思路是把"整表乘常数"从表里提出来：维护一个全局系数 ，表中存的是"真实值除以 "（或说真实值 表内值）。每一步：
- 若 ：情况 3 等价于把 乘上 （表内值不动）；情况 1、2 的增量需要除以新系数后再加到表内对应位置，即对位置 与 各加 。
- 若 ：情况 3 倍率为 0，表内除位置 、 外全部清空，只保留这两个位置。
由于每次只写位置 和 ，而位置 在迭代过程中严格递减、每个位置至多被写一次，表中非零位置总数始终为 。用稀疏的方式（记录"当前非零位置"列表）做清空，总复杂度 。求逆元用费马小定理（模数为质数） 一次，也可预处理逆元表。
最后答案 。
参考代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
ll modpow(ll a, ll e) {
ll r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<ll> D(N - 1);
for (int i = 0; i < N - 1; i++) cin >> D[i];
// dp[a]：后缀 (P_i,...,P_N) 中最大值位于位置 a 的相对大小排列数（已除以全局系数 coef）
vector<ll> dp(N, 0);
dp[N - 1] = 1; // i = N-1：最大值在 N-1
dp[N - 2] = 1; // i = N-1：最大值在 N
vector<int> active = {N - 1, N - 2}; // 当前非零的位置（稀疏表）
ll coef = 1; // 全局系数（情况 3 的连乘）
for (int i = N - 3; i >= 0; i--) {
int j = i + D[i]; // 插入 P_i 前最大元素的位置 a
ll v = dp[j];
if (D[i] == D[i + 1]) { // 情况 3 倍率 = N-i-2 > 0
ll c = N - i - 2;
coef = coef * c % MOD;
ll add = v * modpow(c, MOD - 2) % MOD; // 除以新系数
if (dp[j] == 0) active.push_back(j);
dp[j] = (dp[j] + add) % MOD; // 情况 2
if (dp[i] == 0) active.push_back(i);
dp[i] = (dp[i] + add) % MOD; // 情况 1
} else { // 情况 3 倍率为 0：其余状态清零
for (int pos : active) dp[pos] = 0;
active.clear();
dp[j] = v; // 情况 2
dp[i] = v; // 情况 1
active = {j, i};
}
}
ll sum = 0;
for (ll x : dp) sum = (sum + x) % MOD;
cout << sum * coef % MOD << "\n";
return 0;
}官方题解另给了一份用 defaultdict 的 Python 实现，思路与上述稀疏表完全一致，可作对照：
from collections import defaultdict
mod = 998244353
n = int(input())
d = list(map(int, input().split()))
dp = defaultdict(int)
dp[n - 1] = 1
dp[n - 2] = 1
coef = 1 # 全局系数
for i in reversed(range(0, n - 2)):
j = i + d[i] # 插入前最大元素的位置
v = dp[j]
if d[i] == d[i + 1]:
coef = coef * (n - i - 2) % mod # 情况 3：整体乘倍率
add = v * pow(n - i - 2, -1, mod) % mod # 情况 1、2 的增量（除以倍率）
dp[j] = (dp[j] + add) % mod # 情况 2
dp[i] = (dp[i] + add) % mod # 情况 1
else:
dp.clear() # 情况 3 倍率为 0，清空其余状态
dp[j] = v # 情况 2
dp[i] = v # 情况 1
ans = sum(dp.values()) % mod
print(ans * coef % mod)复杂度分析
- 时间复杂度：（每步一次模逆 ，可用预处理逆元优化到 ）
- 空间复杂度：
G - Catch All Apples
题目链接：https://atcoder.jp/contests/abc457/tasks/abc457_g
题目大意
数轴上有 （）个苹果，第 个在坐标 处、于时刻 落下。机器人可放在任意坐标，从时刻 0 开始以不超过 1 的速度沿数轴自由移动，机器人收集苹果 当且仅当在时刻 恰好位于 。求收集全部苹果所需的最少机器人数。
思路
转化为偏序
若同一台机器人先收集苹果 再收集苹果 （当然必须 ），可行当且仅当
定义苹果之间的序关系 。它满足自反、反对称、传递，因此全体苹果构成一个有限偏序集。
做换元
则 等价于
（验证： 且 ，整理即得 且 。）
一台机器人能收集的苹果集合恰好是偏序中的一条链（任意两两可比）。问题"最少需要几台机器人"就是用最少条链覆盖全部元素。由 Dilworth 定理：有限偏序集中，最小链覆盖数 = 最大反链的大小（反链：任意两两不可比的集合）。
最大反链 → 最长下降子序列
把苹果按 字典序排序，设排序后为 。因为 ，所以
于是按排序顺序取出的任意反链，其 值必须严格递减；反之任一严格递减的 子序列都对应一条反链。因此
求最长严格下降子序列，等价于对 求最长严格上升子序列（LIS），用经典的贪心 + 二分（lower_bound）即可，。
为什么同 不会造成问题：若 ，则 且 当且仅当 ，而不同苹果 必不同（否则 相同，与约束矛盾），所以同 的苹果两两不可比。按 字典序排序后同 的 递增， 递减，LIS 在一组内至多取一个，恰好符合"同 组内至多取一个"的要求，无碍。
参考代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<pair<ll, ll>> a(N);
for (int i = 0; i < N; i++) {
ll T, X;
cin >> T >> X;
a[i] = {T + X, T - X}; // (u, v)
}
sort(a.begin(), a.end()); // 按 (u, v) 字典序排序
vector<ll> lis; // 对 -v 求最长严格上升子序列
for (auto& p : a) {
ll val = -p.second;
auto it = lower_bound(lis.begin(), lis.end(), val);
if (it == lis.end()) lis.push_back(val);
else *it = val;
}
cout << lis.size() << "\n";
return 0;
}复杂度分析
- 时间复杂度：（排序 + LIS）
- 空间复杂度：