本文档是关于“复杂度”主题的题目集，包含三个问题：最大子列和问题（基本要求）、最大子序列和问题（考研真题，难度较高）以及二分查找（函数填空题）。每个题目均涉及算法设计与实现，重点考察动态规划、分治思想及边界处理，其中部分测试点易错，需特别注意。

文章系统总结了若干经典博弈问题及其必败态判定方法：斐波那契博弈中当石子数为斐波那契数时先手必败；巴什博弈中当n是m+1的倍数时先手必败；威佐夫博弈通过黄金分割比判断必败态；尼姆博弈中异或和为0则先手必败；反尼姆博弈中在特定条件下先手可必胜；通用SG函数可将任意公平组合游戏转化为Nim博弈，通过mex运算求解状态值，最终胜负由各子游戏SG值异或和决定。

本文是作者在学习浙大数据结构课程过程中，系统整理和记录的PTA题目集，涵盖线性结构、二叉树、图、排序、散列查找等核心数据结构与算法内容，每部分均包含题目解析与代码实现，结合C++和C语言编写，并使用STL简化部分操作，最终完成了全部课后习题的总结与学习复盘。

文章介绍了最小生成树（MST）问题，重点讲解了Kruskal算法和Prim算法两种求解方法。Kruskal算法通过按边权排序并使用并查集判断连通性来构造MST，效率高且易于实现；Prim算法则从一个节点出发，逐步扩展生成树，类似Dijkstra算法。文章结合多道经典题目（如HDU1863、1879、1875及洛谷P3366）说明了这两种算法的应用场景和解题思路。

文章总结了2020年蓝桥杯模拟省赛的题目及解题思路，涵盖填空题和9道编程题，涉及组合数学、字符串处理、摆动序列、螺旋矩阵、圆面积最大化、最小生成树等知识点，其中部分题目使用了记忆化递归、Prim算法等方法，最后一题因是现场学习算法而未完全熟练，反映出作者在图论和动态规划方面的提升空间。

文章系统介绍了动态规划（动规）的基本思想与解题方法，包括从递归到动规的转化、动规的四个核心步骤（问题分解、状态确定、初始状态、状态转移方程）、问题的最优子结构性质与无后效性特点，并通过四个经典例题（数字三角形、神奇的口袋、最长公共子序列、最长上升子序列）详细说明了动规的应用过程和解题思路。

文章系统介绍了图的基本概念、表示方法（邻接矩阵与邻接表）、图的遍历（DFS与BFS）、最短路径问题（无权图和有权图的单源最短路径算法Dijkstra）以及最小生成树（Kruskal与Prim算法）。重点阐述了图的结构特性、常用操作及在不同场景下的应用与实现思路。

文章介绍了堆和哈夫曼树的基本概念与操作，以及并查集的简要说明。堆是一种基于完全二叉树的数组结构，支持插入、删除和建堆操作，最大堆可通过线性时间复杂度构建；哈夫曼树是带权路径长度最小的二叉树，通过最小堆实现节点合并，用于构造最优编码方案，实现高效压缩；并查集部分简要回顾，重点在于路径压缩与按秩合并。

文章介绍了线段树在解决RMQ（区间最值查询）及区间修改问题中的应用，重点讲解了线段树的数组存储方式、节点编号关系（左子节点为2n，右子节点为2n+1），以及如何通过懒标记优化区间加、乘等操作。通过具体模板题（如区间加、区间加乘）说明了线段树在支持点修改和区间修改时的实现方法，强调了pushdown操作和“先乘后加”的关键逻辑。

文章介绍了二叉搜索树（BST）的基本概念、核心操作（查找、插入、删除）以及平衡二叉树（AVL树）的结构与调整机制。通过分析插入序列是否能生成相同的二叉搜索树，提出了基于树结构比对的方法来判断两个序列是否对应同一棵BST。