算法
  1. Dotcpp
  2. 算法

列表

什么是Prufer序列？

什么是Prufer序列？

Prufer序列可以将一个带标号n个结点的树用[1,n]中的n-2个整数表示。你也可以把它理解为完全图的生成树与数列之间的双射。显然你不会想不开拿这玩意儿去维护树结构。这玩意儿常用组合计数问题上。HeinzPrufer于1918年发明这个序列来证明凯莱定理。
图论 2022年02月11日
置换和排列的区别？

置换和排列的区别？

一、置换一个有限集合S到自身的双射（即一一对应）称为S的一个置换。集合上的置换可以表示为意为将映射为，其中是1,2，…，n的一个排列。显然S上所有置换的数量为n!。乘法对于两个置换和，f和g的乘积记为，其值为简单来说就是先后经过f的映射，再经过g的映射。
数学相关 2022年01月06日
斯坦纳树的应用

斯坦纳树的应用

斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。1.什么是斯坦纳树？斯坦纳树问题是组合优化学科中的一个问题。
图论 2022年02月01日
DP优化（三）四边形不等式优化实例讲解

DP优化（三）四边形不等式优化实例讲解

有一种DP可以写成四边形不等式，那么可以用一个优化来优化这种DP（一般是二维的，不加优化是O(n3)）。如果a≤b≤c≤d，那么如果DP式子满足f(a,c)+f(b,d)≤f(b,c)+f(a,d)，那么这就是一个四边形不等式。一、首先先看一道例题题目：有一群人要乘船,
动态规划 2022年03月09日
分块查找算法介绍与实现

分块查找算法介绍与实现

1.算法简介分块查找是折半查找和顺序查找的一种改进方法，分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况，其核心有二索引表，二是分块处理。分块查找要求把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。
查找算法 2022年05月12日
最小生成树,普利姆(Prim)算法及C/C++代码实现

最小生成树,普利姆(Prim)算法及C/C++代码实现

1.最小生成树（又名：最小权重生成树）概念：将给出的所有点连接起来（即从一个点可到任意一个点），且连接路径之和最小的图叫最小生成树。最小生成树属于一种树形结构（树形结构是一种特殊的图），或者说是直链型结构，因为当n个点相连，且路径和最短，那么将它们相连的路一定是n-1条。
图 2022年03月24日
离散化算法实例讲解

离散化算法实例讲解

说到离散化，可能很多人不知道这是什么，小编简单给大家介绍一下，后面会详细说明，离散化是程序设计中一个常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中，只考虑需要用的值。离散化可以改进一个低效的算法，甚至实现根本不可能实现的算法。
其他算法 2022年03月12日
矩阵扩展-算卷积算法介绍及C语言代码实现

矩阵扩展-算卷积算法介绍及C语言代码实现

1.矩阵扩展算法——简单的算卷积接着上文，矩阵进行更深入的学习就需要学习更多的处理了，矩阵被运用在很多的领域，这里简单以计算机图形处理的重要概念——卷积，为例进行说明：卷积。用一个模板去和另一个图片对比，进行卷积运算。目的是使目标与目标之间的差距变得更大。
串、数组、矩阵和广义表 2022年03月03日
后缀自动机（单词的有向无环图）简介

后缀自动机（单词的有向无环图）简介

在我们学习后缀自动机之前，一定要先了解什么是自动机？自动机（确定有限状态自动机）是由一个非空有限状态的集合Q、一个输入字母表Σ（非空有限字符的集合）、一个转移函数（单值映射）、一个开始状态、一个接受状态（终结状态）的集合所组成的5-元组。历史上，
字符串相关 2022年04月29日
动态规划DP算法详解

动态规划DP算法详解

1.简介动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，
算法和竞赛 2022年02月15日