今天因为不会 伯努利-欧拉装错信封问题 被附近的大佬狠狠地嘲讽了一下，去学习了一下发现，这确实是个经典而有趣的问题，今天就让我们来分享一下这个问题吧！ 什么是伯努利-欧拉装错信封问题 伯努利-欧拉装错信封问题 又称 错位重排问题，具体来说，就是—— 我们有编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不同，即1不能装进1，2不能装进2，3不能装进...
在我们之前接触到的题目里面，线段树的叶子节点都是保存单点的值，其他节点都是保存一个区间的值，这种题目的一些基本构造想法在浅谈线段树的构造(一)中已经提及到了。但你想过吗，当叶子节点保存一个区间的值时，你该如何构造？ 从经典的例题谈起 我们先看一道POI2015的经典例题： 【BZOJ p3747】[POI2015]Kinoman Time Limit: 60 Sec Memory L...
在上一篇BLOG中，我们介绍了二叉查找树的八种操作。但是有人会说，万一退化成链之类的不就超时了吗？为了让我们的二叉查找树高度的期望维持在 log n ，我们就要通过平衡树来进行一些维护。而今天我们就来介绍一种神奇的平衡树——TREAP 写在前面：如果你还不太熟悉二叉查找树，建议先抽空点我学习二叉查找树后再食用这篇BLOG. 什么是Treap 我们都知道，Treap是平衡树的一种实现形式，...
在学习平衡树和Splay之前，我们应该了解一个更为基础的算法——二叉查找树。不论是平衡树还是splay都是建立在二叉查找树上，所以这篇BLOG，我就来带领你走进二叉查找树。 二叉查找树的定义 二叉查找数不同于普通二叉树的一个特点就是:对于每一个节点，若存在左子节点，那么该节点的值一定大于左子节点的值；若存在右子节点，那么该节点的值一定小于右子节点的值，例如下图就是一棵可爱的二叉查找树： ...
说到线段树，大家第一反应就是经典的RMQ问题，相信大家都已经很好的掌握了，今天就不再过多的进行讲解了。今天我们主要通过一道例题开始，浅谈一下线段树的构造吧。 一道水题 我们先从一道简单的例题看起。 给你一段长为n，n≤1e5 的47串，比如4747747444774…………，求这个串的最长不下降子序列的长度是多少(PS 子序列即不一定要连续的串)。 “这不是一道惊天大水题吗”看完后的你一...