AtCoder Beginner Contest 429 题解
AtCoder Beginner Contest 429 题解
| 项目 | 内容 |
|---|---|
| 比赛时间 | 2025-10-25 |
| 比赛链接 | https://atcoder.jp/contests/abc429 |
| 题目数量 | A–G 共 7 题 |
比赛概览
本场整体难度前低后高：A、B 是简单签到；C 是经典组合计数；D 把圆周上的起点按"由有人的点划分出的区间"压缩，再用双指针（滑动窗口）求每个区间的答案，单调性是关键；E 是"多源 BFS 维护每个点最近的、且来自不同起点的两个源"的经典套路；F 建立在"最短路不需要向左走"的观察之上，用线段树维护列与列之间的 min-plus 矩阵复合，较有区分度；G 是数论难题，核心是把指数集合分解为 个等差数列再分别用分治等比数列求和。建议重点掌握 D 的区间压缩 + 双指针、E 的次近源 BFS、F 的矩阵复合思路，以及 G 的 sqrt 启发式。
A - Too Many Requests
题目链接：https://atcoder.jp/contests/abc429/tasks/abc429_a
题目大意
给定两个正整数 和 （）。输出 行：第 行（）若 则输出 OK，否则输出 Too Many Requests。
思路
直接按题意模拟即可。用一个从 到 的循环，第 行根据 是否成立输出对应的字符串。数据范围极小，不需要任何优化。
易错点：题目要求的是"第 行"，判断条件是 （下标从 1 开始）；若用从 0 开始的循环则要写成 。每行输出后记得换行。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
for (int i = 1; i <= N; i++) {
if (i <= M) cout << "OK" << '\n';
else cout << "Too Many Requests" << '\n';
}
return 0;
}官方题解还给出了 Python 实现：
n, m = map(int, input().split())
for i in range(n):
if i < m:
print("OK")
else:
print("Too Many Requests")复杂度分析
- 时间复杂度：
- 空间复杂度：
B - N - 1
题目链接：https://atcoder.jp/contests/abc429/tasks/abc429_b
题目大意
给定长度为 的整数序列 和整数 。问能否删掉 中的某一个元素，使得剩余 个元素的和恰好等于 。能则输出 Yes，否则输出 No。约束：，，。
思路
关键观察：设 。若删去 ，剩余和就是 。要求 ，等价于
所以问题转化为：是否存在某个 使得 。这是一个 O(N) 的查找，不需要枚举删哪个元素。
为什么正确：正向看，删去 后剩余和为 ，等于 当且仅当 ；反向看，若 ，删去它之后剩余和就是 。两者完全等价。
易错点： 可能为负数（当 时），此时序列中没有元素等于它，答案必为 No；这种情形无需特判，只需正常查找。数据范围很小，用 long long 求和更稳妥。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<int> A(N);
long long sum = 0;
for (int i = 0; i < N; i++) {
cin >> A[i];
sum += A[i];
}
long long target = sum - M;
bool ok = false;
for (int x : A) {
if (x == target) ok = true;
}
cout << (ok ? "Yes" : "No") << '\n';
return 0;
}官方题解同样利用了 是否在序列中出现这一观察，Python 实现如下：
n, m = map(int, input().split())
a = list(map(int, input().split()))
if sum(a) - m in a:
print("Yes")
else:
print("No")复杂度分析
- 时间复杂度：
- 空间复杂度：（存储序列）
C - Odd One Subsequence
题目链接：https://atcoder.jp/contests/abc429/tasks/abc429_c
题目大意
给定长度为 的整数序列 （，）。求满足 ，且 中恰好包含两个不同的数值（即有两个相等、另一个不同）的三元组 的个数。
思路
关键观察：一个"恰好两个不同数值"的三元组，其"出现两次的那个数值"是唯一的。例如 （）中出现两次的数值就是 。因此可以按"出现两次的数值是谁"来分类计数，每个合法三元组恰好被统计一次。
对每个数值 ，设
固定数值 ，统计 中恰好有两个等于 的三元组：
- 从 个位置中选出 2 个放 ，方案数为 ；
- 剩下 1 个位置放任意不等于 的值，共有 种选择。
所以数值 的贡献为
答案就是
在读入时 O(N) 统计，再 O(N) 求和即可。
易错点： 在 时可达 量级，必须使用 64 位整数（long long）。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<long long> cnt(N + 1, 0);
for (int i = 0; i < N; i++) {
int x;
cin >> x;
cnt[x]++;
}
long long ans = 0;
for (int x = 1; x <= N; x++) {
ans += cnt[x] * (cnt[x] - 1) / 2 * (N - cnt[x]);
}
cout << ans << '\n';
return 0;
}复杂度分析
- 时间复杂度：
- 空间复杂度：
D - On AtCoder Conference
题目链接：https://atcoder.jp/contests/abc429/tasks/abc429_d
题目大意
周长为 的圆形池塘岸边有一个小屋和 个人。对实数 ，点 表示从小屋顺时针走 距离的位置，第 个人站在点 （同一位置可以站多人）。另给定整数 。
对 定义 ：高桥从点 出发顺时针移动，路上每到一个人的位置就算"遇到这些人"，累计遇到的人数一旦达到 就立刻停下；若停下处有多个人，全部计入。 为停下时累计遇到的人数（可能大于 ）。求 。
约束：，。
思路
第 1 步：按起点区间压缩。 把所有有人的点去重并按大小排序，得到
第 处有 个人，。
高桥的起点是 。若 ，则起点落在开区间 内，他遇到的第一批人一定在点 ；类似地，若 ，则第一批发人一定在 （绕一圈）。因此 只取决于 落在哪个"由有人的点划分出的区间"里：
第 2 步：求每个区间的 值。 把人数列看成循环数组（下标按模 理解）。对 ，令 是满足
的最小下标。那么"第一个遇到 "的起点区间对应的 值为
由于 ，这样的 一定在 开始的 个元素内找得到。
第 3 步：滑动窗口求所有 。 注意 ：当窗口左端 向右移动时，右端 只会向右移动。因此用双指针在线性时间内求出全部 ：维护当前窗口和 （初始 时暴力扩展 ），之后每处理完 就令 再继续扩展。右端总共移动不超过 次，总代价 。
第 4 步：按区间长度加权求和。 "第一个遇到 "（）的起点 满足 ，共 个；"第一个遇到 "的起点跨过 ，共
个。于是答案为
易错点：答案约为 ，必须用 64 位整数； 本身也用 long long 读入。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long m, c;
cin >> n >> m >> c;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
// 去重：b[i] 为有人的点，p[i] 为该点人数
vector<long long> b;
vector<int> p;
for (int i = 0; i < n; ) {
int j = i + 1;
while (j < n && a[j] == a[i]) j++;
b.push_back(a[i]);
p.push_back(j - i);
i = j;
}
int k = (int)b.size();
long long ans = 0;
int r = 0; // 窗口右端点（循环下标）
long long cur = 0; // 窗口和：p[i]+...+p[r-1]（循环意义下）
for (int i = 0; i < k; i++) {
while (cur < c) { // 扩展右端，直到累计人数达到 C
cur += p[r];
r++;
if (r >= k) r -= k;
}
// 此时 cur = Y_{i+1}（第一个遇到 b[i] 的区间）
if (i == 0) ans += (m + b[0] - b[k - 1]) * cur;
else ans += (b[i] - b[i - 1]) * cur;
cur -= p[i]; // 左端前进一格
}
cout << ans << '\n';
return 0;
}复杂度分析
- 排序去重：；滑动窗口：。
- 时间复杂度：
- 空间复杂度：
E - Hit and Away
题目链接：https://atcoder.jp/contests/abc429/tasks/abc429_e
题目大意
个点 条边的简单无向连通图，每条边移动耗时 。每个点被标记为 S（安全）或 D（危险），保证安全点至少 个、危险点至少 个。对每个危险点 ，求：从某个安全点出发，经过 ，最后到达一个不同于起点的安全点，所需的最短时间。
思路
关键观察：对危险点 ，设离它最近的两个（互不相同的）安全点分别为 ，距离为 。则答案为
理由分两步：
- 走法 显然满足条件（起点安全、经过 、终点是不同于起点的安全点），用时恰为 。
- 反过来，任意一条满足条件的走法，都可以拆成"某安全点 到 的路径"与" 到某安全点 的路径"两部分，其总时间
其中最小值恰好由"两个距离最小的不同安全点"取得。
因此只需要对每个点求出：最近的安全点及其距离，以及来自不同安全点的次近距离。
算法：多源 BFS。 把所有安全点作为起点（每个起点携带自己的编号），在图上做 BFS。对每个点维护两个状态：
- ：最近一次到达 的安全点编号， 为对应距离；
- ：来自另一个安全点 的最短距离 。
从点 展开到邻居 时：
- 若 还没被任何安全点到达，记录 、 并入队；
- 否则，若 已被记录过最近源但还没记录次近源，且当前源不等于 ，则记录为次近源并入队。
由于 BFS 按距离递增的顺序展开，每个点第一次被某个安全点到达时得到的是到它的最短距离，第二次被另一个安全点到达时得到的是次近距离。
为什么每个点只需保留两个源就足够：设点 已记录了它的最近源 和次近源 。对 的任意邻居 ，任何经由 到达 的其他源 都满足
即 到达 不可能比 更快，所以 不可能成为 的最近或次近源。故把 的两个源继续向后传播，就能保证每个点拿到它真正的最近与次近源。
最后对每个危险点 输出 即可。由于图连通且安全点至少两个，危险点的两个状态一定都被填满。
参考代码
#include <bits/stdc++.h>
using namespace std;
struct path_info {
int from; // 出发的安全点（源）编号
int to; // 当前到达的点
int dist; // 从源到 to 的距离
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> e(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--; v--;
e[u].push_back(v);
e[v].push_back(u);
}
string s;
cin >> s;
vector<vector<int>> f(n, vector<int>(2, -1)); // 最近 / 次近源
vector<vector<int>> d(n, vector<int>(2, -1)); // 对应距离
queue<path_info> q;
for (int i = 0; i < n; i++) {
if (s[i] == 'S') {
f[i][0] = i;
d[i][0] = 0;
q.push({i, i, 0});
}
}
while (!q.empty()) {
path_info tmp = q.front();
q.pop();
int src = tmp.from, v = tmp.to;
for (int w : e[v]) {
if (f[w][0] == -1) {
f[w][0] = src;
d[w][0] = tmp.dist + 1;
q.push({src, w, tmp.dist + 1});
} else if (f[w][1] == -1 && f[w][0] != src) {
f[w][1] = src;
d[w][1] = tmp.dist + 1;
q.push({src, w, tmp.dist + 1});
}
}
}
for (int i = 0; i < n; i++) {
if (s[i] == 'D') {
cout << d[i][0] + d[i][1] << '\n';
}
}
return 0;
}复杂度分析
- 时间复杂度：
- 空间复杂度：
F - Shortest Path Query
题目链接：https://atcoder.jp/contests/abc429/tasks/abc429_f
题目大意
有一个 的网格，# 为墙，. 为空地，保证初始 .。给出 个查询，每个查询给出 ，把该格子的墙/空状态翻转，然后输出从 走到 的最少步数（每次可以上下左右走到相邻空地），不可达则输出 。约束：。
思路
关键观察 1：最优路径不会向左走。 即存在一条最短路，每一步只向右、上或下（列号不递减）。反证：设 是一条最短路，且某一步从 向左走到 。由于终点在第 列， 之后必然再次到达第 列，设第一次回到第 列的位置为 （由 向右到达），两处之间的部分 全部落在第 列。
- 若 在向左走之前那一步是从 向右走到 的，那么 是"走过去又走回来"，删去后路径缩短 步，矛盾；
- 否则 是从 （）纵向走到 的。此时 与 都可通行且相邻；而 可通行。若 与 相邻，则 纵向连通；若 ，则 恰为中间行、与 相邻，同样纵向连通。因此把从 到 的整段（长度 ）替换为第 列内的纵向路径（长度 ），得到更短的路径，矛盾。
故最短路一定可以不含向左的移动。于是总步数 向右的 步 纵向步数，只需最小化纵向步数。
关键观察 2：每一列是一个"转移矩阵"。 对每一列 定义 矩阵 ，其中 表示"从第 行进入第 列、从第 行离开第 列"所需的最少纵向步数：
- 若第 行或第 行是墙，则 ；
- 若第 、 行可通行，但 与 之间某行是墙（列内纵向不连通），则 ；
- 否则 。
由于列只有 3 行，列内连通性判断非常直接。相邻两列的复合（先过第 列、再过第 列）就是 min-plus 矩阵乘法：
这种"矩阵"构成一个幺半群：复合满足结合律，单位元是对角矩阵（主对角线为 ，其余为 ）。
关键观察 3：用线段树维护。 从 （第 1 列第 0 行）进入，从 （第 列第 2 行）离开，所需纵向步数就是复合矩阵
的 分量。单点翻转只改变一列的矩阵，所以用线段树维护区间复合，每次查询取根节点的 即可：
实现细节：用 3 位掩码表示某一列的墙集合（第 位为 1 表示第 行是墙），预处理 8 种掩码对应的矩阵；线段树的 op 就是 min-plus 矩阵乘法，单次 。总复杂度 。
（官方题解使用 atcoder::segtree 实现，下面的代码为便于编译使用了手写线段树，思路完全一致。）
参考代码
#include <bits/stdc++.h>
using namespace std;
using Mat = array<array<int, 3>, 3>;
const int INF = 1e9;
// 复合：先过 left（较左的列），再过 right（较右的列）
// res[i][j] = min_k ( left[k][j] + right[i][k] )
Mat compose(const Mat& left, const Mat& right) {
Mat res;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) {
int best = INF;
for (int k = 0; k < 3; k++)
best = min(best, left[k][j] + right[i][k]);
res[i][j] = best;
}
return res;
}
// 单位元：对角矩阵
Mat ident() {
Mat m;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) m[i][j] = INF;
for (int i = 0; i < 3; i++) m[i][i] = 0;
return m;
}
// mask 第 r 位为 1 表示第 r 行是墙
Mat buildMat(int mask) {
Mat m;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) m[i][j] = INF;
for (int a = 0; a < 3; a++) { // 进入行 a
if (mask >> a & 1) continue;
for (int b = 0; b < 3; b++) { // 离开行 b
if (mask >> b & 1) continue;
bool ok = true;
for (int r = min(a, b); r <= max(a, b); r++)
if (mask >> r & 1) ok = false; // 列内被墙阻断
if (ok) m[b][a] = abs(a - b);
}
}
return m;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> s(n, 0); // 每列的墙掩码
for (int j = 0; j < 3; j++) {
string ss;
cin >> ss;
for (int i = 0; i < n; i++)
if (ss[i] == '#') s[i] |= 1 << j;
}
int size = 1;
while (size < n) size <<= 1;
vector<Mat> seg(2 * size, ident());
for (int i = 0; i < n; i++) seg[size + i] = buildMat(s[i]);
for (int i = size - 1; i >= 1; i--) seg[i] = compose(seg[i << 1], seg[i << 1 | 1]);
int q;
cin >> q;
while (q--) {
int r, c;
cin >> r >> c;
r--; c--;
s[c] ^= 1 << r; // 翻转该格
int pos = size + c;
seg[pos] = buildMat(s[c]);
for (pos >>= 1; pos; pos >>= 1)
seg[pos] = compose(seg[pos << 1], seg[pos << 1 | 1]);
int v = seg[1][2][0]; // 从第1列第0行进、第N列第2行出
cout << (v >= INF ? -1 : n - 1 + v) << '\n';
}
return 0;
}复杂度分析
- 每次矩阵乘为常数 次运算，线段树单点修改与查询均为 。
- 时间复杂度：
- 空间复杂度：
G - Sum of Pow of Mod of Linear
题目链接：https://atcoder.jp/contests/abc429/tasks/abc429_g
题目大意
组数据（），每组给定 （，，），求
思路
本题是数论难题。官方题解利用 Codeforces 的 Sqrt Heuristic for Floor Sums 技巧：把指数集合
分解成 个两两不交的等差数列，每个等差数列用"分治等比数列求和"以 求值。
第 1 步：化归到 。 令 ，并写 ，，（）。由于
故
因此只需解决 的情形，最后整体乘上 。
第 2 步：化归到 。 设 （）。当 时， 对应的 恰好构成 的一个排列，所以
于是
第一项是等比数列和；下面只需处理 的情形。此时（结合 ） 个值 两两不同。
第 3 步：把指数集合分解为等差数列。
方法一（按商分组）：把下标 按 分组。同一组内
是以 为公差的等差数列。这样的组有 个——当 接近 时组数接近 ，不够用。
方法二（sqrt 启发式）：取常数 。
- 若 ，直接暴力求值， 组（每个长度为 1）。
- 若 ，先看前 项 （）。由鸽巢原理，这 个点落在周长 的圆周上，必有两个点的环上距离 。设这两个点对应的下标差为 （），它们的（环上）距离为 ，则
把下标按 分成 个子序列 ，则
每个子序列内相邻两项的"步长"是 ，而 很小。于是对每个子序列再用方法一按商分组：一个长度为 的子序列只产生 个等差数列。总个数
其中第二个等号用 ，第三个用 且 。
于是无论哪种情况都能得到 个等差数列，且这些等差数列互不重叠（下标集合是 的一个划分）。
第 4 步：每个等差数列用分治等比求和。 对一个等差数列 （其中各项都是 内互不相同的整数，步长取 或 视 而定；若为负步长，把组内倒序即可，仍可写成首项 的递增等差数列），有
等比数列部分用分治计算，不需要模逆（因为 不一定是质数）：
每层递归只做常数次乘法/快速幂，故每个等差数列 。
总复杂度 ，足以通过 的数据。
实现细节：按商分组时会出现负数除法（例如递减序列中 为负），需要自己实现 floor_div 与 ceil_div 对负数取整； 的情形在化归后会变成 、，自然被处理掉。
参考代码
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int64 modpow(int64 a, int64 e, int64 R) {
a %= R;
int64 r = 1 % R;
while (e > 0) {
if (e & 1) r = r * a % R;
a = a * a % R;
e >>= 1;
}
return r;
}
// 返回 (sum_{i=0}^{n-1} x^i mod R, x^n mod R)
pair<int64, int64> geosum_pow(int64 x, int64 n, int64 R) {
if (n == 0) return {0, 1 % R};
if (n == 1) return {1 % R, x % R};
if (n % 2 == 0) {
auto [half, pw] = geosum_pow(x, n / 2, R); // half=sum_{i<n/2}, pw=x^{n/2}
return {half * (1 + pw) % R, pw * pw % R};
} else {
auto [half, pw] = geosum_pow(x, n - 1, R); // half=sum_{i<n-1}, pw=x^{n-1}
return {(half + pw) % R, pw * x % R};
}
}
int64 floor_div(int64 a, int64 b) { // b>0, floor(a/b)
if (a >= 0) return a / b;
return -((-a + b - 1) / b);
}
int64 ceil_div(int64 a, int64 b) { // b>0, ceil(a/b)
if (a >= 0) return (a + b - 1) / b;
return -((-a) / b);
}
// 求解 sum_{k=0}^{N-1} X^{(A*k+B) mod M} mod R
// 前提：gcd(A,M)=1, 0<=A,B<M, 1<=N<=M
int64 solve_coprime(int64 A, int64 B, int64 N, int64 M, int64 X, int64 R) {
if (N <= 0) return 0;
int64 STEP = (int64)sqrt((long double)M) + 2;
if (STEP > N) STEP = N;
if (N <= STEP) { // 暴力
int64 res = 0;
for (int64 k = 0; k < N; k++) {
int64 e = (A * k + B) % M;
res = (res + modpow(X, e, R)) % R;
}
return res;
}
// 前 STEP 项，找环上距离最近的一对（鸽巢原理给出 h <= M/STEP）
vector<int64> v(STEP);
for (int64 k = 0; k < STEP; k++) v[k] = (A * k + B) % M;
vector<int64> ord(STEP);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int64 a, int64 b) { return v[a] < v[b]; });
int64 best_h = M, best_i1 = 0, best_i2 = 1;
for (int64 t = 0; t < STEP; t++) {
int64 a = ord[t], b = ord[(t + 1) % STEP];
int64 gap = (v[b] - v[a] + M) % M;
if (gap != 0 && gap < best_h) { best_h = gap; best_i1 = a; best_i2 = b; }
}
if (best_i1 > best_i2) swap(best_i1, best_i2);
int64 d = best_i2 - best_i1; // 下标差，>= 1
int64 diff = (v[best_i2] - v[best_i1]) % M; // A*d mod M
if (diff < 0) diff += M;
int64 step;
bool neg;
if (diff <= M / 2) { step = diff; neg = false; } // 步长 +h
else { step = M - diff; neg = true; } // 步长 -h
int64 ans = 0;
int64 Xh = modpow(X, step, R); // X^h，所有子序列共用
for (int64 r = 0; r < d; r++) {
if (r >= N) break;
int64 L = (N - 1 - r) / d + 1; // 该子序列长度
int64 C = (A * r + B) % M; // 子序列首项
if (!neg) {
// v_t = (C + step*t) mod M，按商 q=floor((C+step*t)/M) 分组
int64 qmax = (C + step * (L - 1)) / M;
for (int64 q = 0; q <= qmax; q++) {
int64 tlo = max<int64>(0, ceil_div(q * M - C, step));
int64 thi = min(L, ceil_div((q + 1) * M - C, step));
if (tlo >= thi) continue;
int64 len = thi - tlo;
int64 v0 = C + step * tlo - q * M; // 组内首项
int64 add = modpow(X, v0, R) * geosum_pow(Xh, len, R).first % R;
ans = (ans + add) % R;
}
} else {
// v_t = (C - step*t) mod M，按商分组（商随 t 递减）
int64 qmin = floor_div(C - step * (L - 1), M);
for (int64 q = 0; q >= qmin; q--) {
int64 tlo = max<int64>(0, floor_div(C - (q + 1) * M, step) + 1);
int64 thi = min(L, floor_div(C - q * M, step) + 1);
if (tlo >= thi) continue;
int64 len = thi - tlo;
int64 vlast = C - step * (thi - 1) - q * M; // 组内最小项
int64 add = modpow(X, vlast, R) * geosum_pow(Xh, len, R).first % R;
ans = (ans + add) % R;
}
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int64 N, M, A, B, X, R;
cin >> N >> M >> A >> B >> X >> R;
// 化归 gcd=1
int64 g = gcd(A, M);
int64 M2 = M / g;
int64 A2 = A / g;
int64 B1 = B / g;
int64 B2 = B % g;
int64 X2 = modpow(X, g, R); // 新的底数 X^g
// 化归 N < M
int64 N1 = N / M2, N2 = N % M2;
int64 full = geosum_pow(X2, M2, R).first; // sum_{v=0}^{M2-1} (X^g)^v
int64 ans = (N1 % R) * full % R;
ans = (ans + solve_coprime(A2, B1, N2, M2, X2, R)) % R;
ans = ans * modpow(X, B2, R) % R;
cout << ans << '\n';
}
return 0;
}复杂度分析
- 每个测试点：
- 空间复杂度：