余弦の博客

本文介绍了三个关于算法复杂度和应用的问题：第一个是求最大子序列和及其起止元素，第二个是二分查找的填空题，第三个是最大子序列和问题的进阶版本，强调在多个解中选择起始索引最小的解。文章指出，这些问题涉及动态规划和分治思想，适合用于巩固算法学习。

文章系统介绍了几种经典的组合博弈游戏及其获胜策略：斐波那契博弈中，若石子总数为斐波那契数，则先手必败；巴什博弈中，若n是(m+1)的倍数，则先手必败；威斯托夫博弈通过黄金比例与堆差判断必败态；尼姆博弈通过异或和判断胜负，异或和为0则先手必败；反尼姆博弈中，先手在特定条件下获胜。文章还介绍了SG函数及其在博弈分析中的核心作用，用于判断胜负状态。

本文记录了作者在学习数据结构课程过程中完成的MOOC课后习题，涵盖线性结构、二叉树、二叉搜索树、堆、图论、排序和哈希等核心内容，所有代码使用C++编写，部分题目结合STL简化实现。文章以每周问题集的形式系统总结了数据结构的理论与实践应用，兼具学习笔记与解题思路分享。

本文介绍了最小生成树问题及其经典解法Kruskal算法，重点讲解了通过并查集（Union-Find）高效实现连通性判断与合并的操作。文章结合三道HDU题（hdu1863、hdu1879、hdu1875）说明了该算法在实际问题中的应用，包括道路连接、村庄互通等场景，并强调了排序、并查集和贪心策略的结合是解决此类问题的核心思路。

文章记录了2020年蓝桥杯模拟省赛的题目及解题思路，包含填空题和编程题。其中第7题是关于“摆动序列”的计数问题，使用记忆化递归求解；第8题是螺旋矩阵问题，根据螺旋填充规则求指定位置的值；第9题是求最大覆盖面积的树形冲突问题，涉及圆的相交判断和最大权独立集；第10题是带权最小生成树问题，使用Prim算法求解。部分题目有注释和未验证的代码，整体反映了竞赛中的解题思路与实现方法。

本文介绍了动态规划（DP）的基本方法和解题思路，包括将递归问题转化为DP通过状态定义、状态转移方程和边界条件求解；强调了动态规划问题的两个关键特性：最优子结构和无后效性，并通过数三角形、背包问题、最长公共子序列和最长递增子序列等经典例题说明了DP的建模与求解过程。

本文介绍了图的基本概念、表示方法（邻接矩阵和邻接表）、图的遍历算法（DFS和BFS），以及图的连通性与强连通性。重点讲解了图的遍历过程、不同表示方式的优缺点，并详细说明了单源最短路径问题在无权图中的解决方法，即使用广度优先搜索（BFS）求解最短路径。

本文介绍了堆（Heap）和霍夫曼树（Huffman Tree）的基本概念与操作，以及集合中并查集（Union-Find）的应用。堆是一种完全二叉树结构，支持最大堆的插入、删除和建堆操作，建堆可在线性时间内完成；霍夫曼树是带权路径长度最小的二叉树，通过贪心策略构建，用于最优编码，实现压缩存储；并查集用于处理不相交集合的合并与查询问题。

本文介绍了段树（Segment Tree）在处理区间查询与更新问题中的应用，包括单点更新和区间最值查询，以及支持区间加法和乘法的复杂更新操作。通过懒标记（lazy tag）优化，段树能够高效处理范围更新与区间查询，支持多种操作如加法、乘法及混合操作，并强调了“先乘后加”的关键更新顺序。

本文介绍了二叉搜索树（BST）和AVL树（平衡二叉树）的基本概念、操作及实现方法。二叉搜索树通过节点值的大小关系组织结构，支持查找、插入和删除操作；AVL树通过维护节点平衡因子来保证树的高度为O(log n)，在插入或删除后通过旋转（RR、LL、LR、RL）保持平衡。文章还探讨了如何判断两个插入序列是否生成相同的BST，方法是构建一棵树并验证其他序列的查找路径是否仅经过已访问节点。