【算法讲解】dp优化——四边形不等式优化（2）-爱代码爱编程
前言 上文讲了四边形不等式在一类 DP 问题中的优化策略 可能大家会觉得，这么复杂的定理，结果只用应用在某类固定 dp 方程上，有点大炮打蚊子的感觉 本文带来了四边形不等式在另外一类非常常见的 dp 方程的应用 分治 D
【算法讲解】dp优化——四边形不等式优化-爱代码爱编程
前言 此优化策略由高德纳和姚期智发现并证明，故学名称之为 Knuth-Yao Speedup (Knuth 是算法届的鼻祖，对于算法新手来说，KMP一定不陌生，Knuth 就是三个联合发明人之一的 K；Yao 就是清
【基础算法】二分查找、二分答案-爱代码爱编程
文章目录 前言二分搜索精确查找最朴素的做法随机取值优化一下二分查找 查找第一个大于(等于)目标值的下标查找最后一个小于(等于)目标值的下标STL lower_bound, upper_bound
算法串讲之floyd-warshall算法【c++】【图论】【最短路】-爱代码爱编程
我们作为刚学图论的小蒟蒻，先接触到的算法一定是图上最短路径算法。而最短路算法中最简单的当属Floyd-Warshall算法。下面是一些基本介绍： 该算法可以计算图上任意两点间的最短路径 时间复杂度： 适用情况：适用出现负边权的情况 算法伪代码： 弗洛伊德算法的基本思想是动态规划，我们枚举每一个点，并以其为中间节点更新任意两点间的最小
扩展域并查集——基本原理与实现方式-爱代码爱编程
并查集算法可以说是所有提高组算法中最友好的算法之一，就算是它的路径压缩也很好打。但是，对于某些题，朴素的并查集可能无法得出正确答案。例如这道题。 [BOI2003]团伙 题目描述 现在有 n 个人，他们之间有两种关系：朋友和敌人。我们知道： 一个人的朋友的朋友是朋友 一个人的敌人的敌人是朋友 现在要
并查集启发式合并-爱代码爱编程
我们知道，在并查集中为了减少时间复杂度，我们引入了路径压缩，路径压缩的原理说白了就是在find函数回来的路上顺便把本节点指向根节点。然而路径压缩也是有效率的，这个效率取决于本节点到根节点的路径长度。有没有一种方法可以更好的节省路径压缩的时间呢？有！这种方法就是启发式合并。启发式合并可以根据树的大小进行合并，也可以根据树的深度进行合并，但树的
简易理解并计算二进制除法_阿涵阳光向上的博客-爱代码爱编程
二进制除法可以算是二进制算法中最难（相对加减乘）的一个，有些人在理解上出现一些误差，下面教大家如何简单理解并计算二进制除法 首先介绍一下二进制的运算规则：1÷1=1；1÷0=0（无意义）；0÷1=0；0÷0=0（无意义） 众所周知小学除法（十进制）15÷7不够除要向前面借1当10，而二进制不同的就是借1当2（补充：二进制加法1+1=10） 以下图为例
lca的tarjan求法&&poj 1470的辛酸历程_阿蒋的博客-爱代码爱编程
转载请注明出处：http://blog.csdn.net/jiangshibiao/article/details/23659735 【LCA的线性解法】LCA（最近公共祖先）的问题十分常见。以前我单纯的认为，每次O(N)扫一遍每个节点的深度、再直接暴力求LCA的效率很高——Nlog(N)。但是往往树会退化成链（或者说它不平衡），如果询问次数多的话肯定T
跟踪链接|dt介绍，含例子_code_wangzili的博客-爱代码爱编程
决策树 1. 概述 决策树就是一棵树，一个有终止模块的流程图，终点就是分类的结果。 一般来说决策树学习由三个步骤组成：特征选择、决策树构建、决策树修剪。 1.1 优点 计算复杂度不高输出结果易于理解对中间值的缺失不敏
跟踪链接|knn介绍_code_wangzili的博客-爱代码爱编程
K-近邻分类算法 1. 概述 k近邻算法采用测量不同特征值之间的距离方法来进行分类。 1.1 优点 精度高对异常值不敏感无数据输入假定 1.2 缺点 计算复杂度高空间复杂度高 1.3 数据适用范围 数值型与标
浅谈模拟退火_l.e.m.t的博客-爱代码爱编程
Q：模拟退火是什么？ A：一种随机化算法，用于水分。 Q：模拟退火可以解决什么问题？ A：可以处理多峰或单峰函数的求值，这时函数没有二分性，只能动态规划，想不出正解时便可尝试使用模拟退火。 Q：模拟退火的原理是什么？
leetcode 0107.二叉树的层序遍历ii - 另一种方法_tisfy的博客-爱代码爱编程
【LetMeFly】107.二叉树的层序遍历 II 力扣题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/ 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） 示例 1： 输
leetcode 0102.二叉树的层序遍历 + 针对c++的使用空间优化 （可能不同于常规做法）_tisfy的博客-爱代码爱编程
【LetMeFly】102.二叉树的层序遍历 + 针对C++的使用空间优化 （可能不同于常规做法） 力扣题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/ 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。 示例
码蹄集 - mt3435 · 赋值 - 二分图问题 - 图文讲解_tisfy的博客-爱代码爱编程
传送门 赋值题目描述输入描述输出描述样例一输入输出题目分析二分图简述划分为二分图结果计算AC代码 赋值 赋值 .时间限制：1秒空间限制：256M 题目描述 给定一张含有n个结点m条边的无向图，你必须给每个点赋一个点权（必须是1 2 3中的一个），问有多少种不同的赋值方式（这不就是3^n吗？？？，往下看） 但有一个限制条件：那就是每条边
算法讲解|动态规划_code_wangzili的博客-爱代码爱编程
什么是动态规划 动态规划过程是：每次决策都依赖于当前状态，又随即引起状态的转移。 一个具体的决策序列是根据不同状态变化得到的，这种决策过程就称为规划，这种多阶段的最优化策略解决问题的过程就称为动态规划。 基本策略与适用情况 基本策略 基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问
算法讲解|分治递归_code_wangzili的博客-爱代码爱编程
什么是递归？ 递归和迭代的区别联系 很多人其实都不太清楚递归与迭代的具体差别，迭代指的是你在某一个条件下一直循环 比如 for(int i=0;i<100;i++>) 指的就是迭代100次，迭代100次就停止了。 而递归不一样，递归指的是调用自己本身，例如： int function1(int n,int m) { n++
后缀数组SA笔记-爱代码爱编程
后缀数组是什么 后缀数组，SA，可用于解决字符串问题。 那我们看后缀数组： 先约束一些东西： 1.字符数组下标从1开始。 2.len表示字符数组的长度。 后缀数组主要有两个数组组成 s a
二分查找题解-爱代码爱编程
二分就是从中割开将其分为两半，分别处理。 题目背景：给定n个单调不下降的非负整数，m次查询，每次查询给定数字在数列里第一次出现的序号，从1开始编号。 核心思路二分：由于这是一个单调的不下降序列，所以如果当前的数比要找的数k小，那么当前这个数前面的数都比这个数小所以就没有必要去判断了，而为了次数更少我们就可以直接总数列的中间开始判断，如果中间的数mid比
2021-2022-1 北京化工大学程序设计月赛（1） - 问题 G: 游戏的彩蛋 - 题解 - 哈希讲解-爱代码爱编程
传送门 游戏的彩蛋题目描述输入描述输出描述样例一输入输出样例二输入输出题目分析本题彩蛋哈希简介KMP反思AC代码 游戏的彩蛋 游戏的彩蛋时间限制：1秒空间限制：256M 题目描述 Ron Milner 在 1977
可持久化(二)-爱代码爱编程
文章目录 【可持久化值域线段树/主席树】主席树代码【二维数点】例题 【可持久化值域线段树/主席树】 P3834 【模板】可持久化线段树 1（主席树） 查询序列区间第k小，静态在线。给定 n 个整数构成的序列，将对于指定的闭区间查询其区间内的第 k 小值。 类似值域线段树上二分求kth的方法，对于[l,r]区间内部的 kth，若有[1,l-1