题面 题目描述 小 $T$ 打算在城市 $C$ 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，小 $T$ 希望快餐店的地址选在离最远的顾客距离最近的地方。 快餐店的顾客分布在城市 C 的 $N$ 个建筑中，这 $N$ 个建筑通过恰好 $N$条双向道路连接起来，…

前言 其实这篇文章早就想写了，只不过一直咕咕咕着，咕了一年（大雾。 现在对于斜率优化已经产生了十分深刻的李姐了，所以可以放心大胆地胡扯了。 正文 关于一个$DP$方程，如果它的形式如$F[i]=max(or min)(F[j]+(一堆只关于j的式子)+(一堆只关于i的式子))$那么这样我们是可以对其进行单调队列优化的，把复杂度降低一维。但是如果形式…

前言 这是我在中考结束后写的第一篇博客，关于中考他死了。 接下来还有FFT等一众博客要更新，只能慢慢来了。 部分算法为中考前集训学的，现在需要回忆下才能口胡出来，所以先更这篇昨天学习的容斥及广义容斥的姿势。 本文有部分参考于Parsnip的博文可以去他那里补充看看。 正文 容斥原理 这个大家或多或少都接触过，就是给出一些不同性质包含不同数量元素的集…

前言 别问我为啥不和点分治写一块。。。内容过多了。。。所以分开写 正文 我们知道，在处理树上问题的时候，点分治是一个很好用的算法，但是倘若是多次询问或者是带修改操作，那么就需要重新点分治，这样的效率极其低下，那么我们就考虑重构这整棵树。把每个点与他的子树中的重心（或者假重心，可以看看我点分治那篇的最后update有提到）相连，也就是建father。…

学习线性基 我们在处理异或问题的时候可能会遇到某些恶心的问题，比如： 1.给定一个集合，可以让任意多个数异或，求最大/小异或和 2. 给定一个集合，可以让任意多个数异或，求第k小异或和 3. 给定一个集合，可以让任意多个数异或，求x能否被异或出来 这些问题我们可以使用线性基来解决。 何为线性基 线性基是一个集合，它的大小是log2原集合的值域，它的…

学习数位DP 在我们遇到一些什么对于一个区间内的数字找符合要求的个数或求和时，我们可能会想到枚举，但当$l,r$过大时我们便会难以枚举，这个时候就需要用到数位$DP$了,然而有一说一，这个数位$DP$不过只是把枚举的方法换了下而已，但对我这样的蒟蒻来说还是很难。 举个例子吧 windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正…

1.BSGS 求解如关于$x$的方程$A^x≡B \mod\ p$ 的最小整数解。$(A,p互质,p为质数)$ 不难发现$x<=p$ 因为会出现循环。 靠虑将$x$分解为$i\times sqrt(p)-j$ 。 则原式化为$A^{i\times \lceil sqrt(p)\rceil}\times A^{-j}≡B \mod\ p$ 对$…

在面对树上路径的处理问题中，我们有一个十分方便的离线处理方法点分治。 点分治的构成具体如下 1.找重心 2.计算（单个重心）子树答案 3.合并答案 很方便对吧。 让我们一个一个讲 以这题为例题目让我们求一棵树中简单路径距离<=k的点对数。 1.找重心 重心是什么——一个树当中，最大的子树最小的节点便是重心，要注意的是重心不一定唯一，但取任意一…

本文参考借鉴于知乎上$Syu Gau$与$阮行止$在$如何证明莫比乌斯反演？$这一问题下的回答. 前置知识 1.卷积 首先我们先设$f,g$为两个数论函数。 则卷积定义为$(f\times g)(n)=\sum_{ij=n}f(i)g(j)$。(注意本文的$\times$不是乘,是卷积运算，乘都已省略) 易证卷积满足交换律与结合律。 那么让我们设想…

关于模拟退火(以下来自百度百科) 模拟退火算法（Simulate Anneal，SA）是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。模拟退火是由S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所发明的。V.Černý在1985年也独立发明此演算法。模拟退火算法是解决TSP问题的有效方法之一。模拟…