祝馀宫

之前是讲过斜率优化DP的，只不过那时候还没有学过计算几何，所以说讲的不是很深，所以说这里来介绍一下如何从几何意义上也就凸包的角度理解斜率优化DP。 友情链接： 【算法介绍】斜率优化优化动态规划 | 祝馀宫 从例题出发题目传送门 题目大意给出 $N$ 个单词，每个单词有个非负权值 $a_i$，现在要将它们分成连续的若干段，每段的代价为此段单词的权值和的平方，还要加一个常数 $M$，即 $(\sum a_i)^2+M$。现在想求出一种最优方案，使得总费用之和最小。 解题思路首先我们进行一个暴力的推导，也就是最原始的转移方程式。 这个不难，我们对于 $i$ 只需要枚举一个断点即可，规定 $j$ 属于上一段的部分： dp[i]=\min_{0\le j\lt i}\{dp[j] + (sum[i]-sum[j])^2 +M\}这个的转移显然是 $O(n^2)$ 的，接下来我们要对其进行优化，那么这就是斜率优化了。首先我们对于这个式子进行一些简单的移项，可以得到下面这个： \begin{aligned} dp[i]&=dp[j] + (sum[i]-sum[j])^2 +M\\ dp[i ...

导数还是太有用了，这下不得不学了。导数的定义就是很简单的，一个函数每一个点上的斜率。这个斜率的求法其实本质上就是一个极限思想，推导也很简单，直接就是用斜率的计算公式即可。 f'(x)=\lim_{\Delta x\rightarrow 0}\frac{f(x+\Delta x) - f(x)}{\Delta x}这篇文章主要是记一写导数的公式和易错点，不然我也容易忘。 特殊函数的导数从最基础的开始。 常数函数常数函数的斜率处处为 $0$，带入上面的公式也可以知道。 幂函数 f(x)=x^a\longrightarrow f'(x)=ax^{a-1}证明： \begin{aligned} f'(x)&=\lim_{\Delta x\rightarrow 0}\frac{(x+\Delta x)^a-x^a}{\Delta x}\\ &=x^a\lim_{\Delta x\rightarrow 0}\frac{(1+\frac{\Delta x}{x})^a-1}{\Delta x}\\ &=x^a\lim_{\Delta x\rightarrow 0}\frac{e^{a\ln(1+ ...

最近在做网络流的题目，接下来说几个我做到感觉有点意思题目。网络流问题其实全是模板，但是难就难在如何把问题抽象成网络流模型。 T1 - 狼抓兔子题目传送门 我是觉得这题的题面很史所以放过来。题目让我们求在能一网打尽的前提下，设置尽可能少的狼。这个所谓的一网打尽，其实是指我们选中一些边以后，不论 $S$ 到 $T$ 怎么走，都必须经过我们选中的边。如果了解了这个，那么就是模板的最小割了（你怎么知道我一开始没看懂在网上查了一圈题解全都是“一眼模板”） T2 - 蜥蜴题目传送门 这题是一道经典的拆点题。因为石柱是有高度的，这个高度相当于是一个限制，所以说我们很容易就可以想到把一个石柱拆为两个点：一个称为石柱的顶端，一个称为石柱的底端。 那么我们可以这样理解题目中的几类操作： 放蜥蜴：建立超级源点 $S$，对于任意有蜥蜴的石柱，建立从 $S$ 到这个石柱顶端容量为 $1$ 的边。容量为 $1$ 是因为这个点只有一只蜥蜴，所以我们放也只能放一只。 石柱：对于每一个有高度的石柱，从石柱顶端连接到石柱底端，容量为高度。这样的话从这个石柱通过的蜥蜴数量就有了限制。 石柱互通：对于任意一对能够互相抵达的 ...

文章总览：高大的背影2-SAT 一开始觉得听玄学的，学了之后有感觉没什么好写，这篇文章简单说一下罢。 SAT 问题的定义 SAT 问题的解法 SAT 问题的例题 SAT 问题的细节 经典模型：紧紧的拥抱 SAT 问题的定义 首先我们了解一下 SAT 问题的定义。SAT 是英文单词适定性（Satisfiability）的简称，一般来说对于 k - 适定性问题，我们都简称为 k-SAT，这篇文章要讲的就是 2-SAT 问题，这是因为当 $k>2$ 的时候 k-SAT 问题是 NPC 问题（但是好像也有解决 k-SAT 的算法）总而言之，这里研究的是 2-SAT 问题。 简单的概括最基础的 2-SAT 的核心，就是对于 $n$ 个二元组。且存在一些形如 $\langle a,b\rangle$ 的矛盾关系，这代表 $a,b$ 不能被同时选中，这里保证 $a,b$ 不属于同一个二元组。问题就是要问存不存在一种方案，使得每一个二元组都选择出一个元素并且不出现矛盾的情况，有时还会让你输出具体的方案，显然方案是不唯一的。 其实这个问题其实并不难看出是可以抽象为图论的，有人的第一直觉就是二 ...

文章总览：雪地的圣女计算几何，好像是非常难的一部分……其实还是数学，说着难，其实也还好（好罢我不会）。总而言之，这篇文章来简单介绍一下最最基础的计算几何，下为本文大纲： 向量的定义 向量的运算 直线表示法 直线的运算 凸包的定义 凸包的运算 半平面定义 半平面模板 几何大模板 几何例题一 几何例题二 前置知识：付记忆入殓 向量的定义 向量的运算 定义：悲鸣，赐死之先声首先定义向量，其实向量在以前的文章也接触过，不过比较基础，而且并没有给出详细的定义，所以说我们还是先说一个较为形式化的定义。 友情链接： 【算法介绍】快速傅里叶变换 - 复数及其运算 | 祝馀宫 向量，顾名思义就是有方向的量，在数学上来说，只要不改变向量的大小和方向，其端点是可以随意再平面中移动的，一般记作 $\vec a$ 。事实上，向量可以认为是一个有向的线段，而有向线段的三要素非常相似于力的三要素，即起点、方向、长度。所谓三要素，就是只要知道了这三个信息，剩下的信息就可以唯一确定，所以我们也用有向线段来表示向量。 除此之外，向量还有一些其他的概念。 向量的模长：就是向量的长度，记作 $|a|$； 零向量： ...

文章总览：一心平衡树是我 114514 年前就说要学的知识点，结果拖到现在……甚至这个封面都是今年春节前就做好了qwq。因为我太菜了，这篇文章主要讲的内容是普通的二叉搜索树和两种 Treap（或许封面得改成 Treap 专题？ 下为本文大纲： 二叉搜索树概念简介 二叉搜索树分段推导 二叉搜索树优劣分析 无旋 Treap 基本概念 无旋 Treap 思想模拟 无旋 Treap 区间操作 无旋 Treap 综合例题 带旋 Treap 思想简介 带旋 Treap 分段实现 带旋 Treap 代码一览 两类 Treap 对比分析 前置知识：二观 二叉搜索树概念简介 二叉搜索树分段推导 二叉搜索树优劣分析 概念讲解：幽府说起二叉搜索树，各位并不陌生，在很久很久以前，我曾写过这样一篇文章： 友情链接： 【算法介绍】笛卡尔树 | 祝馀宫 这里面提到的笛卡尔树，也是二叉搜索树的一种。不过那篇文章并没有详细解释二叉搜索树的详细定义与编码方式，所以说作为平衡树重要的前置知识，我们把二叉搜索树一并在这里讲了。 首先我们来简单介绍一下二叉搜索树的概念。 规定每个节点有一个附加权值。 左子树和右子树 ...

文章总览：盐与犬豪德，失踪多年的我终于回来写文章了（什么？你说我干什么了？你怎么知道我出遐蝶了！），，，言归正传，这篇文章的内容是 CDQ 分治，最近做到了一道关于 CDQ 分治的题目，一看就发现不会，所以这篇文章来讲一下 CDQ 分治的一些基本原理与应用，所谓 CDQ 分治，更广泛的来说是一种思想，它在被提出之前就已经广泛流传于各大巨佬之间，后来被高中的 IOI2008 金牌得主陈丹琦总结，因此而得名。 话说这剧情怎么这么熟悉，上次讲莫队的时候好像和这个剧本完全一样 下为本文大纲： 二维数点问题的规律总结 CDQ分治思想的简单推导 CDQ分治模板题讲解 CDQ分治的简单应用 前情回顾：狮子之尾 友情链接： 【算法介绍】二维数点 | 祝馀宫【算法介绍】扫描线思想 | 祝馀宫 上面这两篇是我曾经结下的关于二维数点的一些文章。我们可以简单的总结一下，从最最开始的一维数点，是如何一步一步拓展到二维数点的呢？ 首先来从一维数点讲起，这应该是数点问题的起源。什么是数点？举个例子，现在我有一个一维的数轴，我往上面标点，标了点以后，查询某一区间，或者某一前缀等等等等有多少个点。这就是一维数点问 ...

文章总览：群星岸落之夜如你所见，这篇文章的主题是概率与期望。众所周知，概率与期望早就占领了各大领域，比如说投篮的命中率可以表达一个选手的投篮水准，竞赛题目设置很多测试点来测试代码本质是一种抽样调查，等等等等。但是说概率与期望，在初中或者高中课本中都是占比非常大的部分（刚刚好我也打算顺手学了），所以这篇文章的前半部分注重于一些课本上的基础知识介绍与讲解，后面会浅浅的说一些信竞方面的概率期望。 下为本文大纲： 概率基本知识介绍及计算 全概率公式与贝叶斯公式 期望、方差与线性相关性 二项、超几何及正态分布 期望线性性以及简单运用 随机游走的问题概率模型 概念基础：穿过锁孔之风 样本空间与概率定义 古典概型与概率加乘 独立事件与条件概率 全概率与贝叶斯公式 概率定义：这是魔法哟关于概率的定义，你可能会说：“这玩意不是烂大街了嘛吗？还有人不会的？”正确的，概率的定义其实大家都知道是那个意思，可是实际上从稍微严谨的角度出发的概念以及一些性质可能并不广为人知，我们要学概率，就要从最基础概念开始：概率的基础——事件。 对于一个事件，可以是世间万物，比如说下面几个都可以是事件： 在一个既有青蛙又 ...

文章总览：落井当下石这篇文章讲的内容是斯特林数和卡特兰数，两个非常常用的计数类型数列，初赛常考（好吧我怎么感觉斯特林数我从来没有见到过） 本文内容限定如下： 第一类斯特林数推导及实现 第二类斯特林数推导及实现 斯特林数例题 卡特兰数推导及应用 卡特兰数例题 算法其一：得胜必追击 第一类斯特林数推导及实现 第二类斯特林数推导及实现 第一类斯特林数第一类斯特林数就是：将 $n$ 个不同物体排成 $k$ 个互不区分的非空圆排列的方案数。 可以简单的分来讨论，对于第一类斯特林数 $S1(n,k)$： 对于第 $n$ 个数新开了一个圆排列，方案数为 $S1(n-1,k-1)$。 对于第 $n$ 个数插入了以前某一个圆排列，方案数为 $(n-1)\times S1(n-1,k)$，因为在插入这个数以前，一共有 $n-1$ 个数，由于是圆排列，环上的空位数量还是 $n-1$ 个，所以乘起来。 边界条件也是非常的明显是 dp[0][0]=1 。 123456dp[0][0] = 1;for(int i = 1; i <= n; i++) { for(int j = 1; ...