杭州OI学习之旅Day1打卡——看似神奇实则平实的的左偏树。今天在陈学长的带领之下学习了堆和左偏树，这篇BLOG，就让我们一同走进左偏树吧。 【PS 参考资料 黄源河《左 偏 树 的 特 点 及 其 应 用》】 堆 左偏树的实质是一个可并堆，在了解可并堆之前我们需要先了解堆。 堆是什么？看起来很高级，但其实它就是利用完全二叉树的结构来维护一组数据，然后进行相关操作，一般的操作进行一次的时...
这两天已经变成的ACMer的标学长回来传授了一些有趣的东西，感觉会在一些奇奇怪怪的题目上运用上。今天我们就先来讲讲神奇的泰勒展开式。【PS 思路来源于 Orz大佬】 什么是泰勒展开式 首先，泰勒展开式是长这样的： 是不是看起来很让人懵逼很让人迷惑，没事，就下来我就带领你尽量还原泰勒发明的过程，从如何创作这条泰勒公式的角度，走进这条美丽奇幻的泰勒公式。 深入浅出的理解泰勒展开式 在公元1...
最近有些高产啊……咳咳咳……今天看到了一个非常实用的计算几何定理，决定带上简单易懂的证明分享给大家QwQ 什么是Pick定理 皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式，该公式可以表示为2S=2a+b-2，其中a表示多边形内部的点数，b表示多边形边界上的点数，S表示多边形的面积。 这个算法最早是由奥地利的的George Alexander Pick提出，为了纪念他，所以这个...
AC自动机补档第二期……不懂KMP的同学可以好好学习一下这个神奇的单字符串匹配问题的算法吧！ 字符串匹配 什么叫字符串匹配呢？假设我们有一个主字符串和一个子串： 主串：abcbcglx 子串：bcgl 那么在主字符串中，有没有包含子串呢？当然，你一眼就看出，从主串的第4位到第7位恰好为子串 bcgl；这时我们的匹配算法就返回 4 也就是子串在主串中第一次出现的起始位置；若匹配失败，既...
在写完AC自动机后，就有小伙伴要求我具体讲解一下KMP和Trie树，那么这篇BLOG，就带你走进其实很简单的Trie树吧！ 什么是字典树 基本概念 字典树，又称为单词查找树或Tire树，是一种树形结构，它是一种哈希树的变种，用于存储字符串及其相关信息。 基本性质 1.根节点不包含字符，除根节点外的每一个子节点都包含一个字符 2.从根节点到某一节点。从根节点到该节点路径上经过的字符连接...