前缀DP问题问题描述前缀DP是动态规划算法的一种应用形式，它利用前缀信息来优化状态转移过程。前缀DP通常处理以下几类问题： 需要依赖前面已处理的状态进行决策 可以利用前缀和或前缀信息优化复杂度 需要处理连续子序列或子数组 基本思路前缀DP通常遵循...

优先队列(Priority Queue)1. 基本概念优先队列是一种特殊的队列，其中的元素都有一个优先级。在优先队列中，具有高优先级的元素先被处理。 1.1 特点 每个元素都有优先级 高优先级元素优先出队 底层通常用堆实现 插入和删除的时间复杂度为O...

广度优先搜索(BFS)1. 基本概念广度优先搜索(Breadth-First Search, BFS)是一种图形搜索算法，从起始节点开始，沿着宽度方向探索，即先访问所有相邻节点，再访问下一层节点。 1.1 特点 按层次遍历，先浅后深 利用队列实现 找...

C++ STL list 学习笔记1. list 基本概念list 是 C++ STL 中的双向链表容器，它由一系列节点组成，每个节点包含数据和指向前后节点的指针。 1.1 特点 非连续内存存储 不支持随机访问 在任意位置插入/删除效率高 ...

多重背包问题21. 问题描述有N种物品和一个容量为V的背包。第i种物品最多有si件，每件体积是vi，价值是wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。 1.1 输入格式1234567// 第一行两个整数...

不连续子序列匹配1. 问题描述给定两个序列，判断一个序列是否为另一个序列的子序列。子序列不要求连续，但需要保持原序列中元素的相对顺序。 1.1 问题特点 子序列元素在原序列中不要求连续 必须保持原序列中元素的相对顺序 需要考虑序列长度的限制 需要高效...

C++ STL map1. map 基本概念map 是一种关联容器，它提供一对一的哈希，第一个可以称为关键字(key)，第二个可以称为该关键字的值(value)。 1.1 特点 每个关键字只能在map中出现一次 根据关键字自动排序 动态插入和删除 使...

哈希查找1. 基本概念哈希查找（Hash Search）是一种基于哈希表的查找方式，通过哈希函数将关键字映射到表中的位置来访问记录。 1.1 核心组成 哈希函数：将关键字转换为数组下标 冲突处理：解决不同关键字映射到同一位置的问题(key1!...