在之前的BLOG里，我们谈论过了二分图的一部分问题——最大匹配问题，并且一起学习了解决这类问题的匈牙利算法，还没有学过的同学可以 点击我学习最大匹配算法。在这一篇BLOG里，我们将一同学习二分图的另一个问题——最大带权匹配问题。 什么是二分图最大带权匹配 那么什么是二分图的最大带权匹配呢？实现我们都应该知道什么是二分图的最大匹配。不知道也没关系，我们先看一下下面这个问题：比如我们有3个公...
在众多的线段树题目中，有一种题目一直占有一席之地，那就是染色问题，这篇BLOG，我们就针对染色问题，来浅谈一下这一类问题的解决方法 一维染色问题 这一类题目，一般都有一个固定的样式，当你对题目进行简化以后，总会得到类似与下面这种模型类似： 在一条数轴上，依次进行n次操作，每次操作读入3个数,x,y,z，表示在区间[x,y]中涂上颜色z，后涂上的颜色会覆盖之前涂上的颜色。问最后我们还能看...
今天在某神犇老师的带领下学习了后缀自动机，刚开始学的时候还是一脸懵逼的，后面在周围大佬们孜孜不倦的帮助下终于学会了后缀数组。这篇BLOG，就让我们携手走进后缀数组吧。 什么是后缀数组 我们先来一个一个概念搞懂： 子串 若我们有一个长度为n的字符串S，设字符串内的点为[1,n]，那么我们从中任意截取一段[l,r], 若1≤l≤r≤n，那么称 截取出来的这段子字符串SS为原字符串的子串。即若...
我们在之前的BLOG已经多次提到了，平衡树的本质是BST(二叉查找树)，而平衡树的作用是为了加速二叉查找树，但不添加任何内容，可以说是BST的加速版。但是Splay却恰好相反，为了得到更多的功能，splay牺牲了时间和空间，其本质目的不是为了加速二叉排序树，而是为了增加一些普通二叉排序树所不具有的功能，所以splay可以称得上是BST的ex版，所以splay从本质目的上来说已经算不上是平衡...
在我这只蒟蒻在瑟瑟发抖地刷二分图的题目时，惊讶地发现，居然有博弈论用二分图来解答！(大佬轻喷orz)这篇BLOG就让我们来一起了解一下如何用二分图来解决一些博弈论的题目把！ 一类博弈论问题 首先我们要明白，二分图并不能解决所有博弈论的问题。这篇BLOG我们要讨论的一类博弈问题，是基于以下条件： 1.博弈者人数为两人，双方轮流进行决策。 2.博弈状态（对应点）可分为两类（状态空间可分为两个...