什么，RMQ问题你还是只会线段树？什么，区间最值有1e7个查询，O(nlogn)卡不过去？没事，这篇BLOG，就让我们一同学习RMQ[区间最值]问题的另一个大杀器——ST表。 什么是ST表 ST表是一种神奇的数据结构，它虽说有它的短板——不支持修改，但它的特点同样很鲜明——短小精悍，能做到O(nlogn)的预处理，O(1)的单次查询，速度吊锤隔壁的线段树。别看名字很高级，其思路其实就是我...
超级久没有码BLOG了，超级想念当时搭BLOG的感觉……可是现在我已经是一株高三的苍老蒟蒻了，所以更新速度会慢很多，望谅解。下面就让我们一起走进国庆的第一场模拟赛吧！ A 最长距离 问题描述： windy有一块矩形土地，被分为 NM 块 11 的小格子。 有的格子含有障碍物。 如果从格子A可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。 如果从格子A不可以走到格子B，...
昨天去西湖玩了一天，所以BLOG咕咕咕了……这两天考了一场NOIP模拟赛，题目和思路还是很棒的，下面让我们一起来分享一下这些题目和思路吧！ T1 钢铁侠的诞生(a.c/cpp) 托尼是斯塔克工业公司的继承人，在一次交易中不幸被恐怖分子抓捕并关押 在山洞里。为了逃离恐怖分子的魔爪，托尼假装为恐怖分子研究武器，实际上是 在秘密研究一套全新的钢铁战衣。 几个月之后，钢铁战衣基本成型了，但需...
今天复习了一下网络流，复习了之前学习的使用普通SPFA不断找增广路单路增广的算法，并且学习了一下zkw网络流和折中的算法——SPFA多路增广算法，今天就让我们来一起学习一下最小(最大)费用流吧！ 什么是费用流问题 在一般的最大流题目中，一般每条边只有一个参数——容量，但是费用流中每条边还多了一个参数——费用，也就是说在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研...
今天在陈学康学长的指导下，了解并学习了k短路算法，发现也并没有想象中的那么难。那么这篇BLOG，就让我们一起来学习k短路算法吧！ 什么是k短路 我们在之前的学习当中，肯定已经学习过了最短路算法，经典的求解最短路算法有SPFA和Dijkstra之类的，这这里就不再讲解了。今天我们要求解的如果不是最短路，而是第k短路怎么办？比如给你一道题： 给你一副有N个点(N≤1000)，M条边(M≤1...