AtCoder Beginner Contest 440 题解
AtCoder Beginner Contest 440 题解
| 项目 | 内容 |
|---|---|
| 比赛时间 | 2026-01-10 |
| 比赛链接 | https://atcoder.jp/contests/abc440 |
| 题目数量 | A–G 共 7 题 |
比赛概览
本场整体难度中等偏基础。A、B 为送分题；C 题需要抓住"涂色以 为周期"的本质，把问题转化为环上的滑动窗口；D 是经典的"排序 + 二分计数"套路；E 题用优先队列按"最优解逐步妥协"的顺序枚举选法，较有思维含量；F 题先推出贪心结论，再用值域线段树支持动态修改，是数据结构与贪心结合的典型题；G 是全场最难的压轴题，需要把每层的连通块缩成点并做分层 DP，代码量大。值得重点掌握的是 C 的同余类合并、E 的"唯一父状态"枚举以及 G 的分层图 DP。
A - Octave
题目链接：https://atcoder.jp/contests/abc440/tasks/abc440_a
题目大意
声音每升高 个八度，频率翻一倍。给定一个频率为 Hz 的声音，问把它升高 个八度后频率变为多少 Hz。输入一行两个整数 ，约束 ，。输出一个整数（省略单位 Hz）。
思路
每升高 个八度频率乘 ，升高 个八度就要连乘 个 ，因此答案为
由于 最多为 ，答案最大为 ，用 int 就足够。实现方式有三种：
- 循环 次，每次把答案乘 ；
- 用移位运算
x << y（C++ 中1 << y即 ）； - 按 分三种情况输出 、、。
需要注意不要用 C 标准库的 pow 或 Python 的 math.pow，它们返回浮点数，可能有精度误差且输出格式不友好。整数运算即可解决。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int x, y;
cin >> x >> y;
cout << x * (1 << y) << '\n'; // 1 << y 即 2^y
return 0;
}官方题解还给出了 Python 写法：
x, y = map(int, input().split())
print(x * (2 ** y))复杂度分析
- 时间复杂度：
- 空间复杂度：
B - Trifecta
题目链接：https://atcoder.jp/contests/abc440/tasks/abc440_b
题目大意
匹马进行了一场比赛，所有马同时起跑，第 匹马用时 秒到达终点（所有 互不相同）。按名次从第 名到第 $3 名，输出这三匹马的编号。输入：第一行 ，第二行 ，约束 。
思路
用时最短的马是第 名。如果只问时间，排序 即可；本题问的是"马的编号"，所以把 与编号打包成二元组 ，按 升序排序后取前三个二元组中的编号即可：
很小，排序足够快。由于题目保证 互不相同，排序后的相对顺序不会出现并列问题，这是题目特意给出的便利。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<pair<int, int>> ti; // (用时, 编号)
for (int i = 0; i < n; i++) {
int t;
cin >> t;
ti.push_back({t, i + 1});
}
sort(ti.begin(), ti.end());
cout << ti[0].second << ' ' << ti[1].second << ' ' << ti[2].second << '\n';
return 0;
}官方题解还给出了 Python 写法：
n = int(input())
T = list(map(int, input().split()))
TI = []
for i in range(n):
TI.append((T[i], i + 1))
TI.sort()
print(TI[0][1], TI[1][1], TI[2][1])复杂度分析
- 时间复杂度：
- 空间复杂度：
C - Striped Horse
题目链接：https://atcoder.jp/contests/abc440/tasks/abc440_c
题目大意
有 个排成一行的方格，初始全为白色，把方格 涂成黑色的代价是 。执行一次如下操作：选择一个正整数 ，对所有满足
的方格 涂黑。求这次操作的最小总代价。有 组测试数据，，。
思路
关键观察 1：涂色状态只依赖 模 的余数。 条件中出现的只有 ，所以方格 和方格 的涂色状态完全相同。因此把下标模 相同的方格"合并"成一个槽位，槽位 （）的代价定义为
若某个余数没有对应的方格，则 。合并后每个槽位要么被涂要么不涂，被涂时的代价就是 。
关键观察 2：涂黑的是"环上的 个连续槽位"。 对每个周期来说， 恰好选中 个槽位；当 遍历 时， 可以取遍 ，于是被涂的 个槽位可以是环上任意一段连续的 个槽位。
于是问题转化为：在大小为 的环上，每个槽位有权值 ，求一段长度为 的连续槽位的权值和的最小值。这是经典滑动窗口：
- 把数组复制一份接到自己后面，得到长度为 的数组；
- 用前缀和（或滑动窗口）枚举每个起点 ，窗口 的和，取最小值。
正确性说明：合并同余类没有丢失信息——同一余数对应的方格涂黑状态必然一致，且它们各自独立累加代价；滑动窗口枚举了 的所有可能（即环上所有起点），所以取到的最小值就是答案。
易错点： 可能比 大（此时大部分槽位代价为 ，答案可能为 ）； 是 起始，取模时要正确处理；答案可能很大（ 之和可达 ），要用 long long。
参考代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, w;
cin >> n >> w;
vector<ll> c(n);
for (auto &v : c) cin >> v;
int m = 2 * w; // 周期长度
vector<ll> cost(m, 0);
for (int i = 0; i < n; i++) cost[i % m] += c[i];
// 环上长度为 w 的滑动窗口
vector<ll> b(2 * m);
for (int i = 0; i < 2 * m; i++) b[i] = cost[i % m];
ll cur = 0;
for (int i = 0; i < w; i++) cur += b[i];
ll best = cur;
for (int i = w; i < m + w - 1; i++) {
cur += b[i] - b[i - w]; // 窗口整体右移一格
best = min(best, cur);
}
cout << best << '\n';
}
return 0;
}复杂度分析
- 时间复杂度：每个测试 ，总体
- 空间复杂度：
D - Forbidden List 2
题目链接：https://atcoder.jp/contests/abc440/tasks/abc440_d
题目大意
有一个包含 个互不相同的整数的列表 。有 个询问，每个询问给定 ，求"大于等于 且不在列表 中的整数"中第 小的一个。约束 ，。
思路
先把 排序（顺序不影响答案），此后默认 。对询问 ：
- 用二分（
lower_bound）找到第一个不小于 的元素，设其下标为 。 - 对某个下标 ，考察区间 （含两端）。区间内共有 个整数，其中属于 的有 共 个，所以"好数"（大于等于 且不在 中）的个数为
随 增大而单调不减，因此可以二分找最小的 使得 。
3. 设该最小下标为 。此时区间 内好数严格少于 ，而 内好数不少于 ，所以答案位于 与 之间（不含两端）。若记答案为 ，那么 内恰有 个属于 的元素（即 ），于是
边界情况：若对所有 都有 ，说明第 个好数比所有 都大，此时取 ，上面的公式依然成立（ 内属于 的元素就是 共 个）。
答案最大约为 ，接近 ，应使用 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, q;
cin >> n >> q;
vector<ll> a(n);
for (auto &v : a) cin >> v;
sort(a.begin(), a.end());
while (q--) {
ll x, y;
cin >> x >> y;
// s = 第一个 >= x 的下标
int s = lower_bound(a.begin(), a.end(), x) - a.begin();
// 找最小的 t 使得 (a[t] - x + 1) - (t - s + 1) >= y
int lo = s, hi = n - 1, t = n;
while (lo <= hi) {
int mid = (lo + hi) / 2;
ll good = (a[mid] - x + 1) - (ll)(mid - s + 1);
if (good >= y) {
t = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
cout << x + (y - 1) + (ll)(t - s) << '\n';
}
return 0;
}复杂度分析
- 时间复杂度：
- 空间复杂度：
E - Cookies
题目链接：https://atcoder.jp/contests/abc440/tasks/abc440_e
题目大意
有 种曲奇，每种都有 个，第 种每个的美味度为 。从这些曲奇中选出总共 个（只关注每种选了多少个），一共有 种选法。对每种选法，求和得到美味度总和 。把所有 从大到小排列（相同的值算多次），输出前 个。约束 ，，，。
思路
先把 按从大到小排序，记 。一种选法用计数向量 表示，其中 是选第 种的个数，满足 。美味度总和为 。
关键观察 1：最优选法是一切从"全选第 1 种"开始。 显然 个全选第 1 种时总和最大，为 。
关键观察 2：定义"一步妥协"操作。 从选法 出发，选择某个 （要求 ），把第 种的一个曲奇换成第 种，得到
由于 ，一步妥协后的总和 不会变大。因此按总和降序枚举时，必须先处理原选法，才能处理它的妥协选法。另一方面，任何选法都可以从"全选第 1 种"出发，经过有限次一步妥协得到（把曲奇不断从前面移到后面即可）。于是可以用优先队列模拟：
- 初始把 （总和 ）入队；
- 每次弹出总和最大的选法并输出，然后生成它所有的一步妥协选法入队；
- 注意用集合去重，避免同一个选法被多次入队。
每个弹出的选法至多生成 个孩子，因此前 个可以 求出来。这是官方题解给出的基本做法。
更好的做法（官方 bonus，无去重）：给每个选法指定唯一的"父选法"。 对状态 （不是全选第 1 种的状态），令 为最靠右的满足 的下标，定义其父状态为"把位置 的一个曲奇还给位置 "，即
可以验证（分 与 两种情况讨论），这个父状态恰好是唯一一个能通过一步妥协到达 的状态——因为一步妥协把曲奇右移，而"把最右非零分量往左拉一个"是它的逆操作，且逆操作唯一。于是从根 出发，每个状态恰好被生成一次，无需去重。
生成规则（设 为最右非零位置）：
- 孩子 A：若 ，把位置 的一个曲奇移到 ，总和变化
- 孩子 B：若 ，把位置 的一个曲奇移到 ，总和变化
正确性论证：每个非根状态有唯一的父状态，所以从根出发的生成树覆盖所有状态且不重复；每条边（从父到子）总和单调不增；优先队列按总和从大到小弹出，因此第 次弹出的就是第 大的总和。这个论证与官方题解中"优先队列模拟 + 去重"的思路完全一致，只是省掉了去重这一步。
注意：总和可能为负（ 允许为负），但只要优先队列按降序比较即可；相同的总和出现多次时照常输出（见样例 2）。
参考代码
#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, x;
cin >> n >> k >> x;
vector<ll> a(n);
for (auto &v : a) cin >> v;
sort(a.rbegin(), a.rend()); // 降序
// 状态：(美味度总和, 计数向量)
using State = pair<ll, vector<ll>>;
priority_queue<State> pq;
vector<ll> init(n, 0);
init[0] = k;
pq.push({k * a[0], init});
while (x--) {
auto [sum, c] = pq.top();
pq.pop();
cout << sum << '\n';
int r = -1; // 最右的非零位置
for (int i = n - 1; i >= 0; i--) {
if (c[i] > 0) { r = i; break; }
}
// 孩子 A：把 r-1 的一个曲奇移到 r
if (r >= 1 && c[r - 1] > 0) {
auto c2 = c;
c2[r - 1]--; c2[r]++;
pq.push({sum + a[r] - a[r - 1], c2});
}
// 孩子 B：把 r 的一个曲奇移到 r+1
if (r + 1 < n) {
auto c2 = c;
c2[r]--; c2[r + 1]++;
pq.push({sum + a[r + 1] - a[r], c2});
}
}
return 0;
}复杂度分析
- 时间复杂度：（每次弹出生成至多 2 个孩子，每次压入/弹出涉及 大小的向量比较与拷贝）
- 空间复杂度：（优先队列中至多 个状态，每个状态 ）
F - Egoism
题目链接：https://atcoder.jp/contests/abc440/tasks/abc440_f
题目大意
有 匹马，第 匹有心情值 与整洁度 。每天晚上 匹马按某个顺序 洗澡，第 匹的满意度为 ，之后第 匹的满意度为 （即自己的心情乘以前一匹的整洁度）。给定 次修改，每次把第 匹马的心情改为 、整洁度改为 ，然后问：在可以任意安排顺序的前提下，这一晚总满意度的最大值。约束 ，。
思路
问题转化。 对任意排列，把第 位马的"权重"定义为其前一匹马的整洁度（第 1 位的权重固定为 ）。总满意度就是
也就是说，被赋予权重 的马贡献 ，被赋予权重 的马贡献 。记 ，则答案形如 ，其中 是"被赋予权重 的马的心情值之和"。
权重为 1 的位置结构。 设整洁度为 的马有 匹，位置为 。则权重为 的位置包括：第 位，以及每一匹整洁度 的马的后一位（若该马不是最后一匹）。于是权重为 1 的位置共有 个或 个，取决于最后一匹马是不是整洁度 。
官方有一个关键结论：只需考虑"最后一匹马整洁度为 1"的排列。 若最后一匹马整洁度为 （记其位置为 ），考虑把马按新顺序 重排：除原第 位的马（其前驱从"无"变成整洁度为 的马，权重从 升为 ）与原第 位的马（新顺序下变成第 1 位，权重仍为 ）之外，其余马的权重都不变（它们的前驱不变）。所以这个重排不会降低总满意度，且新顺序的最后一匹马是 ，整洁度为 。因此只用分析下面三种情况。
(1) ：所有马整洁度都是 。 此时只有第 位权重为 ，其余全部权重为 。最优是把心情最小的马放在第 位，答案
(2) ：所有马整洁度都是 。 所有位置权重都为 ，答案就是 。
(3) 。 只考虑 case 2 型排列（最后一匹整洁度为 ）。此时权重为 的位置恰有 个。设这些位置上的马构成集合 。有两个子结论：
- 中必须包含至少一匹整洁度为 的马。 设整洁度为 的马第一次出现的位置为 ：若 ，则第 1 位（权重 1）就是整洁度 2 的马；若 ，则位置 是整洁度 1 的马，所以位置 的权重为 1，而它整洁度为 2。因此总有一匹整洁度 2 的马权重为 1。
- 反过来，任意含至少一匹整洁度 2 马的 元集合 都能实现。 记 为"整洁度 且要求权重 "的马的集合，此时 ，且 。按如下顺序排列即可实现所有要求：先放 个 的元素，再放全部 的元素，再放 个 的元素，然后交替放 组（ 元素、 元素），最后放全部 的元素。逐位检查可知每个位置要求的权重都恰好实现。
因此答案是
其中 取遍"含有至少一匹整洁度 2 马"的 元子集。设 为全局 最小的 匹马组成的集合（并列时任意取）：
- 若 中已含有整洁度 的马，则取 ，扣除量为 ；
- 若 全是整洁度 ，则从 中移除 最大的一匹（整洁度 1），再加入整洁度 的马中 最小的一匹，扣除量为
动态维护。 修改会改变某匹马的心情与整洁度，、 都会变。由于 的值域只有 ，可以用值域线段树维护。线段树每个节点（对应值域区间）保存三个信息：（该值域内整洁度 1 的马的个数）、（整洁度 2 的马的个数）、（该值域内所有马的 之和）。配合三个操作：
find_zth(z)：二分找最小的值 ，使得 的马不少于 匹；- 查询 上的 ；
find_first2()：找最小的 值，使得该值上存在整洁度为 的马（即 的马中 的最小值）。
设 、、 分别是 上的总和、马数、整洁度 2 的马数。前 小的马由"所有 的马"加上"若干匹 的马"组成，其总和为
若 ，说明前 小里可以含整洁度 2 的马，扣除量就是这个值；否则需要换掉最大的一匹（其值为 ）并加入最小整洁度 2 的马（其值为 ），扣除量为
最后特判 （全部整洁度 2，扣除 ）与 （全部整洁度 1，扣除 ）。实现时令 可统一处理 的情况。
参考代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXV = 1000000; // A_i 的上界
struct Node {
ll sum;
int c1, c2;
};
Node mergeNode(Node a, Node b) {
return {a.sum + b.sum, a.c1 + b.c1, a.c2 + b.c2};
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n), b(n);
int SZ = 1;
while (SZ <= MAXV) SZ <<= 1;
vector<Node> seg(2 * SZ, {0, 0, 0});
ll totalSum = 0;
int total1 = 0, total2 = 0;
auto update = [&](int pos, int dc1, int dc2, ll dsum) {
int v = SZ + pos;
seg[v].sum += dsum;
seg[v].c1 += dc1;
seg[v].c2 += dc2;
for (v >>= 1; v; v >>= 1) seg[v] = mergeNode(seg[v << 1], seg[v << 1 | 1]);
};
auto queryPrefix = [&](int r) {
// 返回 [0, r] 的信息
int l = SZ, rr = SZ + r + 1;
Node res = {0, 0, 0};
while (l < rr) {
if (l & 1) res = mergeNode(res, seg[l++]);
if (rr & 1) res = mergeNode(res, seg[--rr]);
l >>= 1;
rr >>= 1;
}
return res;
};
auto findZth = [&](int z) {
// 最小的值 v，使得 A <= v 的元素个数 >= z
int v = 1;
while (v < SZ) {
int cnt = seg[v << 1].c1 + seg[v << 1].c2;
if (cnt >= z) v <<= 1;
else { z -= cnt; v = v << 1 | 1; }
}
return v - SZ;
};
auto findFirst2 = [&]() {
// 最小的 A 值，该值上存在整洁度为 2 的马
int v = 1;
while (v < SZ) {
if (seg[v << 1].c2 > 0) v <<= 1;
else v = v << 1 | 1;
}
return v - SZ;
};
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
totalSum += a[i];
if (b[i] == 1) { total1++; update(a[i], 1, 0, a[i]); }
else { total2++; update(a[i], 0, 1, a[i]); }
}
while (q--) {
int w, x, y;
cin >> w >> x >> y;
--w;
// 删除旧属性
totalSum -= a[w];
if (b[w] == 1) { total1--; update(a[w], -1, 0, -(ll)a[w]); }
else { total2--; update(a[w], 0, -1, -(ll)a[w]); }
// 写入新属性
a[w] = x;
b[w] = y;
totalSum += a[w];
if (b[w] == 1) { total1++; update(a[w], 1, 0, a[w]); }
else { total2++; update(a[w], 0, 1, a[w]); }
ll minus; // 需要从 2*totalSum 中扣除的部分
if (total2 == 0) {
// 全部整洁度 1，权重全为 1
minus = totalSum;
} else {
int z = max(1, total1); // 权重为 1 的马的数量
int r = findZth(z); // 前 z 小的阈值
Node nd = queryPrefix(r);
if (nd.c2 > 0) {
minus = nd.sum - (ll)r * (nd.c1 + nd.c2 - z);
} else {
int bi = findFirst2();
minus = nd.sum - (ll)r * (nd.c1 + nd.c2 - z + 1) + bi;
}
}
cout << 2 * totalSum - minus << '\n';
}
return 0;
}复杂度分析
- 时间复杂度：，其中
- 空间复杂度：
G - Haunted House
题目链接：https://atcoder.jp/contests/abc440/tasks/abc440_g
题目大意
有一座 层的鬼屋，每层是 的网格。单元格 是数字（表示该格有若干金币，数字即金币数）或 #（墙）。你可以从空格移动到同层相邻空格、从 向上移动到 （若为空），以及从 向下移动到 （仅当 上放了梯子）。对于每个询问：选择一个空格放梯子，然后从 出发自由移动，求访问过的所有格子金币总数（重复访问不重复计数）的最大值。约束 ，，。
思路
第一步：分层图建模。 在一层内部可以自由移动的只有由空格组成的连通块，因此把每一层用并查集缩成若干"点"（连通块）。点 上的金币数 是块内所有数字之和。层与层之间，只要同一 位置在相邻两层都为空，就在对应的两个连通块之间形成一条"向上"边（向上移动免费）。向下移动必须借助唯一的一把梯子，即梯子相当于把某一对相邻层之间的某条向上边变成"双向边"。
第二步：没有梯子时只有"纯向上链"。 由于不能向下，从 层的 出发只能沿向上边一路走，且每层最多进入一个连通块。记 为 在下一层的可到达连通块集合，则
其中 表示"不用梯子（或梯子完全用不上）"时能收集的最大金币数。
第三步：一把梯子带来一次"之字形"。 梯子放在某层 （连通块 ）与其上一层 （连通块 ）之间，使 双向可达。此时最优路径的形态是：先沿向上链到达 ，从 下到 ，再从 升回 层的某个 （ 是 的某个向上邻居，可能仍是 ），之后继续纯向上。注意 的向上邻居可能有多个，但除 外每个都是一次性"有去无回"的，所以至多额外多覆盖一个 层的连通块。
第四步：DP 定义与转移。 从最上层向下逐层处理，设：
- ：从 层 出发，不用梯子，纯向上链的最大值；
- ：从 层 出发，梯子放在 层及以上的最大金币数；
- ：从 层 出发，升到 层的 ，之后不再用梯子：
- ：从 层 出发，利用 层的梯子下到 ，再升回 层的最佳 ，之后不再用梯子。若 ， 的金币已经算过，不能再加 ：
- ：从 层 出发、先下后上的之字形最大值。
最后用之字形更新 ：从 层 升到 ，再从 做一次之字形。若之字形下到的恰好是 本身，则 的金币已计入，不重复加：
顶二技巧。 需要枚举所有 ，但只需取 中按值排序后的前两名：第一名若恰为 ，则 的最佳选择就是第二名。同理 的更新也只需 的前两名。这样每条边都能 转移。
第五步：回答询问。 对询问 ，设起点所在连通块为 ，答案取三种情况的较大者：
三者分别对应：梯子放在完全用不上的位置（纯向上链）、梯子放在 层及以上的某个边界（先向上后做之字形）、梯子放在 层与 层之间（起点直接先向下）。若 ，第三项不存在，视为 即可。
易错点：金币非负，所以"能到就全收"是最优的；重复访问不重复计金币，因此连通块合并时只需把金币求和一次；之字形转移时要注意避免同一连通块金币被重复累加（即上面 、 的特殊分支）。
参考代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p;
DSU(int n) : p(n) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a != b) p[a] = b;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int F, H, W;
cin >> F >> H >> W;
vector<vector<string>> s(F, vector<string>(H));
for (int k = 0; k < F; k++)
for (int i = 0; i < H; i++) cin >> s[k][i];
int V = H * W;
vector<vector<bool>> pass(F, vector<bool>(V, false));
for (int k = 0; k < F; k++)
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++)
if (s[k][i][j] != '#') pass[k][i * W + j] = true;
// 每层内部连通块
vector<DSU> dsu;
for (int k = 0; k < F; k++) {
DSU d(V);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
int id = i * W + j;
if (!pass[k][id]) continue;
if (i > 0 && pass[k][id - W]) d.merge(id, id - W);
if (j > 0 && pass[k][id - 1]) d.merge(id, id - 1);
}
}
dsu.push_back(d);
}
// 连通块金币和、是否为根
vector<vector<ll>> csum(F, vector<ll>(V, 0));
vector<vector<bool>> isroot(F, vector<bool>(V, false));
for (int k = 0; k < F; k++) {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
int id = i * W + j;
if (!pass[k][id]) continue;
int r = dsu[k].find(id);
csum[k][r] += s[k][i][j] - '0';
isroot[k][r] = true;
}
}
}
// 相邻层的重叠关系（去重后）
vector<vector<vector<int>>> up(F, vector<vector<int>>(V));
vector<vector<vector<int>>> down(F, vector<vector<int>>(V));
for (int k = 0; k < F; k++) {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
int id = i * W + j;
if (!pass[k][id]) continue;
int r = dsu[k].find(id);
if (k + 1 < F && pass[k + 1][id]) {
int r2 = dsu[k + 1].find(id);
up[k][r].push_back(r2);
down[k + 1][r2].push_back(r);
}
}
}
}
for (int k = 0; k < F; k++) {
for (int v = 0; v < V; v++) {
sort(up[k][v].begin(), up[k][v].end());
up[k][v].erase(unique(up[k][v].begin(), up[k][v].end()), up[k][v].end());
sort(down[k][v].begin(), down[k][v].end());
down[k][v].erase(unique(down[k][v].begin(), down[k][v].end()), down[k][v].end());
}
}
vector<vector<ll>> dp0(F, vector<ll>(V, 0));
vector<vector<ll>> dp1(F, vector<ll>(V, 0));
vector<vector<ll>> up1(F, vector<ll>(V, 0));
vector<vector<vector<pair<ll, int>>>> dv0(F, vector<vector<pair<ll, int>>>(V));
vector<vector<vector<pair<ll, int>>>> dv1(F, vector<vector<pair<ll, int>>>(V));
for (int k = F - 1; k >= 0; k--) {
// 纯向上链
for (int v = 0; v < V; v++) {
if (!isroot[k][v]) continue;
ll best0 = 0, best1 = 0;
for (int u : up[k][v]) {
best0 = max(best0, dp0[k + 1][u]);
best1 = max(best1, dp1[k + 1][u]);
}
dp0[k][v] = csum[k][v] + best0;
dp1[k][v] = csum[k][v] + best1;
}
if (k + 1 < F) {
// dv0: [k] 出发升到 [k+1]
for (int v = 0; v < V; v++) {
if (!isroot[k][v]) continue;
for (int u : up[k][v])
dv0[k][v].push_back({csum[k][v] + dp0[k + 1][u], u});
sort(dv0[k][v].rbegin(), dv0[k][v].rend());
}
// dv1 / up1: [k+1] 出发先下到 [k] 再升回
for (int v = 0; v < V; v++) {
if (!isroot[k + 1][v]) continue;
ll c = csum[k + 1][v];
for (int u : down[k + 1][v]) {
ll best = 0;
int m = min(2, (int)dv0[k][u].size());
for (int i = 0; i < m; i++) {
ll add = dv0[k][u][i].first;
int w = dv0[k][u][i].second;
if (w == v) best = max(best, add);
else best = max(best, c + add);
}
up1[k + 1][v] = max(up1[k + 1][v], best);
dv1[k + 1][v].push_back({best, u});
}
sort(dv1[k + 1][v].rbegin(), dv1[k + 1][v].rend());
}
// 用之字形更新 dp1[k]
for (int v = 0; v < V; v++) {
if (!isroot[k][v]) continue;
ll c = csum[k][v];
for (int u : up[k][v]) {
int m = min(2, (int)dv1[k + 1][u].size());
for (int i = 0; i < m; i++) {
ll add = dv1[k + 1][u][i].first;
int w = dv1[k + 1][u][i].second; // 之字形下到的 [k] 层连通块
if (w == v) dp1[k][v] = max(dp1[k][v], add);
else dp1[k][v] = max(dp1[k][v], c + add);
}
}
}
}
}
int Q;
cin >> Q;
while (Q--) {
int g, a, b;
cin >> g >> a >> b;
--g; --a; --b;
int r = dsu[g].find(a * W + b);
cout << max({dp0[g][r], dp1[g][r], up1[g][r]}) << '\n';
}
return 0;
}复杂度分析
- 时间复杂度：（建图 ，每层对的排序总代价 ，转移对每条边 ）
- 空间复杂度：
（本场题目均有官方题解，本文思路以上述官方题解为核心重新组织并补充了细节推导。）