【拾题杂谈】LuoguP3679 [CERC2016] 二分毯 Bipartite Blanket
题目大意大秦为你打开题目传送门
题目描述在二分图中，所有点被划分成了两个不相交的集合 $A$ 和 $B$，每条边都恰好连接着某个 $A$ 和某个 $B$。一个匹配是一个边集，满足没有任何两条边有相同的端点。我们称一个匹配 $M$ 覆盖了点集 $V$ 当且仅当 $V$ 中的每个点都是 $M$ 中至少一条边的端点。
给定一个二分图，每个点有一个正整数权值。定义一个点集的权值为其中所有点的权值之和。
给定一个参数 $t$，请统计有多少点集 $V$，满足 $V$ 的权值不小于 $t$，且 $V$ 被至少一个匹配 $M$ 覆盖。
输入格式第一行包含两个正整数 $n,m$，分别表示 $A$ 集合的点数和 $B$ 集合的点数。
接下来 $n$ 行，每行 $m$ 个 01 字符，其中第 $i$ 行第 $j$ 列为 $1$ 表示 $A_i$ 和 $B_j$ 之间有一条边。
接下来一行包含 $n$ 个正整数 $v_1,v_2,\cdots,v_n$，分别表示 $A$ 中每个点的权值。
接下来一行包含 $m$ 个正整数 $w_1,w_2,\cdots,w_m$，分别表示 $B$ 中每个点的权值。
最后一行 ...
【算法介绍】李超线段树
文章总览：百脉甘津宁神久李超线段树，是一种维护带斜率的线段信息的线段树，早就听说了，所以今天跑过来填坑了。李超线段树也是属于线段树的变种，主要的应用也就是刚刚说的维护带斜率线段。并且因为他能维护这种特殊的几何结构，也可以用来编写斜率优化DP，所以说也算是比较重要的数据结构了。
下为本文大纲：
李超线段树推导
李超线段树模板
李超树应用基础
李超数应用斜优
算法推导：壶中洞天云螭眠
李超线段树推导
主要思想：云吟那么刚刚也说了，李超线段树就是一种维护带斜率的线段的线段树，一般来说查询的都是在一条垂直于 $x$ 轴的是线上我们插入的线段与其的交点中最顶端（纵坐标最大）的那一个。
很显然，我们对于每一个节点，只需要存储我们查询的时候的答案（我们将其称之为优势线段）即可。现在的问题是如何快速处理这个所谓的优势线段。
不难想到分类讨论处理插入的情况。如果插入的情况搞定了，查询就是易如反掌。
基础结构：雷音有了大概的思路，我们可以考虑以什么样的载体来存储这个李超线段树。很显然我们面对的是一个非常大的区间，毕竟每个线段的左右端点可以到 $x$ 轴很远很远的地方，那么这种时候我们就只有一种选择： ...
【奇技淫巧】费用流杂题选讲
T1 - Farm Tour题目传送门
题目大意现在有 $N$ 个节点，有 $M$ 条边，要从 $1$ 走到 $N$ 然后再回到 $1$。要求走的边不能重复，求最短路径。
解题思路很简单，我们直接把这个图作为网络的一部分，然后另外开一个源点和汇点，发送 2 的流量，走出来的一个最小费用最大流就是我们想要的答案。
正确代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149 ...
【算法介绍】点分治算法
文章总览：一心二用之术这个算法其实之前写过，但是写的一塌糊涂，所以说这里重新写了。这篇文章的主要内容是点分治算法，另外会额外拓展一些点分树的内容。点分治很显然就是基于点的分支，其详细内容会在下文介绍，大体分类属于树分治。本文讲述点分治与点分树，树分治就还剩下一个边分治了，接下来是本文大纲：
点分治思想
点分治例题
点分树思想
点分树例题
算法推导：理清逃跑路线那么还是来介绍一下点分治的概念。点分治呢其实是一种基于点在树上的分治，它基于点与树上路径的关系来快速统计一些树上路径的信息。在点分治中，路径可以分为两类：
经过当前根的。这个又可以分为端点为根或者两个端点都不为根。
不经过当前根的。
显然第一类中的第二个情况是可以通过第一个情况造成了两个链拼接而成，而不经过当前根的我们需要接下去递归处理，所以说这里是关于点分治正确性的一些简单证明。
然后我们来思考一个问题，点分治的分治逻辑是什么。因为说一般来讲树都是无根树，我们递归的顺序可以非常明显的影响到我们的复杂度。这个就不难想到是用重心了，因为重心每一次可以排除掉这棵树 $1/2$ 的大小，大大节约了我们的复杂度，这样的话点分治除去 ...
【奇技淫巧】斜率优化DP的几何理解
之前是讲过斜率优化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 问题
文章总览：高大的背影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|$；
零向量： ...
【算法介绍】常见平衡树——Treap
文章总览：一心平衡树是我 114514 年前就说要学的知识点，结果拖到现在……甚至这个封面都是今年春节前就做好了qwq。因为我太菜了，这篇文章主要讲的内容是普通的二叉搜索树和两种 Treap（或许封面得改成 Treap 专题？
下为本文大纲：
二叉搜索树概念简介
二叉搜索树分段推导
二叉搜索树优劣分析
无旋 Treap 基本概念
无旋 Treap 思想模拟
无旋 Treap 区间操作
无旋 Treap 综合例题
带旋 Treap 思想简介
带旋 Treap 分段实现
带旋 Treap 代码一览
两类 Treap 对比分析
前置知识：二观
二叉搜索树概念简介
二叉搜索树分段推导
二叉搜索树优劣分析
概念讲解：幽府说起二叉搜索树，各位并不陌生，在很久很久以前，我曾写过这样一篇文章：
友情链接：
【算法介绍】笛卡尔树 | 祝馀宫
这里面提到的笛卡尔树，也是二叉搜索树的一种。不过那篇文章并没有详细解释二叉搜索树的详细定义与编码方式，所以说作为平衡树重要的前置知识，我们把二叉搜索树一并在这里讲了。
首先我们来简单介绍一下二叉搜索树的概念。
规定每个节点有一个附加权值。
左子树和右子树 ...