当前位置：首页 > news >正文

2026ACM训练日记

news 2026/4/15 0:15:47

天梯赛
- 2026.4.15
  - L2-001 紧急救援
  - L2-002 链表去重
  - L2-003 月饼
  - L2-004 这是二叉搜索树吗？
  - L2-005 集合相似度
  - L2-006 树的遍历

天梯赛

2026.4.15

L2-001 紧急救援

链接：https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805073643683840&page=1

题面：单源最短路，含边权（距离）和点权（救援队数）。求最短路径条数，并在最短路径中输出点权和最大的一条路径。

做法：Dijkstra 扩展。维护 dis, num (路径数), cnt (最大点权和), pre (前驱)。松弛时，若 dis[u] + w < dis[v]，更新 dis、覆盖 cnt 和 num 并记录 pre；若 dis[u] + w == dis[v]，累加 num，并尝试用较大的 cnt[u] + a[v] 去更新 cnt[v] 和 pre。最后利用 pre 回溯输出路径即可。

L2-002 链表去重

链接：https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805072641245184&page=1

题面：给定静态链表，删除键值绝对值重复的节点，保留首次出现的节点，并将被删除节点按序组成新链表输出。

做法：静态数组模拟链表。开一个 vis 数组记录绝对值是否出现过。顺着头结点的 next 遍历原链表，根据 vis 状态将当前节点地址分别 push_back 到两个 vector 中。重组时无需修改原 next 指针，直接按 vector 顺序输出相邻元素即可（注意地址使用 %05d 格式化）。

L2-003 月饼

链接：https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805071789801472&page=1

题面：分数背包问题。给定各物品总量、总价值与背包容量，求最大价值。

做法：考虑贪心。算出单价按降序排序，优先装单价高的，最后不足的按比例拆分。

坑点：题目中的“正数”包含浮点数！输入存在小数，必须使用 double 及 cin/scanf，不能使用仅支持整数的快读模板。

L2-004 这是二叉搜索树吗？

链接：https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805070971912192&page=1

题面：判断给定序列是否为合法 BST 或其镜像的前序遍历，若是则输出后序遍历。

做法：利用前序首位为根的特性，双指针夹击划分左右子树。i 从前往后找第一个 \(\ge\) 根的（右子树起点），j 从后往前找第一个 \(<\) 根的（左子树终点）。若合法必有 i - j == 1，否则直接 return 阻断。合法则继续递归 [L+1, j] 和 [i, R]，回溯时将根压入后序数组。若最终后序数组大小等于 \(N\) 则树合法。

L2-005 集合相似度

链接：https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805070149828608&page=1

题面：多次查询两集合的相似度 \(|A \cap B| / |A \cup B|\)。

做法：std::set 去重存图。由容斥原理得 \(|A \cup B| = |A| + |B| - |A \cap B|\)。为避免动态开辟集合的巨大常数开销，每次查询仅需遍历 \(size\) 较小的集合，去较大的集合里查 find()，统计出交集大小 \(cnt\) 后，\(O(1)\) 算出并集大小求解即可。时间复杂度降维至 \(O(K \cdot \min \log \max)\)。