回归梦想

算法

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2) 题解(271)

/ 注册

全部文章 / 算法（共76篇）

博弈论讲解（一）

常见的博弈论有巴什博弈，威佐夫博弈，尼姆博弈，斐波那契博弈等等，今天暂时讲几个@[toc] 一.巴什博弈巴什博奕：只有一堆n个物品，两个人轮流从中取物，规定每次最少取一个，最多取m个，最后取光者为胜。证明：显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能...

2020-05-10

0 629

三分法

二分用到的挺多，三分用的少，但也不能忘。。。二分我们常常用于一个具有单调性的情况中求解某值而三分就像是求一个凸性或凹形函数时，来求那个凹凸点一开始L=0，R=inf，然后也是不断缩小L与R的范围，逼近最值点这里面有两个中间点mid1与mid2mid1=(L+R)>>1mid2=(mid...

三分

2020-05-01

1 465

最小生成树(模板)

@[TOC]昨天做蓝桥杯的题，最后一题最小生成树，但好久没用一下子生疏了。。。又过了几天离散学到了最小生成树。。。趁此复习一波最小生成树两种方法：Prim和Kruskal 关于时间复杂度： prim:该算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图。 kruskal:需要对图的边...

最小生成树

2020-05-01

2 782

ST表讲解

ST表主要用于解决RMQ问题（区间最值问题）当然你可以用线段树等，但今天用一种ST表（倍增算法） ST表是倍增算法的一个典型应用暴力做RMQ问题，往往会超时，ST表利用对其进行优化给定一段序列A，ST算法能在O(NlogN)的时间预处理后，以O(1) 的复杂度查询，在线回答在一段区间l,r 中最大...

ST表

2020-05-01

1 571

欧拉序与DFS序

@[TOC]欧拉序与DFS序相似又不同欧拉序的定义树在dfs过程中的节点访问顺序称为欧拉序.那有人会问：dfs序和欧拉序啥区别？ dfs序：是指将一棵树被dfs时所经过的节点顺序（不绕回原点）。欧拉序：就是从根结点出发，按dfs的顺序在绕回原点所经过所有点的顺序。欧拉序与dfs序不同地方在于，欧...

dfs序欧拉序

2020-05-01

0 1304

序列自动机

题目：给你a和b两个字符串，问b是不是a的子序列？题解：参考题解注意看，子序列不是子串，两者含义不一样一个字符串 s 被称作另一个字符串 S 的子串，表示 s 在 S中出现了。一个字符串 s被称作另一个字符串 S 的子序列，说明从序列 S通过去除某些元素但不破坏余下元素的相对位置（在前...

序列自动机

2020-04-02

0 842