今天在某神犇老师的带领下学习了后缀自动机，刚开始学的时候还是一脸懵逼的，后面在周围大佬们孜孜不倦的帮助下终于学会了后缀数组。这篇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.博弈状态（对应点）可分为两类（状态空间可分为两个...
今天因为不会 伯努利-欧拉装错信封问题 被附近的大佬狠狠地嘲讽了一下，去学习了一下发现，这确实是个经典而有趣的问题，今天就让我们来分享一下这个问题吧！ 什么是伯努利-欧拉装错信封问题 伯努利-欧拉装错信封问题 又称 错位重排问题，具体来说，就是—— 我们有编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不同，即1不能装进1，2不能装进2，3不能装进...
在我们之前接触到的题目里面，线段树的叶子节点都是保存单点的值，其他节点都是保存一个区间的值，这种题目的一些基本构造想法在浅谈线段树的构造(一)中已经提及到了。但你想过吗，当叶子节点保存一个区间的值时，你该如何构造？ 从经典的例题谈起 我们先看一道POI2015的经典例题： 【BZOJ p3747】[POI2015]Kinoman Time Limit: 60 Sec Memory L...