算法

1. Dotcpp
2. 算法

概率DP实例讲解

在动态规划中，概率DP一般会用于研究有关于概率，步数，期望等问题。简单总结为以下四个点：（1）数学期望P=Σ每一种状态*对应的概率。（2）因为不可能枚举完所有的状态，有时也不可能枚举完，比如抛硬币，有可能一直是正面，etc。但是现在发现大多数题就是手动找公式或者DP推出即可，

动态规划 2022年02月16日 105 点赞 0 评论 66011 浏览

简述LGV引理

LGV引理可以用于在DAG上求解不相交路径方案数问题，下面我们简单介绍一下。一、简介LGV引理英文全称是Lindström–Gessel–Viennotlemma，可以用来处理有向无环图上不相交路径计数等问题。在此之前，大家要先了解图论相关概念、矩阵、高斯消元求行列式等知识，

图论 2022年04月20日 249 点赞 0 评论 65870 浏览

什么是树上随机游走？

什么是树上随机游走？我们可以假设给定一棵树，树的某个结点上有一个硬币，在某一时刻硬币会等概率地移动到邻接结点上，问硬币移动到邻接结点上的期望距离。1.树上随机游走用到的定义：●所讨论的树●结点的度数●结点与v结点之间的边的边权●结点的父结点●结点的子结点集合●结点的兄弟结点集合2.向父结点走的期望距离

图论 2022年03月22日 88 点赞 0 评论 65712 浏览

三维计算几何基础

本篇内容是围绕着三维计算几何展开，三维几何的很多概念和知识与二维几何是想通的，所以在我们做三维几何问题的时候，可以采用解决二维几何问题相同的方法来解决。其中点，向量，直线等概念和二维几何相似，就不再重复介绍了。平面我们可以用平面上的一点和该平面的法向量（即垂直于该平面的向量）n来表示一个平面。

计算几何 2022年01月10日 74 点赞 0 评论 65402 浏览

最小表示法算法解析

提到最小表示法，要了解它的定义，最小表示法是用于解决字符串最小表示问题的方法。一算法简介：当一个字符串形成一个环的时候，要比较两个字符串是否相同就会变得很困难，因为你不知道对于第二个字符串来说，以哪个字符开始比较才会和第一个字符串相同。所以我们就会想到枚举起点比较是否相同，而这样的复杂度O(n^2)。

字符串相关 2022年03月10日 142 点赞 0 评论 65328 浏览

树哈希常用的方式

树哈希，顾名思义，对树进行哈希，经常判断两个树是否同构。一下均为对有根树的算法，而无根树只需要找重心。我们有时需要判断一些树是否同构。这时，选择恰当的哈希方式来将树映射成一个便于储存的哈希值（一般是32位或64位整数）是一个优秀的方案。树哈希有很多种哈希方式，下面将选出几种较为常用的方式来加以介绍。

图论 2022年03月28日 143 点赞 0 评论 65100 浏览

悬线法实例讲解

先说说什么是悬线？就是一条竖线，这条竖线有初始位置和高度两个性质，可以在其上端点不超过当前位置的矩形高度的情况下左右移动。一、概述悬线法的适用范围是单调栈的子集。具体来说，悬线法可以应用于满足以下条件的题目：（1）需要在扫描序列时维护单调的信息；（2）可以使用单调栈解决；（3）不需要在单调栈上二分。

其他算法 2022年03月25日 83 点赞 0 评论 64703 浏览

广义后缀自动机概述

广义后缀自动机的前置知识点是后缀自动机和字典树（Trie树）的相关内容，因为这两个知识点穿插在一起更容易理解和构建知识框架。当我们的是动机如何储存一个字符串的所有子串？该怎么办？怎么做？后缀自动机的作用就展现出来了。首先，后缀自动机起源于刘研绎在其2015国家队论文《后缀自动机在字典树上的拓展》上提出

字符串相关 2022年04月26日 108 点赞 0 评论 63789 浏览

计数DP实例讲解

本篇主要从计数DP上结合实例分析。一、计数类DP——整数划分整数划分大体上可以分为3类（1）考虑顺序的拆分方案（即1，1，2；和2，1，1是两种不同的方案），这种问题一般转化为完全背包即可解决。（2）不考虑顺序的拆分方案，可以划分出空集（也就是可以有对拆分完全没贡献的东西存在（0））（3）不考虑顺序的

动态规划 2022年04月04日 98 点赞 0 评论 61681 浏览

C++标准库中的字符串

一、C++字符串C++提供了以下两种类型的字符串表示形式：（1）C风格字符串（2）C++引入的string类类型二、C风格字符串C风格的字符串起源于C语言，并在C++中继续得到支持。字符串实际上是使用null字符\0终止的一维字符数组。因此，一个以null结尾的字符串，包含了组成字符串的字符。

字符串相关 2022年02月05日 170 点赞 0 评论 61313 浏览