w1nn0w

摘要： 题目：洛谷p1462 只要某个性质具有单调性，就必然可以二分。 以最短路为判断条件，二分费用，只允许使用费用小于等于目前费用的节点，求最短路，看是否可行，再根据可行性二分费用，最后求出费用的最小值 K 越大，可行性越高（单调性） 如果你允许 cost ≤ K 肯定比 cost ≤ K-1 能用的点更 阅读全文

摘要： LNIS 1.处理一个数时： 如果这个数小于等于当前序列的最后一个数，则直接接在后面，ct++ 反之，从序列头开始寻找第一个比这个数小的数并且替代他，目的：使这个序列更容易接后面的数 2.代码模板 int LNIS(vector& a) { vector tail; for (int x : a) 阅读全文

摘要： 差分约束算法 一.形式 由一组形如x_i​−x_j≤c​的不等式组成的系统，其中x_i,x_j,是变量，c是常量。 目标是：判断是否有一组 x 值同时满足所有约束；若有，求出一组可行解。 二.思路：转化成最短路问题 1.将x_i​−x_j≤c转化成x_i​≤c+x_j，添加一条j节点到i节点的权值为 阅读全文

摘要： SPFA算法 1.SPFA 是 Bellman-Ford 算法 的一种优化算法，用来求解 带权有向图 中 单源最短路径（可以有负权边，但不能有负权回路）。 2.算法流程： 以源点 s 为起点： (1)初始化 dist[i] = INF，dist[s] = 0； (2)建立一个队列 q，将 s 入队； 阅读全文

摘要： 一.DAG即有向无环图，常用于： 任务依赖：某任务必须在另一个任务完成后执行（如编译依赖、任务调度）。 课程顺序：先修课关系。 表达式计算顺序。 动态规划优化：例如在 DAG 上进行最长路径、最短路径 DP。 二.拓扑排序 1.拓扑排序只存在于DAG中 2.两种算法 a.入度法： (1)统计所有节点 阅读全文

摘要： 1.返回值和状态更新 写法 特征 举例 返回值是否有意义 ① 记忆化递归（自顶向下） 用返回值表示状态 dfs(i) 返回从 i 出发的最大值 ✅ 非常重要 ② 递推（自底向上） 不返回值，只更新表 dp[i][j] = ... ❌ 一般返回 void a.把总问题分割成小问题更简单时，用方法一，函 阅读全文

摘要： 二叉搜索树 1.什么是二叉搜索树？ 对于树中的任意一个节点 N： 左子树 中所有节点的值 都小于 N 的值； 右子树 中所有节点的值 都大于 N 的值； 左右子树也分别是二叉搜索树。 2.常见操作（递归思想） （1）.查找 TreeNode* search(TreeNode* root, int k 阅读全文