蓝桥杯C++/C语言算法竞赛笔记与解析

"这份资料是关于蓝桥杯C++/C语言竞赛的，包含了研究生组、A组、B组的真题和算法编程练习，由闫学灿(y总)精心整理，部分题目附有注释。建议在学习过程中结合www.acwing.com网站上的Y总视频讲解，对于算法学习和准备蓝桥杯比赛有很大帮助。" 在这份资料中，主要涉及的知识点包括： 1. **时间复杂度**：理解不同复杂度如O(n)，O(n^2)，O(logN)和O(nm)的含义，以及如何分析算法的时间复杂度。在蓝桥杯竞赛中，需要注意算法的时间复杂度是否超过评测机的处理能力，例如C++评测机大约每秒能运行一亿次操作，如果时间复杂度超过10^8，算法可能会超时。 2. **C++编译选项**：在Dev-C++中，如果需要使用`cstdio`中的`scanf`和`printf`，需要添加`-std=c++11`编译选项。 3. **递归**： - **斐波那契数列**：展示了递归实现斐波那契数列的方法，但需要注意递归深度可能导致效率低下。 - **递归搜索树**：任何递归问题都可以通过构建递归树来理解。 - **递归恢复现场**：在递归过程中，需要确保在回溯时恢复之前的状态，例如在选择问题中，递归时应处理各种可能的选择情况。 4. **指数型枚举**：递归可以用于实现指数型枚举，例如在选择问题中，先决定是否选择某个元素，然后递归处理剩余的部分。 5. **状态记录**：使用数组`st`记录每个位置的状态，例如0表示未考虑，1表示选择，2表示不选择，这是动态规划或回溯法中的常见技巧。 6. **边界条件**：在递归函数中，通常需要设置边界条件，如在示例中，当`u > n`时递归终止。 7. **回溯法**：在递归过程中，通过改变状态并尝试不同的路径，当发现无法达到目标时回溯到上一步，尝试其他选择。在递归实现中，可以使用`dfs`（深度优先搜索）来实现回溯。 这份资料对于准备蓝桥杯竞赛的选手来说是一份宝贵的资源，它不仅包含了实际的编程练习，还提供了算法理解和优化的思路。通过结合视频讲解，学习者可以更深入地掌握C++/C语言编程和算法应用。