在前面的文章中，我们介绍了 C++ Standard Template Library (STL) 中的通用算法库 <algorithm>。掌握了这些常用算法后，我们已经能够写出非常高效的数据处理代码。 然而，在实际参加信奥竞赛（如 CSP-J/S、NOIP 等）时，仅仅写出逻辑正确的代码是不够的。信奥比赛有一条极其严格的硬性规定：程序必须通过文件进行数据的输入与输出。 如果...

CSP-J 2023真题“公路”是一道典型的贪心算法题。本题要求计算出在不同站点油价不同的情况下，从起点行驶到终点的最小花费。适合 GESP 四级及以上考生练习，难度⭐⭐，洛谷难度等级普及-。 P9749 [CSP-J 2023] 公路 题目要求 题目描述 小苞准备开着车沿着公路自驾。 公路上一共有 $n$ 个站点，编号为从 $1$ 到 $n$。其中站点 $i$ 与站点 $i ...

在前面的文章中，我们介绍了 C++ STL 中的各种容器。在实际编写程序和参加竞赛时，仅存储数据是不够的，通常还需要对数据进行各种操作，例如： 将学生的成绩按照从高到低排序（sort）； 去掉数组中重复的数据（unique）； 在排好序的数据中用二分法快速查找某个数（lower_bound / upper_bound）； 将一串字符或数组的内容颠倒顺序（reverse）；...

CSP-J 2022真题-解密，是一道结合数学推导与数值运算的经典题目。本题可以通过将方程组转化为一元二次方程，利用求根公式在 $O(1)$ 的时间内求解；也可以利用单调性通过二分法进行求解。适合 GESP 四级及以上考生练习，难度⭐⭐，洛谷难度等级普及-。 P8814 [CSP-J 2022] 解密 题目要求 题目描述 给定一个正整数 $k$，有 $k$ 次询问，每次给定三个正...

上一篇文章我们介绍了 set 和 multiset，它们通过底层的红黑树实现自动去重、自动排序，以及在 $O(\log n)$ 时间内进行查找的机制。 但是，set 只能存放单一的元素（也就是 键 Key）。在很多实际的信奥问题或开发场景中，我们需要的是一种“对应关系”。例如： 给你一个学生的名字（Key），你需要快速查出他的信奥成绩（Value）； 给你一个英文单词（Key）...

CSP-J 2022真题-乘方，是一道基础模拟与数值溢出处理的考点。重点考察如何在指数运算中安全地进行溢出判断，以及如何针对特殊边界（如 $a=1$）进行优化以避免超时。适合GESP二级及以上考生练习，难度⭐，洛谷难度等级入门。 P8813 [CSP-J 2022] 乘方 题目要求 题目背景 为模拟赛时得分情况，本题时限降低 50%。 题目描述 小文同学刚刚接触了信息学竞赛，...

上一篇文章我们拆解了 deque 双端队列，并以此告别了“序列容器”的世界。在之前的文章中，无论是 vector、stack、queue 还是 deque，元素都是按照我们 插入的顺序 排列的。如果想要查找某个元素是否存在，在没有排序的情况下，我们只能从头到尾挨个找，时间复杂度是 $O(n)$。 如果我们需要一个容器，能 自动帮我们去重、排序，并且在 极短的时间内（比如 $O(\log n...

CSP-J 2019真题-纪念品，完全背包动态规划考点，重点考察如何将看似复杂的“跨天交易与长期持有”问题，优雅地拆解为每日独立的“当日买入、明日卖出”的完全背包问题。适合GESP六级及以上考生练习，难度⭐⭐⭐☆，洛谷难度等级普及+/提高。 P5662 [CSP-J 2019] 纪念品 题目要求 题目描述 小伟突然获得一种超能力，他知道未来 $T$ 天 $N$ 种纪念品每天的价格...

上一篇文章介绍了 stack 和 queue，它们本质上是容器适配器，底层默认使用的容器就是 deque。我们提到 deque 能同时做到头尾操作 $O(1)$ 和下标随机访问 $O(1)$，比 vector 灵活得多。 这篇文章就来拆解 deque 的内部结构，看看它是怎么做到这些的。 往期回顾： 第一部分【计算机历史】系列文章合集（共8篇） 第二部分【C++的奇妙之旅...

上一篇文章我们介绍了 vector 动态数组。vector 支持末尾追加、下标随机访问、中间插入删除等操作，功能非常灵活。 既然 vector 已经足够通用，为什么 STL 中还要专门提供 stack（栈）和 queue（队列）？ 这就引出了软件工程中一个重要的设计思想：主动限制权限。在”撤销操作”或”排队处理”等场景中，过于自由的接口反而容易导致数据被意外修改。如果从接口层面关闭随机访...