比赛:JIJ Programming Contest 2026(AtCoder Beginner Contest 476)
比赛时间:2026-09-19 20:00 ~ 21:40
比赛时长:100 分钟
比赛概况
这场 ABC 476 一共 7 道题,这里总结了前五题:
| 题目 | 名称 | 分值 | 核心知识点 |
|---|---|---|---|
| A | Appender | 100 | 字符串、分类讨论 |
| B | Wild Card | 200 | 字符串匹配、通配符 |
| C | Third Largest Number | 300 | multiset、动态维护 |
| D | Automat | 425 | 排序、前缀和、二分 |
| E | Min-Max Swap | 450 | 线段树、区间最值 |
Problem A - Appender
题意简述: 给定一个字符串
1 | // Problem: A - Appender |
Problem B - Wild Card
题意简述: 给定长度为
解题思路: 逐位比较两个字符串:
- 如果
,当前字符匹配,继续检查。 - 如果不相等,我们需要看
是否是通配符 '*'。 - 如果是,它可以充当
,我们直接 continue。如果既不相等, 也不是 '*',说明无法匹配,直接输出 No。 如果循环顺利结束,则说明完全匹配,输出 Yes。时间复杂度:
1 | // Problem: B - Wild Card |
Problem C - Third Largest Number
题意简述: 给定一个长度为
解题思路: 我们需要一个能够动态维护一组数字并快速查询其排名的数据结构。在 C++ 中,std::multiset 是一个绝佳的选择。 为了方便找“第
1 | // Problem: C - Third Largest Number |
Problem D - Automat
解题思路: 这道题相对复杂,结合了贪心、前缀和以及二分查找。 从代码逻辑来看,主要涉及使用两种不同的预算(
核心步骤:
- 排序与前缀和预处理: 为了最大化购买数量,我们贪心地优先购买价格便宜的物品,因此先对数组
和 进行升序 sort,并计算它们的前缀和。同时计算了数组 按 划分的消耗前缀和 cb。 - 二分查找: 主逻辑中使用二分查找(while(l < r))来快速定位在给定的预算
下最多能购买多少个 类物品。 - 分情况枚举: 在能够购买一部分
物品的基础上,枚举剩余预算的分配策略,结合除法取模判断如何利用打包机制(代码中的 sum <= yy * k 分支),再利用嵌套的二分查找在 的前缀和 cb 上确定 类物品的最大购买量。本题的细节较多,边界条件的把控(如剩余物品的继续二分查找)非常考验代码基本功。
1 | // Problem: D - Automat |
Problem E - Max-Min Swap Segment Tree
题意简述: 给定一个长度为
解题思路: 这题是典型的数据结构题,非常适合用线段树 (Segment Tree) 来解决。 由于我们需要交换最大值和最小值,线段树的每个节点不仅需要维护区间最大值 (vmax) 和最小值 (vmin),还必须维护它们在原数组中的对应下标 (idx1 和 idx2)。
实现细节:
- 建树 (build) & 上传 (pushup):叶子节点记录自身的索引和值。父节点在 pushup 时不仅取子节点的最值,还将对应最值的索引一并继承上来。
- 区间查询 (query1, query2):分别编写了查询区间最大值和最小值的函数。返回值是一个 pair<int, int>,包含最值以及它的下标。
- 单点修改 (modify):当我们通过查询得到了区间
内的最大值 v1 和最小值 v2 后,只需调用两次单点修改:modify(1, v1.second, v2.first); (把原最大值位置设为最小值)modify(1, v2.second, v1.first); (把原最小值位置设为最大值) - 输出结果:最后再对每一个位置进行一次单点查询即可输出最终数组。操作的时间复杂度为
,建树为 ,总体时间复杂度完全在两秒的限制内。
1 |
|