
## 欠拟合与过拟合

神经网络的本质是在大量的数据中寻找不变的规律，或**模式**。对于学习模式，可以有两种方式：一是简单地让模型“记忆”给定的数据集，二是让模型通过数据集“理解”数据的分布特征。前者一般在离散的小数据集上表现较好，而后者在更大的数据集（尤其是训练数据远小于预测数据范围时）通常有更好的表现。

### 泛化误差与训练误差

如何去衡量这二者的优劣呢？我们给出**训练误差**（training error）和**泛化误差**（generalization error）。我们称模型在学习数据集中的数据后再进行预测的误差为训练误差，而在陌生数据集上（如真实数据应用）产生的误差为泛化误差。显然，我们希望泛化误差尽可能地小，来更好地适应实际应用。

而一个很现实的问题是，在模型训练阶段，我们通常只能获得训练误差，而很难获得准确的泛化误差。那是否可以简单地认为训练误差约等于泛化误差呢？在统计学中，格里文科–康特利定理指出：

> 当样本量趋于无穷大时，样本的经验分布函数几乎必然一致收敛到总体的真实分布函数。

也就是说，当训练数据集足够大时，训练误差几乎必然等于泛化误差。

定理考虑了训练数据和测试数据均符合**独立同分布假设**（i.i.d. assumption），即采样过程关于采样顺序并没有关联。在现实中，我们很难找到一个完美符合独立同分布假设的应用场景，甚至有些会严重违背这一假设。一个简单的例子是使用大学生的人脸图像训练针对老年人的人脸识别系统，这显然不符合上述假设，因为大学生与老年人有很大的差异。

即便假定数据符合独立同分布假设，解释泛化性也是一个极其困难的问题。实践上，我们希望在训练误差尽可能小的基础上，同时使泛化误差与训练误差的差较小。如果一个模型在训练中表现得过于完美，那么其泛化能力就会令人担忧，导致模型过拟合。

一个模型的泛化性很大程度上取决于模型复杂性。实践中，我们一般认为模型的复杂度与可调整参数的数量（或**自由度**）、参数的取值范围、训练数据的数量高度相关。当我们使用更简单的模型和大量的数据时，我们期望泛化误差和训练误差相近；而模型更复杂且样本更少时，尽管训练误差会毫无疑问地下降，泛化误差可能会增大。下图展示了模型复杂度对拟合程度的影响。

![capacity-vs-error](https://blog.samzhangjy.com/assets/posts/nn-optimize/capacity-vs-error.svg)

### 训练集、测试集与验证集

那什么样的模型是合适的呢？我们需要使用某种方法来衡量训练误差和泛化误差。我们可以通过模型在训练集上的表现来确定训练误差，而泛化误差的获得则要复杂些。直接使用测试集进行预测是不可取的：这会导致模型选择过程中不可避免地倾向于选择泛化程度高即测试集误差小的模型，进而导致测试集被过拟合。这一现象也称作测试集泄露。

一个常见的做法是采用独立于训练集和测试集之外的第三个数据集——**验证集**（validation set），通过获得模型在验证集上的表现来尽可能估算泛化误差。

实践中，可供我们使用的数据集通常是有限的，我们需要尽可能使用每一个样本进行训练。上述方法显然占用了过多的数据用于测试和验证，这压缩了训练集的数量。我们通常可以采用 K 折交叉验证的方式构成验证集。我们先将训练集分为 K 个不重叠的子集，然后进行 K 次模型训练与验证。每次训练中，我们对 K - 1 个子集构成新的训练集，对于剩余的 1 个子集则留为验证集，最后取 K 次实验的结果取平均值估计误差。

## 权重衰减

我们知道，扩大数据集规模可以提高模型的泛化能力，缓解过拟合问题。另一种有效的方式是采用**权重衰减**（weight decay）的方法来环节过拟合。前文提到，模型复杂度与参数的数量和取值范围相关。不难发现，单单调节模型参数数量带来的拟合情况可能过于粗糙，无法精细调节模型拟合程度。于是，我们可以考虑使用限制参数的取值范围来细粒度调节拟合程度。

为什么限制参数取值范围可以调整拟合程度呢？一个很简单的例子是线性回归：$\hat{\mathbf{y}} = \mathbf{Wx} + \mathbf{b}$ ，当权重 $\mathbf{W}$ 很大时，输入值 $\mathbf{x}$ 一点点细微的改变就会导致预测值 $\hat{\mathbf{y}}$ 发生极大的改变，而实际情况可能是更为平滑的。所以，限制参数的取值范围可以一定程度上降低过拟合风险，提高泛化能力。

### 范数与正则化

我们希望限制模型的复杂性。从直觉上来讲，我们模型拟合出的函数 $f$ 越接近函数 $f = 0$ 时，模型越简单。那么我们的任务也就是衡量模型与 $f = 0$ 之间的距离。这与模型参数的范数密切相关，此处简单介绍一下线性代数中范数与正则化相关概念。

形象地说，**范数**（norm）表示一个向量的分量的大小。这不难联系到平面几何中欧几里得距离的概念。事实上，欧几里得距离是一个 $L_2$ 范数，表示为：

$$
\|\mathbf{x}\|_2 = \sqrt{\sum_{i=1}^n x_i^2},
$$

即向量元素平方和的平方根。同时我们也有 $L_1$ 范数，表示为向量元素的绝对值之和：

$$
\|\mathbf{x}\|_1 = \sum_{i=1}^n \left|x_i \right|.
$$

更一般地，我们有 $L_p$ 范数：

$$
\|\mathbf{x}\|_p = \left(\sum_{i=1}^n \left|x_i \right|^p \right)^{1/p}.
$$

深度学习中，以 $L_1$ 范数和 $L_2$ 范数最为常用，分别对应 $L_1$ 正则化和 $L_2$ 正则化。

所谓**正则化**（regularization），即对原始损失函数引入额外信息，防止过拟合和提高模型泛化能力的一类方法。可以认为，正则化在原始损失函数 $L_0$ 的基础上增加了关于参数的惩罚项，即 $L = L_0 + l$ 。

### $L_2$ 正则化

而权重衰减属于正则化技术的一种，也称为 **$L_2$ 正则化** 。对于线性回归中的均方误差损失，我们的初始损失表达为：

$$
L(\mathbf{w}, b) = \frac{1}{n}\sum_{i=1}^n \frac{1}{2}\left(\mathbf{w}^\top \mathbf{x}^{(i)} + b - y^{(i)}\right)^2.
$$

按照正则化的概念，我们应该在原始损失函数的基础上添加正则化项，使得模型的训练目标由“最小化预测与实际值之间的差异”转变为“在最小化预测与实际值之间的差异的基础上，尽可能使模型简单”。那么我们的新损失函数就是：

$$
L(\mathbf{w}, b) + \frac{\lambda}{2} \|\mathbf{w}\|^2_2,
$$

其中 $\lambda$ 是可以调节的超参数。实践上一般取 $\lambda = 0$ ，寻找最优学习率，而后在最优学习率固定的情况下从 $\lambda = 1$ 开始以 10 倍为标准放大/缩小 $\lambda$ ，找到合适的数量级，而后进行微调确定最终的 $\lambda$ 。

从上式可以看出，$L_2$ 正则化对过大的参数施加了巨大的惩罚，导致模型倾向于更小的参数，来避免过拟合。而 $L_1$ 正则化可以使参数稀疏化，只保留对模型由重要作用的特征，用于特征选择。

## Dropout

深层神经网络对比线性网络一个重要的不同是隐藏层的存在，这使得模型可以考虑不同特征之间的关联。一个好的预测模型，正如上文所述，应该是简单的，且在未知数据上有较好的表现。$L_2$ 正则化考虑了模型参数大小的简单性，而 **Dropout**（暂退法）则关注模型的平滑性，即一些噪声不应该对整体预测结果产生较大的影响。

那么，为了增强网络对抗噪声的能力，我们可以考虑手动在网络中加入一定噪声。这种方法就是 Dropout 法。Dropout 在前向传播中，对每一层加入噪声。标准的 dropout 会在训练中将某些神经元的活性值置为 $0$ ，即丢弃某些神经元，进而从某些程度上降低网络对于其他神经元的高度依赖，迫使网络学习更有泛化性的特征。

在标准 dropout 中，我们有：
$$
\begin{split}\begin{aligned}
h' =
\begin{cases}
    0 & \text{ 概率为 } p \\
    \frac{h}{1-p} & \text{ 其他情况}
\end{cases}
\end{aligned}\end{split}
$$
其中，$\frac{h}{1-p}$ 是对参数大小的缩放，确保了模型在后续测试时的参数值仍然有效。

实际应用中，我们可以将 dropout 应用到多层感知机中，降低模型过拟合。下图是一个例子。

![dropout](https://blog.samzhangjy.com/assets/posts/nn-optimize/dropout.svg)

具体地说，我们在训练过程中，对于每一次 epoch ，都重新生成一个 dropout 神经元的集合，从而变相地在训练过程中同时训练了多个神经网络。从某种意义上说，dropout 也是在使用多次求值取平均的思想来降低过拟合。

一般来讲，dropout 只在训练时使用，测试时不采用 dropout 。


浅谈模型优化


## 隐藏层

简单的单层网络（如前文提到的线性回归）对比真正的深层神经网络有一个很大的不同：前者只能拟合出输入值和输出值之间的**线性**关系，而后者可以拟合逼近出任意的复杂函数关系。这其中的差别在于层数不同，也就是**隐藏层**（hidden layer）的存在与否。

在线性回归中，我们通过单个仿射变换 $\mathbf{Y} = \mathbf{Wx} + \mathbf{b}$ 进行模型预测，由输入直接映射到输出。假设我们的目标关系是线性相关的（如之前学习时间和成绩的例子的假设），那么线性回归的确可以很好地处理这些问题。但是大部分的函数关系并不是线性的，例如拟合一个目标函数 $y = x^2 + 2x$ ，线性回归无法通过线性变换对其进行很好的拟合，损失始终会很大。

于是我们考虑在网络中加入一个或多个隐藏层来克服线性模型的限制。一个很朴素的方法是简单堆叠多个全连接层，最后一个隐藏层与输出层相连，这就构成了**多层感知机**（multilayer perceptron）。如下图就是一个有一层隐藏层的多层感知机的模式图。

![mlp](https://blog.samzhangjy.com/assets/posts/mlp/mlp.svg)

我们来看一下多层感知机的计算过程。假定有样本 $\mathbf{X}$ ，**隐藏表示** $\mathbf{H}$ 即隐藏层的输出为单隐藏层的输出，隐藏层权重为 $\mathbf{W}^{(1)}$ ，偏置 $\mathbf{b}^{(1)}$ ，输出层权重 $\mathbf{W}^{(2)}$ ，偏置 $\mathbf{b}^{(2)}$ ，多层感知机输出为 $\mathbf{O}$  ，则：

$$
\mathbf{H} = \mathbf{W}^{(1)}\mathbf{X} + \mathbf{b}^{(1)},\\
\mathbf{O} = \mathbf{W}^{(2)}\mathbf{H} + \mathbf{b}^{(2)}.
$$

但是不难发现，上述表达并没有对网络的既定线性关系做出本质的改变。上述网络仍可以等价于一个单层线性网络 $\mathbf{O} = \mathbf{W}^{(1)}\mathbf{W}^{(2)}\mathbf{X} + \mathbf{b}^{(1)}\mathbf{W}^{(2)} + \mathbf{b}^{(2)}$ 。这就需要我们引入一个新的机制：**激活函数**（activation function）$\sigma$ 。其输出被称为**活性值**（activations）。那么上述的多层感知机网络变化为：

$$
\begin{aligned}
\mathbf{H} &= \sigma(\mathbf{W}^{(1)}\mathbf{X} + \mathbf{b}^{(1)}),\\
\mathbf{O} &= \mathbf{W}^{(2)}\mathbf{H} + \mathbf{b}^{(2)}.
\end{aligned}
$$

一般来讲，隐藏层经过激活函数的变换后，网络就不会退化为线性网络。当然，上述隐藏层也可以进行堆叠，增强模型的表达能力。

## 激活函数

那么使得网络具有非线性特征的激活函数是什么呢？

激活函数的本质是通过计算加权和并加上偏置确定神经元是否应该被激活，大多数都是非线性的。事实上，线性神经网络中也存在线性激活函数 $\sigma(x) = x$ 。激活函数的存在是深度学习网络能够学习复杂特征的基础。

### sigmoid 函数

对于任意 $x \in \mathbb{R}$ ，sigmoid 函数可以将其值压缩到 $(0, 1)$ 区间内。其定义为：

$$
\operatorname{sigmoid}(x) = \frac{1}{1 + \exp(-x)}.
$$

可以发现其与 softmax 函数（$\operatorname{softmax}(x) = \frac{\exp(o_j)}{\sum_k\exp(o_k)}$）具有相似的运算性质。事实上，sigmoid 函数可以看作 softmax 函数的特例，在二分类问题上可以与 softmax 函数进行等价。

![sigmoid](https://blog.samzhangjy.com/assets/posts/mlp/sigmoid.svg)

![sigmoid-grad](https://blog.samzhangjy.com/assets/posts/mlp/sigmoid-grad.svg)

上图是 sigmoid 函数和其导数的图像。可以发现，其在 $x$ 接近 $0$ 时表现接近线性变换，此时具有较好的激活性；而在正负饱和区（$|x|$ 较大时）梯度接近 $0$ 。这一缺陷将会导致训练中出现梯度消失，减缓模型的收敛速度。

### tanh 函数

与 sigmoid 函数类似，tanh （双曲正切）函数也可以将 $x$ 压缩到有限区间 $(-1, 1)$ 上，其定义为：

$$
\operatorname{tanh}(x) = \frac{1 - \exp(-2x)}{1 + \exp(-2x)}.
$$

![tanh](https://blog.samzhangjy.com/assets/posts/mlp/tanh.svg)

![tanh-grad](https://blog.samzhangjy.com/assets/posts/mlp/tanh-grad.svg)

tanh 函数和其导数的图像如上图所示。其性质大体与 sigmoid 函数类似，但图像关于原点对称。这在前馈网络中是一个较好的性质，保证了信息在层间传递时均值为 $0$ ，使得模型训练收敛更快。

但同样地，tanh 函数也具有和 sigmoid 函数一样的梯度消失问题，在实践中很少使用。sigmoid 系激活函数的部分应用场景是循环神经网络。

### ReLU 函数

最受欢迎的激活函数是 **修正线性单元** （Rectified Linear Unit, ReLU）。其实现简单，且在多种预测任务中表现良好。其定义如下：

$$
\operatorname{ReLU}(x) = \max(x, 0).
$$

形象地来讲，ReLU 的作用在于屏蔽了 $x < 0$ 部分的输入，即单侧抑制。其函数和导数图像如图所示。

![ReLU](https://blog.samzhangjy.com/assets/posts/mlp/relu.svg)

![ReLU-grad](https://blog.samzhangjy.com/assets/posts/mlp/relu-grad.svg)

下面简单探讨一下为什么 ReLU 具有比较优秀的性能。

可以发现，ReLU 函数在负半区的导数为 0 ，导致神经元不被激活。这将会使得网络具有稀疏性，提高了网络的计算效率。稀疏性的出现使得神经元只对输入信号的少部分选择性响应，其余的信号被刻意屏蔽了。这样可以提高学习精度，提高特征的鲁棒性，降低模型的过拟合风险。

同时，ReLU 并没有 sigmoid 系函数的正负饱和区，其梯度始终是 1 ，属于单端饱和，有效减轻了训练中的梯度消失问题。


浅谈多层感知机


## 分类问题

回归可以用于预测**多少**的问题，如房价、住院天数；分类模型则可以用于判断某一目标是否属于某一**类别**。对于分类问题，我们又有*硬性*和*软性*分类，前者只希望得到目标的类别，后者则还需要目标属于每个类别的概率大小。实践中，即便对于硬分类问题，我们也采用软分类算法解决。

假设我们有一个图像分类问题，输入为 $2 \times 2$ 的灰度图像，类别可能是猫、狗、鸡中的一个。

那么，我们的输入特征就是像素值 $\mathbf{x} = x_1, x_2, x_3, x_4$ 。而对于类别的表示，我们采用**独热编码**（one-hot encoding）的方式：独热编码是一个和类别数目分量一致的向量，某一类别的独热编码表示为该类别对应分量为 $1$ ，其余分量为 $0$ 。在上述例子中，我们可以假定向量 $(1, 0, 0)$ 表示猫，$(0, 1, 0)$ 表示狗，$(0, 0, 1)$ 表示鸡。那么我们的标签 $y \in {(1, 0, 0), (0, 1, 0), (0, 0, 1)}$ 。

## softmax 回归

与前文中线性回归模型不同，分类问题需要模型有多个输出来对应每个类别。为此，我们需要和类别数量一样多的**仿射函数**（affine function），即通过线性变换和平移变换后得到的函数。例如，我们需要 $12$ 个标量来表示上例中的权重：

$$
o_1 = x_1w_{1,1} + x_2w_{1, 2} + x_3w_{1, 3} + x_4w_{1, 4} + b_1\\
o_2 = x_1w_{2,1} + x_2w_{2, 2} + x_3w_{2, 3} + x_4w_{2, 4} + b_2\\
o_3 = x_1w_{3,1} + x_2w_{3, 2} + x_3w_{3, 3} + x_4w_{3, 4} + b_3\\
$$


![](https://blog.samzhangjy.com/assets/posts/softmax-regression/softmax-nn.svg)

形式化地，softmax 回归的模型可以表达为 $\mathbf{o} = \mathbf{Wx} + \mathbf{b}$ 。如上图所示，softmax 回归是一个单层的全连接的神经网络。这样的全连接层虽然性能开销较大，但便于理解。

根据前文中对于分类问题的一般定义，我们知道，分类模型的输出需要是检测目标属于每个类别的概率大小。那么对于硬分类问题我们可以选择最大输出值的类别 $\arg\max_i\hat{y}_i$ 作为预测，对于软分类问题直接给出 $\hat{y}$ 即可。

考虑输出 $o_i$ ，其值可以根据输入特征和权重的变换在整个 $\R$ 上变化，这显然违背了基本的概率公理。进一步地，我们需要使整个输出的加和等于 $1$ ，即 $\sum_{i=1}^{n}o_{i} = 1$ 。为此，我们需要一个方法来标准化模型输出。这一操作可以通过 **softmax 函数** 来实现。softmax 函数可以将未规范化的预测变换为非负数且总和为 $1$ ，同时保持模型可导的性质。这一绝佳的函数性质十分适合作为分类问题的目标函数：

$$
\hat{\mathbf{y}} = \text{softmax}(\mathbf{o})
$$

其中

$$
\hat{y}_j = \frac{\exp(o_j)}{\sum_k\exp(o_k)}.
$$
因此，$\hat{\mathbf{y}}$ 可以视作一个正确的概率分布。尽管不难看出，softmax 函数并非一个线性函数，但 softmax 回归的输出仍然由输入特征的仿射变换决定，因此仍是一个线性模型。

## 损失函数

我们需要一个确定模型拟合程度好坏的度量，该度量被称作**损失函数**（loss function），能够量化目标的实际值与预测值之间的差距。损失通常是非负的，且数值越小代表损失越小。

### 平方损失函数

对于回归问题，最常用的损失函数为**平方损失函数（Square Error Function）**：

$$
l^{(i)}(\mathbf{w}, b) = \frac{1}{2}(\hat{y}^{(i)} - {y}^{(i)})^2.
$$

常数 $\frac{1}{2}$ 的意义在于使 $l$ 的导数常数系数为 1 。对于整个数据集，我们有：

$$
L(\mathbf{w}, b) = \frac{1}{n} \sum^n_{i = 1}l^{(i)}(\mathbf{w}, b) = \frac{1}{n}\sum^{n}_{i = 1}\frac{1}{2}(\mathbf{w}^{\top}\mathbf{x}^{(i)} + b - y^{(i)})^2 .
$$

我们训练模型的过程即寻找一组参数 $\mathbf{w}^*,b^*$ ，使得 $L(\mathbf{w}^*,b^*)$ 最小。那么如何求得这一组最优参数呢？

### 随机梯度下降

**梯度下降**（gradient descent）是一种通过不断地在损失函数递减的方向上更新参数来降低误差的方法，广泛应用于各类深度学习模型上。这其中，梯度即代表损失函数关于模型参数的导数。

为了避免在每一次更新时遍历一遍数据集，我们通常会在每次需要更新的时候随机抽取一小批样本，即**小批量随机梯度下降（minibatch stochastic gradient descent）**。

在每次迭代时，我们首先随机抽样一个容量固定的小批量 $\mathcal{B}$ ，并计算小批量的平均损失关于模型参数的偏导数。最后，我们将梯度乘以一个预先确定的正数 $\eta$（**学习率，learning rate**），并从当前参数的值中减掉。

形式化地，对于每次迭代，我们有：

$$
(\mathbf{w}, b) \larr (\mathbf{w}, b) - \frac{\eta}{\vert\mathcal{B}\vert} \sum_{i \in \mathcal{B}}\partial_{(\mathbf{w}, b)}l^{(i)}(\mathbf{w}, b) .
$$

其中

$$
\partial_{(\mathbf{w}, b)}l^{(i)}(\mathbf{w}, b) = \left(\frac{\partial l^{(i)}}{\partial \mathbf{w}}, \frac{\partial l^{(i)}}{\partial b}\right)
$$

对于类似 $\eta$ 和 $\vert\mathcal{B}\vert$ （**批次大小，batch size**） 的可以调整但是不在训练过程中的参数我们成为**超参数（hyperparameter）**。**调参（hyperparameter tuning）** 即选择超参数的过程。

需要注意的是，即便函数完全遵循线性回归且无噪声，模型参数 $\hat{\mathbf{w}}$ ，$\hat{b}$ 也不会达到实际最小值，而是无限接近最小值。对于较为复杂的深度神经网络，损失平面通常包含多个最小值。实践上一般不会追求训练集上的最小损失，而是追求能在陌生数据上实现较小损失。这一过程即**泛化（generalization）**。

### 交叉熵损失函数

让我们回到 softmax 回归。

softmax 函数让模型输出标准化为概率，如 $\hat{y}_1 = P(y = 猫 \mid \mathbf{x})$ 。假设数据集 $\{\mathbf{X}, \mathbf{Y}\}$ 有 $n$ 个样本，其中特征向量为 $\mathbf{x}^{(i)}$ ，独热标签向量（ground truth）为 $\mathbf{y}^{(i)}$ 。那么我们有：

$$
P(\mathbf{Y} \mid \mathbf{X}) = \prod^n_{i = 1}P(\mathbf{y}^{(i)}\mid \mathbf{x}^{(i)}).
$$

我们称上式为整个数据集的**似然**（likelihood），其中 $P(A \mid B)$ 表示 A 在 B 发生的条件下发生的概率。

#### 似然

让我们先回顾一下模型的本质。

在概率模型里，我们认为数据是从某个分布里“采样”来的。也就是说，世界上所有猫的照片，都是从某个潜在分布 $P_{真实}(x)$ 中抽取的样本。所谓分布，即决定随机变量可能出现的“规律”，它告诉我们每个可能结果出现的概率有多大。我们显然只能获得从真实分布中抽取到的有限大小的样本，而我们希望模型从这些有限大小的样本中尽可能拟合出真实的分布。

似然，即当模型参数一定时，观察到数据的“可能性”大小。具体地，假设我们有一个参数为 $\theta$ 的模型，其有一个概率分布 $P(x \mid \theta)$ 。我们又有一组真实数据 $x_{\text{obs}}$ ，那么似然函数 $L(\theta) = P(x_{\text{obs}} \mid \theta)$ ，即在参数为 $\theta$ 时我们有多可能观测到 $x_{\text{obs}}$ 这一数据。相对于概率计算的是参数固定的情况下不同数据有多可能出现，似然计算的是数据固定的前提下，不同参数时的分布下这个数据有多可能出现。

我们通常要找让似然最大的参数，其根本原因在于我们试图找到一个概率分布 $P(x \mid \theta)$ ，使得这一分布尽可能接近真实世界中的概率分布。我们的计算也就是在求 $\hat{\theta}_{\text{MLE}} = \arg\max_{\theta}L(\theta)$ ，其中 $L(\theta)$ 为似然函数。

回到交叉熵损失中，根据最大似然估计，我们最大化 $P(\mathbf{Y} \mid \mathbf{X})$ ，相当于最小化负对数似然：

$$
-\log P(\mathbf{Y} \mid \mathbf{X}) = \sum_{i = 1}^n -\log P(\mathbf{y}^{(i)} \mid \mathbf{x}^{(i)}) = \sum_{i = 1}^n l(\mathbf{y}^{(i)}, \hat{\mathbf{y}}^{(i)}).
$$

即损失函数为

$$
l(\mathbf{y}, \hat{\mathbf{y}}) = - \sum_{j=1}^q y_j \log \hat{y}_j.
$$

我们称 $l$ 为**交叉熵损失函数**（cross-entropy loss function）。至于最小化负对数似然的原因，其一是由于对数运算的性质 $\log ab = \log a + \log b$ 更便于梯度计算且对数函数单调递增，二是取负号方便进行最小化，满足损失函数最小时损失最小的性质，三是对数自然对应了信息量。

#### 信息量

信息论中，我们称能量化数据中信息内容的量为分布 $P$ 的**熵**（entropy）：

$$
H[P] = \sum_j - P(j) \log P(j).
$$

上式中，$P(j)$ 为事件 $j$ 发生的概率，$\log \frac{1}{P(j)} = -\log P(j)$ 为事件 $j$ 的信息量（越不可能发生信息量的值越大）。直观地来讲，如果一件事经常发生，我们不会对它感到惊异，信息量就小；反之，如果一件事很少发生，我们会对其感到惊异，信息量就大。熵 $H[P]$ 也就是通过把每件事发生的概率加权，求出所有可能事件的平均信息量。

那什么是交叉熵呢？我们记交叉熵为 $H(P, Q)$ ，描述一个主观概率为 $Q$ 的观察者在看到根据概率 $P$ 生成的数据时的预期差异。当 $P = Q$ 时，交叉熵达到最低，即 $H(P, P) = H(P)$ 。

回归到交叉熵损失函数中，如果对于某一组数据，真实类别是第 $k$ 类，那么 $y_k = 1$ ，其他全为 $0$ 。损失化简为 $l^{(i)} = -\log \hat{y}_k$ 。 $\hat{y}_k < 0$ ，则 $l^{(i)} > 0$ ，且 $\hat{y}_k$ 越接近 $1$ ，$l^{(i)}$ 越小。也就是说，模型越相信正确类别（$\hat{y}_k$越大），损失越小；反之损失越大。从信息论的角度来讲，交叉熵损失函数实际上是在计算模型输出的概率分布距离真实分布的不匹配度，衡量了预测分布与真实分布之间的差距。 



浅谈 softmax 回归


## 线性回归

**回归（regression）** 即通过建模某个或多个自变量与因变量之间关系，预测某一数值的问题。回归问题预测的数值是连续的；分类则是预测离散数值。

线性回归则是假设自变量 $\mathbf{x}$ 与因变量 $y$ 之间具有线性关系，且观测数据噪声遵循正态分布。一般地，我们把试图预测的目标成为**标签（label）**或**目标（target）**，预测所依据的自变量（数据）称为**特征（feature）**或**协变量（covariate）**。一般使用 $n$ 表示数据集样本容量，对于索引为 $i$ 的样本，其输入表示为 $\mathbf{x}^{(i)} = [x_1^{(i)},x_2^{(i)}, \cdots]^{\top}$ ，对应标签为 $y^{(i)}$ 。

### 线性模型

首先，给出线性模型的一般定义式：
$$
\hat{y} = \mathbf{w}^{\top}\mathbf{x} + b.
$$
其中 $\mathbf{w}$ 表示模型**权重（weight）**，$b$ 表示**偏置（bias）**，$\mathbf{x}$ 表示单个数据样本的特征。对于特征矩阵 $\mathbf{X} \in \R^{n \times d}$ ，我们同样有：
$$
\hat{\mathbf{y}} = \mathbf{Xw} + b.
$$
线性模型中，偏置项的意义在于提升模型的表达能力，其物理意义即为当所有特征取值都为 0 时，预测值应该为多少。上述二式即代表对于输入特征的**仿射变换（affine transformation）**，即通过加权对特征进行**线性变换（linear transformation）**，并通过偏置项进行**平移（translation）**。

> 矩阵乘法即对于张空间内的向量进行变换。

我们的任务就是对于给定的特征数据集，找到一组最优的 $\mathbf{w}, b$ 来拟合给定的标签，即寻找最优模型参数。

### 损失函数

**损失函数（loss function）**能够量化目标的实际值与预测值之间的差距。通常我们有损失 $\geq 0$ ，且数值越小损失越小，完美预测时损失为 0 。回归问题中最常用的损失函数为**平方损失函数（Square Error Function）**：
$$
l^{(i)}(\mathbf{w}, b) = \frac{1}{2}(\hat{y}^{(i)} - {y}^{(i)})^2.
$$
常数 $\frac{1}{2}$ 的意义在于使 $l$ 的导数常数系数为 1 。对于整个数据集，我们有：
$$
L(\mathbf{w}, b) = \frac{1}{n} \sum^n_{i = 1}l^{(i)}(\mathbf{w}, b) = \frac{1}{n}\sum^{n}_{i = 1}\frac{1}{2}(\mathbf{w}^{\top}\mathbf{x}^{(i)} + b - y^{(i)})^2 .
$$

### 随机梯度下降

尽管对于线性回归，我们可以通过最小化 $\Vert\mathbf{y} - \mathbf{Xw}\Vert^2$ 求出其解析解 $\mathbf{w}^* = (\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\mathbf{y}$ ，但在大部分深度学习模型中，我们无法简单通过解析解来获得最优参数。**梯度下降（gradient descent）**正是一中可以通过不断地在损失函数递减的方向上更新参数来降低误差的方法。

梯度下降的一般定义即是在迭代时计算损失函数均值关于模型参数的偏导数（通过链式法则，也称梯度），但效率极低。为了避免在每一次更新时遍历一遍数据集，我们通常会在每次需要更新的时候随机抽取一小批样本，即**小批量随机梯度下降（minibatch stochastic gradient descent）**。

在每次迭代时，我们首先随机抽样一个容量固定的小批量 $\mathcal{B}$ ，并计算小批量的平均损失关于模型参数的偏导数。最后，我们将梯度乘以一个预先确定的正数 $\eta$（**学习率，learning rate**），并从当前参数的值中减掉。

形式化地，对于每次迭代，我们有：
$$
(\mathbf{w}, b) \larr (\mathbf{w}, b) - \frac{\eta}{\vert\mathcal{B}\vert} \sum_{i \in \mathcal{B}}\partial_{(\mathbf{w}, b)}l^{(i)}(\mathbf{w}, b) .
$$
对于类似 $\eta$ 和 $\vert\mathcal{B}\vert$ （**批次大小，batch size**） 的可以调整但是不在训练过程中的参数我们成为**超参数（hyperparameter）**。**调参（hyperparameter tuning）**即选择超参数的过程。

需要注意的是，即便函数完全遵循线性回归且无噪声，模型参数 $\hat{\mathbf{w}}$ ，$\hat{b}$ 也不会达到实际最小值，而是无限接近最小值。对于较为复杂的深度神经网络，损失平面通常包含多个最小值。实践上一般不会追求训练集上的最小损失，而是追求能在陌生数据上实现较小损失。这一过程即**泛化（generalization）**。

### 噪声与正态分布

若随机变量 $x$ 具有均值 $\mu$ 和方差 $\sigma^2$ ，其正态分布概率密度函数如下：
$$
p(x) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp(-\frac{1}{2\sigma^2}(x - \mu)^2) .
$$
改变均值会产生沿 $x$ 轴的偏移，增加方差会分散分布、降低峰值。

而均方误差损失函数可以用于线性回归的原因之一是我们假设了观测中包含噪声，而噪声服从正态分布：
$$
y = \mathbf{w}^{\top}\mathbf{x} + b + \epsilon.
$$
通过给定的 $\mathbf{x}$ 观测到特定 $y$ 的**似然（likelihood）**为：
$$
p(y \mid \mathbf{x}) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp(-\frac{1}{2\sigma^2}(y - \mathbf{w}^{\top}\mathbf{x} - b)^2) .
$$
对于整个数据集的似然，即为：
$$
P(\mathbf{y} \mid \mathbf{X}) = \prod^n_{i = 1}p(y^{(i)}\mid \mathbf{x}^{(i)}) .
$$
通过最小化负对数似然，得：
$$
-\log P(\mathbf{y} \mid \mathbf{X}) = \sum^n_{i = 1}\frac{1}{2}\log(2\pi\sigma^2) + \frac{1}{2\sigma^2}(y^{(i)} - \mathbf{w}^{\top}\mathbf{x}^{(i)} - b)^2 .
$$
剔除式中常数项，该式即等价于最小化均方误差。

浅谈线性回归


## 并查集

并查集是一种用于管理元素所属集合的数据结构，

并查集支持两种操作：

- 合并（`merge`）：合并两个节点所属的结合（合并两个树）
- 查询（`find`）：查询某个节点所对应的集合

使用路径压缩后的并查集的平均时间复杂度为 $O(\alpha(n))$ ，其中 $\alpha(n)$ 表示阿克曼函数的反函数。在宇宙可观测的 $n$ 中，$\alpha(n) \leq 5$ ，即路径压缩后的平均时间复杂度为渐进 $O(1)$ 。但是，可以构造特殊数据使得朴素路径压缩（没有进行按秩合并）的并查集实现达到单次查询 $O(\log n)$ 的最坏时间复杂度。具体证明和验证见 <https://leetcode.cn/problems/number-of-provinces/solutions/550060/jie-zhe-ge-wen-ti-ke-pu-yi-xia-bing-cha-0unne/> 以及 <https://oi-wiki.org/ds/dsu-complexity/#%E4%B8%BA%E4%BD%95%E5%B9%B6%E6%9F%A5%E9%9B%86%E4%BC%9A%E8%A2%AB%E5%8D%A1> 。一般情况下可以认为并查集实现为均摊 $O(1)$ 。

若追求严格 $O(1)$ ，可以通过按秩合并或启发式合并实现最坏 $O(\alpha(n))$ 即均摊 $O(1)$ 的时间复杂度。详见 <https://oi-wiki.org/ds/dsu/#%E5%90%88%E5%B9%B6> 。

本文将仅采用路径压缩的朴素并查集。下面给出面向对象的模板代码：

```cpp
class DSU {
private:
    int fa[N];

public:
    DSU() {
        for (int i = 0; i < N; i++) {
            fa[i] = i;
        }
    }

    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    void merge(int u, int v) {
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            fa[fu] = fv;
        }
    }
};
```

注意 `fa[i]` 数组的初始化赋值。

## 例题

### [P2024 [NOI2001] 食物链](https://www.luogu.com.cn/problem/P2024)

#### 题目大意

有 A 吃 B 、B 吃 C 、C 吃 A 三种狩猎关系，保证给出的每个动物都是 A, B, C 中的一种，判断对于每条给定信息是否与先前信息矛盾。输出矛盾信息的总数。

每条信息分为两类：

1. 给定 X 和 Y ，表示 X 和 Y 是同类；
2. 给定 X 和 Y ，表示 X 吃 Y 。

#### 题目分析

显然可以通过种类并查集暴力维护，具体实现方法不在此赘述。此处将主要探讨带权并查集的解法。

不妨对 X, Y 可能产生的所有关系进行枚举。规定如下权值：

- `0` 表示此节点与父节点为同类；
- `1` 表示此节点被父节点吃；
- `2` 表示此节点吃父节点。

随后对每个可能的合法关系进行枚举，得到下表：

| 节点 X 与父关系 | 节点 X 与 Y 关系 |  节点 Y 与父关系|
| :----------: | :----------: | :----------: |
|0  |  0|  0|
|0  | 1 |  1|
|  0| 2 |  2|
|  1|  0|  1|
|  1|  1|  2|
|  1|  2|  0|
|  2|  0|  2|
|  2|  1|  0|
|  2|  2|  1|

设 $w_i$ 表示节点 $i$ 与其父节点的关系。观察规律可得，有 $w_Y = (w_{X,Y}' + w_X) \bmod 3$ 。

其中 $w_{X,Y}'$ 表示 X 与 Y 之间的关系。上式可用于维护并查集的合并操作。

设 F1 , F2 分别为 X 和 Y 的父节点（根），则在更新时有 $w_{F1} = w'_{X,Y} + w_Y - w_X$ 。具体证明可以画图易得。

注意实现时需要注意溢出问题，即 $w_{F1} = (w'_{X,Y} + w_Y - w_X + 3) \bmod 3$ 。

查找时我们需要对并查集进行路径压缩。显然此时我们可以通过 $w_Y'' = (w_Y + w_X) \bmod 3$ ，其中 $w''_Y$ 表示更新后的权值，来更新每一个路径。

对于判断每条信息是否矛盾，我们首先需要判断 F1 与 F2 是否在一个集合中。若不在一个集合中，则表明 X 和 Y 之间没有明确的信息表示它们之间的关系，故不矛盾；否则我们需要分情况讨论：

- 若当前信息为 X 和 Y 是同类，则不矛盾时的情况由上表可知需要满足 $w_X = w_Y$ ，故若 $w_X \neq w_Y$ 时信息矛盾；
- 若当前信息为 X 吃 Y ，则不矛盾时的情况由上表可知需要满足 $w_Y - w_X = 1$ 即 $(w_Y - w_X + 3) \bmod 3 = 1$ 时不矛盾，反之则当前信息矛盾。

至此我们就完成了这道题目主体的分析。可以发现，我们事实上通过该并查集维护了一个在 $\bmod 3$ 意义下的整数加法群。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int n, m, ans = 0;
int fa[N], w[N];
/**
 * 0 = SAME
 * 1 = PREDATOR
 * 2 = PREY
 */

int find(int x) {
    if (fa[x] == x) return x;
    int rFa = find(fa[x]);
    w[x] = (w[x] + w[fa[x]]) % 3;
    return fa[x] = rFa;
}

void merge(int u, int v, int weight) {
    int fu = find(u), fv = find(v);
    if (fu != fv) {
        fa[fu] = fv;
        /**
         * fu ---> fv
         * ↑       ↑
         * u - - > v
         */
        w[fu] = (weight + w[v] - w[u] + 3) % 3;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if (x > n || y > n) {
            ans++;
            continue;
        }
        if (op == 1) {
            int fx = find(x), fy = find(y);
            if (fx == fy && w[x] != w[y]) {
                ans++;
            } else {
                merge(x, y, 0);
            }
        } else {
            int fx = find(x), fy = find(y);
            if (fx == fy && (w[x] - w[y] + 3) % 3 != 1) {
                ans++;
            } else {
                merge(x, y, 1);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}
```

### [P1196 [NOI2002] 银河英雄传说](https://www.luogu.com.cn/problem/P1196)

#### 题目大意

在 $[1, 3 \times 10^4]$ 上有分布不同的数列，定义合并操作为将第 $j$ 列的数列的列首接到第 $i$ 列的列尾。

给定 $T$ 个操作，每个操作分为两类：

- 合并操作，将第 $i$ 列的数列合并到第 $j$ 列之后；
- 查询操作，查询编号为 $i$ 的数和 $j$ 的数是否在同一列中，若在同一列中求 $i$ 和 $j$ 之间有多少个数间隔。

保证 $i \neq j$ 。

#### 题目分析

带权并查集。考虑维护每个数所在队列的总长度 $\text{cnt}_i$ 和其到当前队首的距离 $\text{w}_i$ 。

直接维护即可。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 30010;

int T;
int fa[N], w[N], cnt[N];

int find(int x) {
    if (fa[x] == x) return x;
    int rFa = find(fa[x]);
    w[x] += w[fa[x]];
    cnt[x] = cnt[fa[x]];
    return fa[x] = rFa;
}

void merge(int u, int v, int weight) {
    int fu = find(u), fv = find(v);
    if (fu != fv) {
        fa[fu] = fv;
        w[fu] += cnt[fv];
        cnt[fu] += cnt[fv];
        cnt[fv] = cnt[fu];
    }
}

int main() {
    cin >> T;
    for (int i = 1; i < N; i++) {
        fa[i] = i;
        cnt[i] = 1;
    }
    while (T--) {
        char op;
        int i, j;
        cin >> op >> i >> j;
        if (op == 'M') {
            merge(i, j, 1);
        } else {
            int fi = find(i), fj = find(j);
            if (fi != fj) {
                cout << -1 << '\n';
            } else {
                cout << abs(w[i] - w[j]) - 1 << '\n';
            }
        }
    }
    return 0;
}
```

### [P1525 [NOIP2010 提高组] 关押罪犯](https://www.luogu.com.cn/problem/P1525)

#### 题目大意

给定 $n$ 个节点和 $m$ 条边，求将每个点分配到两个独立的互不相连的图后，两个图中边权的最大值的最小值。

若可以通过一种分配方式使得每个图（森林）中的点互不相连，输出 `0` 。

#### 题目分析

考虑种类并查集。设 `fa[i]` 表示监狱 A ，`fa[i + n]` 表示监狱 B 。

我们不妨对每条边按照边权降序排序，每次对于一条边的两个端点，尝试将其分配到不同的两个集合中。若当前边的两个端点已经在同一集合中，则代表此边为产生冲突的最大边权的最小值。

证明显然。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int n, m;
struct Relation {
    int a, b, c;

    bool operator > (const Relation x) const {
        return c > x.c;
    }
} relations[N];
int fa[2 * N];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void merge(int u, int v) {
    int fu = find(u), fv = find(v);
    if (fu != fv) {
        fa[fu] = fv;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &relations[i].a, &relations[i].b, &relations[i].c);
    }
    sort(relations + 1, relations + m + 1, greater<Relation>());
    for (int i = 1; i <= 2 * n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        if (find(relations[i].a) == find(relations[i].b) || find(relations[i].a + n) == find(relations[i].b + n)) {
            printf("%d\n", relations[i].c);
            return 0;
        }
        merge(relations[i].a, relations[i].b + n);
        merge(relations[i].a + n, relations[i].b);
    }
    printf("0\n");
    return 0;
}
```

### [P1783 海滩防御](https://www.luogu.com.cn/problem/P1783)

#### 题目大意

给定在纵方向上无限延伸的二维平面 $U$ 和平面内 $m$ 个点，其中每个点可以覆盖以 $k$ 为半径的圆形区域。二维平面的最大横坐标为 $n$ 。求一个最小的 $k$ ，使得这 $m$ 个点覆盖范围所形成的区域的横坐标可以连续覆盖 $[0, n]$ 区间。

精度 $\geq 10^{-2}$ 。

#### 题目分析

考虑二分答案。

对于 `check` 函数，我们不妨对每两个防御塔构成的点对 $(t_i, t_j)$ 按照距离进行排序预处理。对于每次 `check` 操作，假设当前答案为 $x$ ，则我们不妨先选择出所有相距距离 $\leq x$ 的防御塔点对，然后根据每个（已连接或未连接的）防御塔距离两个边界 $(0,0)$ 和 $(n, 0)$ 的大小进行判断是否符合。

我们可以使用并查集来维护该操作。首先先将所有距离 $\leq x$ 的防御塔点对都 `merge` 到相应集合中，然后对于每个需要检查距离边界距离的点对 $(i,j)$ ，若 $i$ 和 $j$ 在同一集合中且 $i$ ，$j$ 均符合距离要求，则当前答案 $x$ 满足条件，缩小右端点；反之亦然。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
constexpr double eps = 1e-4;

int n, m;

class DisjointSet {
private:
    int fa[N];

public:
    DisjointSet() {
        for (int i = 0; i < N; i++) {
            fa[i] = i;
        }
    }

    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    void merge(int u, int v) {
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            fa[fu] = fv;
        }
    }
};

struct Point {
    int x, y;

    Point() {}

    Point(int _x, int _y) {
        x = _x, y = _y;
    }

    double distanceFrom(const Point a) const {
        return sqrt(double(x - a.x) * (x - a.x) + double(y - a.y) * (y - a.y));
    }
};

struct Tower {
    int id;
    Point pos;
} a[N];

struct DiffPair {
    Tower u, v;

    bool operator< (const DiffPair a) const {
        return u.pos.distanceFrom(v.pos) < a.u.pos.distanceFrom(a.v.pos);
    }
};

vector<DiffPair> vt;

bool check(double x) {
    DisjointSet ds;
    for (auto pair : vt) {
        if (pair.u.pos.distanceFrom(pair.v.pos) > 2 * x) {
            break;
        }
        ds.merge(pair.u.id, pair.v.id);
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            Tower L = a[i], R = a[j];
            int fL = ds.find(L.id), fR = ds.find(R.id);
            if (L.pos.x <= x && R.pos.x + x >= n && fL == fR) {
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int col, row;
        scanf("%d%d", &col, &row);
        a[i].id = i, a[i].pos.x = col, a[i].pos.y = row;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            vt.push_back(DiffPair{a[i], a[j]});
        }
    }
    sort(vt.begin(), vt.end(), less<DiffPair>());
    double l = 0, r = n;
    while (r - l >= eps) {
        double mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    printf("%.2lf\n", l);
    return 0;
}
```

### [P2502 [HAOI2006] 旅行](https://www.luogu.com.cn/problem/P2502)

#### 题目大意

给定一张 $n$ 个点 $m$ 条边的带权无向图，求一条从节点 $s$ 到节点 $t$ 的路径，使得路径上最大权值与最小权值的比值最小。输出该比值。

数据保证边权均为正数。

#### 题目分析

乍一看很像 Kruskal 重构树，那不妨运用 Kruskal 的部分思路进行求解。

首先，我们可以通过一个并查集来判断 $s$ 与 $t$ 的连通性，若不连通则直接输出 `IMPOSSIBLE` 结束程序。

接下来考虑求解。我们不妨对边按照权值从小到大排序，按照边权大小枚举最小边和最大边。每次扩展最大边时，我们将该边的两端点使用并查集进行连通，若某一时刻 $s$ 与 $t$ 在当前并查集中连通，则尝试更新答案并结束枚举。

该做法正确性显然：选择了最小边、最大边后，我们无需关注中间边的连接方式和边权，因为它们对于最终答案没有贡献。

需要注意的是，存在 $s$ 与 $t$ 仅需要一条边相连的情况。为此，我们只需要将最大边枚举的左边界移动为当前最小边即可。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
const int INF = 0x3f3f3f3f;

int n, m, s, t;

class DisjointSet {
private:
    int fa[N];

public:
    DisjointSet() {
        for (int i = 0; i < N; i++) {
            fa[i] = i;
        }
    }

    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    void merge(int u, int v) {
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            fa[fu] = fv;
        }
    }
};

struct Edge {
    int u, v, w;

    bool operator <(const Edge a) const {
        return w < a.w;
    }
};
vector<Edge> edge;

DisjointSet ds;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edge.push_back(Edge{u, v, w});
        ds.merge(u, v);
    }
    scanf("%d%d", &s, &t);
    if (ds.find(s) != ds.find(t)) {
        printf("IMPOSSIBLE\n");
        return 0;
    }
    sort(edge.begin(), edge.end());
    int maxn = INF, minn = INF;
    double ans = INF;
    for (int i = 0; i < edge.size(); i++) {
        DisjointSet edgeDs;
        for (int j = i; j < edge.size(); j++) {
            Edge minEdge = edge[i], currEdge = edge[j];
            edgeDs.merge(currEdge.u, currEdge.v);
            if (edgeDs.find(s) == edgeDs.find(t)) {
                double curr = (double)currEdge.w / (double)minEdge.w;
                if (curr < ans) {
                    ans = curr;
                    maxn = currEdge.w, minn = minEdge.w;
                }
                break;
            }
        }
    }
    if (maxn % minn == 0) {
        printf("%d\n", maxn / minn);
    } else {
        printf("%d/%d\n", maxn / __gcd(maxn, minn), minn / __gcd(maxn, minn));
    }
    return 0;
}
```

### [P2391 白雪皑皑](https://www.luogu.com.cn/problem/P2391)

#### 题目大意

对一个长度为 $n$ 的序列进行 $m$ 次染色操作，第 $i$ 次染色操作将第 $[(i \times p + q) \bmod n] + 1$ 至第 $[(i \times q + p) \bmod n] + 1$ 个数染色为 $i$ （包括端点）。求 $m$ 次操作之后的染色序列。

初始时染色序列均为 $0$ 。

#### 题目分析

一道使用并查集维护**序列信息**的题目。

我们容易发现一个性质：若从第 $m$ 次操作开始倒序枚举，则每个数仅会被染色一次。我们不妨利用这个性质，记录对于每个节点 $i$ ，其需要被染色的下一个节点 $\text{fa}_i$ 。

考虑使用并查集实现。直接暴力枚举 $m$ 次操作，对于每次操作暴力枚举区间 $[l, r]$ 。设当前数为 $i$ ，则我们从并查集中找到其对应的下一个需要染色的点 $\text{nxt}_i$ 进行跳转。若 $i = \text{nxt}_i$ ，则说明当前节点尚未被染色，我们将其染色后将 $\text{fa}_i$ 与 $\text{fa}_{i + 1}$ 进行合并，代表其下一个需要染色的节点为 $\text{fa}_{i+1}$ 所对应的节点。

由于并查集优秀的传递性，我们可以高效的进行暴力枚举。若并查集实现为渐进 $O(1)$ ，则此实现方法时间复杂度约为 $O(m)$ ，接近线性。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

int n, m, p, q;

int color[N];

class DisjointSet {
private:
    int fa[N];

public:
    DisjointSet() {
        for (int i = 0; i < N; i++) {
            fa[i] = i;
        }
    }

    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    void merge(int u, int v) {
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            fa[fu] = fv;
        }
    }
} ds;

int main() {
    scanf("%d%d%d%d", &n, &m, &p, &q);
    for (int i = m; i >= 1; i--) {
        int l = (i * p + q) % n + 1,
        r = (i * q + p) % n + 1;
        if (l > r) swap(l, r);
        for (int j = l; j <= r;) {
            int nxt = ds.find(j);
            if (nxt == j) {
                color[j] = i;
                ds.merge(j, j + 1);
            }
            j = nxt;
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%d\n", color[i]);
    }
    return 0;
}
```



浅谈并查集


## 差分约束

差分约束系统是一种特殊的 $n$ 元一次不等式组，形如：
$$
\left\{
\begin{aligned}
&x_i \leq x_j + c_k,\\
&x_{i'} \leq x_{j'} + c_{k'},\\
&\cdots
\end{aligned}
\right.
$$
注意到这与最短路算法中 $\text{dis}_{v} \leq \text{dis}_{u} + w$ 类似。所以我们考虑构造一种特殊的图，使得这个图能够通过某种途径判断它所代表的差分约束系统是否有解。

> 注：若一个差分约束系统有解，则它必有无数个解。
>
> **证明：**若 ${a_1, a_2, \cdots, a_n}$ 为差分约束系统 $U$ 的一组解，则其必有另一组解 ${a_1 + d, a_2 + d, \cdots, a_n + d}$ ，其中 $d \in \R$ 。故得证。

考虑如何求解。我们显然可以通过新建一条边权为 $c_k$ 的边 $E_{j,i}: j \rarr i$ 来表示不等式 $x_i \leq x_j + c_k$ ，以此类推，将每个变量 $x_u$ 看作图中的一个节点，将每个不等式看作图中的一条带权有向边。

由于通过上述方法构造的图无法保证连通，我们不妨设超级源点 $U = x_0$ ，然后从 $U$ 出发向每个节点 $x_i$ （$x_i > 0$） 连接一条边权为 $0$ 的有向边 $E_{0,i}: 0 \rarr i$ 来保证连通性。之后，我们通过从节点 $U$ 开始求单源最短路并检查负环是否存在。若负环存在，则给定的差分约束系统无解；否则 $x_i = \text{dis}_i$ 即为该差分约束系统的一组可能解。

在实现上我们一般采用 SPFA（队列优化的 Bellman-Ford ）作为最短路算法。注意判断负环时因超级源点的存在而导致节点数相应增加。

## 例题

### [P1993 小 K 的农场](https://www.luogu.com.cn/problem/P1993)

#### 题目大意

给定 $n$ 个约束条件，其中分为三类：

- $x_a - x_b \geq c$
- $x_a - x_b \leq c$
- $x_a = x_b$

给定序列 $x_i$ 和 $n$ 个约束条件，求该差分约束系统是否有解。

#### 题目分析

模板题。考虑对于每个操作进行转化，使其成为形如 $x_i \leq x_j + c_k$ 的形式：

- $x_a - x_b \geq c \Rarr x_b \leq x_a - c$
- $x_a - x_b \leq c \Rarr x_a \leq x_b + c$
- $x_a = x_b \Rarr x_a \leq x_b\ ,\ x_b \leq x_a$

最后建边并连接超级源点、检测负环即可。

#### 代码

```cpp
// Problem: P1993 小 K 的农场
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1993
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 5 * 1e5 + 10;

int n, m;
int h[2 * N], vtx[2 * N], nxt[2 * N], w[2 * N], idx, vis[2 * N], dis[2 * N];
int cnt[2 * N], op, a, b, c;
queue<int> q;

void addEdge(int a, int b, int c) {
    vtx[idx] = b, nxt[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool spfa(int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.push(s);
    vis[s] = 1;
    while (!q.empty()) {
        int tmp = q.front();
        vis[tmp] = 0;
        int p = h[tmp];
        while (p != -1) {
            int v = vtx[p];
            // 此处不能取等，否则会把 0 环判定为负环
            if (dis[tmp] + w[p] < dis[v]) {
                dis[v] = dis[tmp] + w[p];
                cnt[v]++;
                if (cnt[v] > n) return 0;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
            p = nxt[p];
        }
        q.pop();
    }
    return 1;
}

int main() {
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> op;
        if (op == 1) {
            cin >> a >> b >> c;
            addEdge(a, b, -c);
        } else if (op == 2) {
            cin >> a >> b >> c;
            addEdge(b, a, c);
        } else {
            cin >> a >> b;
            addEdge(b, a, 0);
            addEdge(a, b, 0);
        }
    }
    for (int i = 1; i <= n; i++) {
        addEdge(n + 1, i, 0);
    }
    if (spfa(n + 1)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}
```

### [P2294 [HNOI2005] 狡猾的商人](https://www.luogu.com.cn/problem/P2294)

#### 题目大意

给定 $m$ 条关于前缀和数组 $c_i$ 的信息，每条信息形如 $c_t - c_{s - 1} = v_k$ ，求该差分约束系统是否有解。

#### 题目分析

根据题目抽象出题目大意后问题就再次转化为裸的差分约束问题，对每条信息可转化为：

- $c_t \leq c_{s - 1} + v_k$
- $c_{s - 1} \leq c_t - v_k$

建边跑最短路即可。注意超级源点。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

struct Edge {
    int v, w;
};

vector<Edge> G[N];
int cnt[N], dis[N], vis[N];
int n, m, T;

void addEdge(int u, int v, int w) {
    G[u].push_back(Edge{v, w});
}

bool spfa(int u) {
    queue<int> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(cnt, 0, sizeof(cnt));
    memset(vis, 0, sizeof(vis));
    dis[u] = 0, vis[u] = 1;
    q.push(u);
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        vis[t] = 0;
        for (auto edge : G[t]) {
            int v = edge.v, w = edge.w;
            if (dis[v] > dis[t] + w) {
                dis[v] = dis[t] + w;
                cnt[v] = cnt[t] + 1;
                if (cnt[v] >= n + 2) {
                    return 1;
                }
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    return 0;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        for (int i = 0; i < N; i++) {
            G[i].clear();
        }
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++) {
            int s, t, v;
            scanf("%d%d%d", &s, &t, &v);
            // sum[t] - sum[s - 1] = v
            // sum[t] - sum[s - 1] >= v
            // sum[t] - sum[s - 1] <= v
            // sum[s - 1] + v <= sum[t]
            // sum[t] - v <= sum[s - 1]
            addEdge(s - 1, t, v);
            addEdge(t, s - 1, -v);
        }
        for (int i = 0; i <= n; i++) {
            addEdge(n + 1, i, 0);
        }
        bool flag = spfa(n + 1);
        if (flag) {
            printf("false\n");
        } else {
            printf("true\n");
        }
    }
    return 0;
}
```

### [P4878 [USACO05DEC] Layout G](https://www.luogu.com.cn/problem/P4878)

#### 题目大意

给定一个长度为 $n$ 的数列 $a_i$ 和 $m$ 条信息，对于每条信息，有两种可能：

1. $d_a - d_b \leq c_k$
2. $d_a - d_b \geq c_k$

其中 $d_i$ 表示第 $i$ 个数所在的位置。保证数据有序给出。

求 $(d_n - d_1)_{\text{max}}$ 。

#### 题目分析

一个有点意思的题目。

对于判断是否有解的方法显然，套用差分约束模板即可。在此主要探讨关于求解 $(d_n - d_1)_{\text{max}}$ 。

显然我们无法直接使用由超级源点 $U$ 出发的最短路数组（正权均被设为 $0$ ），不妨在有解的情况下从结点 $1$ 开始跑第二次最短路，此时的 $\text{dis}$ 数组即为 $1$ 出发可到达的节点的最短路，即为差分约束系统的部分可能解。若 $\text{dis}_n = +\infin$ ，则代表从 $1$ 没有相应的条件指向 $n$ ，此时两者可以相距正无穷远（即为输出 `-2` 时的情况）。

这道题还有一个细节需要注意。题目明确，可以有多个奶牛在同一位置上，即两个相邻奶牛最小距离 $\geq 0$ 。即 $d_i - d_{i - 1} \geq 0$ 也需要作为差分约束系统的条件之一参与决策。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;

int n, ml, md;

struct Edge {
    int v, w;
};
vector<Edge> G[N];

int cnt[N], dis[N], vis[N];

void addEdge(int u, int v, int w) {
    G[u].push_back(Edge{v, w});
}

bool spfa(int s) {
    queue<int> q;
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (auto [v, w] : G[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n + 1) {
                    return 0;
                }
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return 1;
}

int main() {
    scanf("%d%d%d", &n, &ml, &md);
    for (int i = 1; i <= ml; i++) {
        int a, b, d;
        scanf("%d%d%d", &a, &b, &d);
        // s_b - s_a <= d
        // s_b <= s_a + d
        addEdge(a, b, d);
    }
    for (int i = 1; i <= md; i++) {
        int a, b, d;
        scanf("%d%d%d", &a, &b, &d);
        // s_b - s_a >= d
        // s_a <= s_b - d
        addEdge(b, a, -d);
    }
    for (int i = 2; i <= n; i++) {
        // s_i - s_i-1 >= 0
        // s_i-1 <= s_i - 0
        addEdge(i, i - 1, 0);
    }
    for (int i = 1; i <= n; i++) {
        addEdge(0, i, 0);
    }
    bool flag = spfa(0);
    if (flag) {
        spfa(1);
        if (dis[n] == INF) {
            printf("-2\n");
        } else {
            printf("%d\n", dis[n]);
        }
    } else {
        printf("-1\n");
    }
    return 0;
}
```



浅谈差分约束


乘法逆元在 OI 中有非常重要的用途，通常用来快速求解模意义下大数除法问题。本文将简单讨论有关乘法逆元的求解方法和题目。

## 线性同余方程

在了解乘法逆元概念之前，我们需要先了解一个前置概念：线性同余方程。

形如 $ax \equiv b \pmod n$ 的方程称为**线性同余方程**。其中 $a,b,n$ 为给定整数，$x$ 为未知数。

### 同余

所谓同余，即两个数对同一个数取模有相同的余数。例如 $a \equiv b \pmod p$ 就意味着 $a$ 、$b$ 除以 $p$ 的余数相同。形式化地， $a - b = km$ 为 $a \equiv b \pmod m$ 的充要条件，其中 $k \in \Z$ 。

具象化地，若 $a \equiv b \pmod m$ ，则 $a$ 、$b$ 在$\bmod m$ 意义下是等价的。

同余有如下性质：

- 自反性：$a \equiv a \pmod m$ ；
- 对称性：$a \equiv b \pmod m \Leftrightarrow b \equiv a \pmod m$ ；
- 传递性：$a \equiv b \pmod m ,\ b \equiv c \pmod m \Rightarrow a \equiv c \pmod m$ ；
- 相加：$a \equiv b \pmod m, \ c \equiv d \pmod m \Rightarrow a \pm c \equiv b \pm d \pmod m$ ；
- 相乘：$a \equiv b \pmod m, \ c \equiv d \pmod m \Rightarrow ac \equiv bd \pmod m$ ；
- 幂运算：$a \equiv b \pmod m \Rightarrow a^n \equiv b^n \pmod m$ ；
- ……

我们考虑求解上述线性同余方程。我们可以发现，上述同余方程等价于如下线性不定方程：
$$
ax + nk = b
$$
其中 $x$ 、$k$ 为未知数，当且仅当 $\gcd(a,n) \mid b$ 时上述方程有整数解。

### 扩展欧几里得算法

我们知道，在基本欧几里得算法中，我们通过辗转相除法来求解 $\gcd(a,n)$ 。具体地，基本欧几里得算法有递归式 $\gcd(a,n) = \gcd(n, a \bmod n)$ ，直到 $a \bmod n = 0$ 。

扩展欧几里得算法的扩展在于，它可以在计算 $\gcd(a,n)$ 的基础上求得一组对于方程 $ax + nk = \gcd(a,n)$ 的整数特解。我们称上述方程 $ax + nk = \gcd(a,n)$ 为**贝祖等式**。

扩展欧几里得算法使用了递归的思想求解。我们不妨设已知等式：
$$
nx_1 + (a \bmod n)k_1 = \gcd(n, a \bmod n)
$$
容易发现，$a \bmod n = a - \lfloor\frac{a}{n} \rfloor \times n$ 。则上述等式化为：
$$
nx_1 + (a - \lfloor \frac{a}{n} \rfloor \times n)k_1 = \gcd(n, a\bmod n)
$$
整理得：
$$
ak_1 + n(x_1 - \lfloor \frac{a}{n} \rfloor \times k_1) = \gcd(a,n)
$$
则我们可以求得新的解 $x = k_1$ ，$y = x_1 - \lfloor \frac{a}{b} \rfloor \times k_1$ 。

#### 具体过程

设要计算 $\gcd(a,n)$ 和贝祖等式 $ax + nk = \gcd(a,n)$ 的特解 $x_0$ ，$k_0$ 。

首先，若 $n = 0$ ，则按照基本欧几里得算法，有 $\gcd(a,n) = a$ ，且 $x_0 = 1$ ，$k_0 = 0$ 。递归终止。

我们考虑计算。按照上述推导，我们可以发现 $\gcd(n, a \bmod n) = nx_1 + (a \bmod n)k_1$ ，且当前 $x_0 = y_1$ ，$k_0 = x_1 - \lfloor \frac{a}{n} \rfloor \times k_1$ 。

#### 代码实现

```cpp
int ex_gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
      x = 1;
      y = 0;
      return a;
    }
    int d = ex_gcd(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp - a / b * y;
    return d;
}
```

### 扩展欧几里得算法求解线性同余方程

我们继续考虑求解线性同余方程 $ax \equiv b \pmod n$ 的转化形式：
$$
ax + nk = b \tag{1-1}
$$

我们已知可以求解出方程
$$
ax_0 + nk_0 = \gcd(a,n) \tag{1-2}
$$
的一组特解。考虑对 $\text{(1-2)}$ 式进行转化。等式两边同时乘以 $\frac{b}{\gcd(a,n)}$ ，得：
$$
a\frac{b}{\gcd(a,n)}x_0 + n\frac{b}{\gcd(a,n)}k_0 = b
$$
则原方程有特解 $x = \frac{b}{\gcd(a,n)}x_0$ ，$k = \frac{b}{\gcd(a,n)}k_0$ 。

考虑求得通解。显然，若 $\gcd(a,n) = 1$ ，且方程 $ax + nk = b$ 有特解 $X_0$ ，$K_0$ ，则我们可以求出该方程的任意解：
$$
\left\{
\begin{aligned}
&x = X_0 + nt,\\
&k = K_0 - at
\end{aligned}
\right.
$$
其中 $t \in \Z$ 。如果要求最小正整数解，则 $x = X_0 \bmod t$ ，其中 $t = \frac{n}{\gcd(a,n)}$ 。若 $n$ 为质数，则 $x = X_0 \bmod n$ 。

#### 代码实现

```cpp
int ex_gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
      x = 1;
      y = 0;
      return a;
    }
    int d = ex_gcd(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp - a / b * y;
    return d;
}

bool liEu(int a, int b, int c, int& x, int& y) {
    int d = ex_gcd(a, b, x, y);
    if (c % d != 0) return 0;
    int k = c / d;
    x *= k;
    y *= k;
    return 1;
}
```

## 乘法逆元

指模意义下的乘法逆元。

### 定义

如果有 $x$ 满足线性同余方程 $ax \equiv 1 \pmod b$ ，则 $x$ 被称为 $a \bmod b$ 的逆元，记作 $x = a^{-1}$ 。

在实数意义下，$a$ 的逆元即为 $a$ 的倒数 $\frac{1}{a}$ 。在模意义下，$x$ 的逆元 $x^{-1}$ 在模意义下的运算类似于 $\frac{1}{x}$ 。

### 求解

#### 扩展欧几里得求逆元

显然我们可以选择求解上述线性同余方程。直接套用扩展欧几里得算法即可。

```cpp
void exgcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}
```

#### 线性求连续序列的逆元

如果要选择求解 $1,2,\dots,n$ 中每个数关于某个模数的逆元，扩展欧几里得算法就会出现很多冗杂的计算，导致时间复杂度偏高。

考虑线性递推求解。我们显然可以注意到一个重要前提：
$$
1^{-1} \equiv 1 \pmod p
$$
证明显然：$1 \times 1 \equiv 1 \pmod p$ 对于任意 $p \in \Z$ 恒成立，$1$ 在$\bmod p$ 意义下的逆元恒为 $1$ 。

假设我们现在要计算 $i$ 的逆元 $i^{-1}$ ，即求出 $i^{-1} \times i \equiv 1 \pmod p$ 的解 $i^{-1}$ 。

令 $k = \lfloor\frac{p}{i} \rfloor$ ，$j = p \bmod i$ 。则 $p = ki + j$ 。即 $ki + j \equiv 0 \pmod p$ 。

两边同时乘以 $i^{-1} \times j^{-1}$ ，有：
$$
kj^{-1} + i^{-1} \equiv 0 \pmod p
$$
移项，有
$$
i^{-1} \equiv -kj^{-1} \pmod p
$$
代入 $k = \lfloor\frac{p}{i}\rfloor$ ， $j = p \bmod i$ ，有
$$
i^{-1} \equiv -\lfloor\frac{p}{i}\rfloor \times (p \bmod i)^{-1} \pmod p
$$
不难发现 $p \bmod i < i$ ，即计算 $i^{-1}$ 时已经算出 $(p \bmod i)^{-1}$ ，可以递推求解。

形式化地，我们有：
$$
i^{-1} = \left \{
\begin{aligned}
&1,&& \text{if}\quad i = 1,\\
&-\lfloor\frac{p}{i}\rfloor \times (p \bmod i)^{-1}, &&\text{otherwise.}\\
\end{aligned}
\right. \pmod p
$$
具体实现如下：

```cpp
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
    inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}
```

注意我们使用 $p - \lfloor\frac{p}{i}\rfloor$ 来防止出现负数。

#### 线性求任意 $n$ 个数的逆元

考虑前缀积。我们计算出 $n$ 个数 $a_1,a_2,\dots,a_n$ 的前缀积 $s_i$ ，然后使用扩展欧几里得算法计算 $s_n$ 的逆元 $s_n^{-1}$ 。

我们不妨抽象理解为实数意义下的逆元，即 $s_n^{-1} = \frac{1}{s_n} \pmod p$ 。

又 $s_n = s_1 \times s_2 \times \dots \times s_n$ ，则 $s_n^{-1} = \frac{1}{s_1 \times s_2 \times \dots \times s_n} \pmod p$ 。将 $s_n^{-1}$ 乘上 $s_n$ ，我们即可得到 $s_{n - 1}^{-1}$ 。如此递推可求得所有 $s_i^{-1}$ 。

对于 $a_i^{-1}$ ，我们显然有：
$$
a_i^{-1} \equiv s_{i - 1} \times s_{i}^{-1} \pmod p
$$

```cpp
s[0] = 1;
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p;
sv[n] = exgcd(s[n], p);
// sv_i 即为 s_i 的逆元
for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;
```

总时间复杂度为 $O(n + \log p)$ 。

## 题目

### [P1082 [NOIP2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082)

模板题，套用扩展欧几里得算法即可。

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

int a, n;

int exgcd(int a, int n, int& x, int& k) {
    if (n == 0) {
        x = 1, k = 0;
        return a;
    }
    int t = exgcd(n, a % n, x, k);
    int xx = x;
    x = k, k = xx - a / n * k;
    return t;
}

int main() {
    scanf("%d%d", &a, &n);
    int x, k;
    int t = exgcd(a, n, x, k);
    t = n / t;
    printf("%d\n", (x % t + t) % t);
    return 0;
}
```

### [P5431 【模板】模意义下的乘法逆元 2](https://www.luogu.com.cn/problem/P5431)

模板题，使用线性乘法逆元模板带入求解即可。注意快速输入输出和 `long long` 。

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10;

long long n, p, K;
long long a[N], s[N], sv[N];

long long read() {
	long long x=0,flag=1;char c;
	while ((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
	while (c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*flag;
}

int exgcd(int a, int n, int& x, int& k) {
    if (n == 0) {
        x = 1, k = 0;
        return a;
    }
    int t = exgcd(n, a % n, x, k);
    int xx = x;
    x = k, k = xx - a / n * k;
    return t;
}

int main() {
    s[0] = 1;
    n = read(); p = read(); K = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        s[i] = s[i - 1] * (a[i] % p) % p;
    }
    int x, k;
    int b = exgcd(s[n], p, x, k);
    b = p / b;
    sv[n] = (x % b + b) % b;
    for (int i = n; i >= 1; i--) {
        sv[i - 1] = sv[i] * a[i] % p;
    }
    long long ans = 0, t = 1, inv;
    for (int i = 1; i <= n; i++) {
        t = t * K % p;
        inv = sv[i] * s[i - 1] % p;
        ans = (ans + inv * t % p) % p;
    }
    printf("%lld\n", ans);
    return 0;
}
```

### [P2054 [AHOI2005] 洗牌](https://www.luogu.com.cn/problem/P2054)

#### 题目大意

给定一个序列 $a_i$ ，其中 $1 \leq i \leq n$ 且 $n$ 为偶数。对于每次操作，将序列分为 $a_1 \sim a_{\frac{n}{2}}$ 和 $a_{\frac{n}{2} + 1} \sim a_n$ 两部分。对于前半部分的元素 $a_i$ ，其在新序列中的位置为 $2i$ ；对于后半部分的元素 $a_j$ ，其在新序列中的位置为 $2j - (n + 1)$ 。

现在给定 $n$ 和操作次数 $m$ ，求经过 $m$ 次操作后位于第 $L$ 个位置上的元素在初始序列中的位置 $x$ 。

其中 $1 \leq n \leq 10^{10}$ ，$0 \leq m \leq 10^{10}$ 且 $n$ 为偶数。

#### 分析

对于序列中任意元素 $a_i$ ，考虑其在新序列中的位置。显然其在新序列中的位置为 $2i \bmod (n + 1)$ 。

我们容易发现，经过 $m$ 次变换后，其最终位置为 $i \cdot 2^m \bmod (n + 1)$ 。则易得如下同余方程：
$$
x \cdot 2^m \equiv L \pmod{n + 1}
$$
则有
$$
x \equiv \frac{L}{2^m} \pmod{n + 1}
$$
考虑乘法逆元。设 $2$ 在$\bmod{n + 1}$ 意义下的乘法逆元为 $k$ ，则有
$$
x \equiv k^m \cdot L \pmod{n + 1}
$$
得解。

对于 $2$ 在模意义下的乘法逆元 $k$ ，我们显然可以通过扩展欧几里得算法在 $O(\log n)$ 时间内求解。

注意到 $n \leq 10^{10}$ ，需要使用快速幂求解 $k^m$ 。这里介绍一下快速乘：一个对于模意义下大数乘法的快速计算方法，原理类似快速幂。具体操作是维护一个被乘数 $a$ ，将其按二进制位依次乘到乘数 $b$ 中，计算时逐步取模。

详细参见 <https://leungll.site/2021/05/24/ksm-permalink/> 和 [https://oi-wiki.org/math/binary-exponentiation](https://oi-wiki.org/math/binary-exponentiation/#%E6%A8%A1%E6%84%8F%E4%B9%89%E4%B8%8B%E5%A4%A7%E6%95%B4%E6%95%B0%E4%B9%98%E6%B3%95) ，存在在 `long long` 范围内的 $O(1)$ 快速解法。下面的程序使用朴素的 $O(\log_2 m)$ 的普通快速乘。

#### 代码

注意 `long long` 和取模。数据范围较大，也需要注意常数优化。

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

long long n, m, L;

long long exgcd(long long a, long long n, long long& x, long long& k) {
    if (n == 0) {
        x = 1, k = 0;
        return a;
    }
    long long t = exgcd(n, a % n, x, k);
    long long xx = x;
    x = k, k = xx - a / n * k;
    return t;
}

long long qmul(long long a, long long b, long long mod) {
    long long ans = 0;
    while (b) {
        if (b & 1) {
            ans = (ans + a) % mod;
        }
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans;
}

long long qpow(long long a, long long b, long long mod) {
    long long ans = 1, base = a;
    while (b) {
        if (b & 1) {
            ans = qmul(ans, base, mod);
        }
        base = qmul(base, base, mod);
        b >>= 1;
    }
    return ans;
}

int main() {
    scanf("%lld%lld%lld", &n, &m, &L);
    long long x, k;
    long long t = exgcd(2, n + 1, x, k);
    t = (n + 1) / t;
    long long inv2 = (x % t + t) % t;
    printf("%lld\n", qmul(L, qpow(inv2, m, n + 1), n + 1));
    return 0;
}
```



浅谈乘法逆元


## 基础概念

- 样本点：随机试验中可能发生的结果
- 样本空间：所有样本点的集合，记作 $\Omega$
- 概率：记作 $P(A)$ ，即事件 $A$ 发生的概率，满足 $P(A) \in \R 且 0\leq P(A) \leq 1$

## 概率模型

### 古典模型

即各个事件出现的概率相等。此时 $P(A) = \frac{A 包含的基本事件总数}{基本事件总数}$ 。典型的例子包括抛硬币、掷骰子等。

**例：一年有 365 天，每个人出生日期都是随机的。班里有 30 名同学，则存在两位同学生日相同的概率是多少？**

**解：** 每个人的生日有 365 种可能性，基本事件总数即为 $365^{30}$ 。等概率随机即满足古典概型。显然直接计算概率需要考虑只有两个同学生日相同、只有三个同学生日相同等情况，计算复杂。考虑转化。

我们不妨计算上述命题的逆命题，即不存在两位同学生日相同的概率有多少。此时每位同学的生日都互不相同，所有可能的情况即为 $A^{30}_{365}$ 种。则该逆命题的概率为 $P(不存在两位同学生日相同) = \frac{A^{30}_{365}}{365^{30}}$ 。

则原问题的答案为 $P(存在两位同学生日相同) = 1 - \frac{A^{30}_{365}}{365^{30}}$ 。

### 几何概型

如果每个事件发生的概率只与构成该事件区域的长度（面积或体积或度数）成比例，则称这样的概率模型为几何概率模型，简称为几何概型。[^1]

简单来说，在几何概型下，随机试验的所有可能结果（即基本事件总数）为 $\infty$ 且每个事件发生的概率均等。典型的例子包括在一个几何区域内随机取一点进行实验、一个人到单位的时间（在 8:00 ~ 9:00 之间的任意时刻）等。

**例：0 时刻时甲乙两人开始等车，甲的车在前 60 min 内随机时刻会到，乙的车在前 120 min 内随机时刻会到。求甲比乙早上车的概率。**

**解：** 设甲的车在 $X$ 时刻会到，乙的车在 $Y$ 时刻会到。则满足 $0 \leq X \leq 60$ ，$0 \leq Y \leq 120$ 。

显然我们要计算的是 $X < Y$ 的概率。不妨用坐标系来表示 $X,Y$ ：

![geometric-probability](https://blog.samzhangjy.com/assets/posts/probability-theory/geometric-probability.png)

那么，我们要求的 $X < Y$ 可以分为两部分： $0 \leq Y \leq 60$ 时和 $60 < Y \leq 120$ 时。显然第二个区间永远满足 $X < Y$ 。

对于 $0 \leq Y \leq 60$ 时，显然我们可以将图像化为两个三角形。对于上半部分的三角形，永远满足 $X < Y$ 。

综上， $X < Y$ 在坐标轴图像上表现为图中的阴影区域。让我们来计算一下其发生的概率：
$$
P(甲比乙早上车) = P(X < Y) = \frac{60 \times 60 + \frac{1}{2} \times 60 \times 60}{60 \times 120} = \frac{3}{4} = 75\%
$$
即有 75% 的概率甲比乙早上车。

### 条件概率

即事件 $A$ 在事件 $B$ 发生的条件下发生的概率，记作 $P(A|B)$ 。要计算条件概率，我们需要引入两个概念：

- **联合概率** 表示两个事件共同发生的概率，记作 $P(A \cap B)$ 或 $P(A,B)$ 或 $P(AB)$ ；
- **边缘概率** 表示某个事件发生的概率，记作 $P(A)$ 。

条件概率 $P(A|B) = \frac{P(A \cap B)}{P(B)}$ 。特别地，若 $A$ 、$B$ 为两个独立事件，则 $P(A \cap B) = P(A) \times P(B)$ ，则 $P(A | B) = P(A)$ ， $P(B|A) = P(B)$ 。

**例 1 ：一对夫妻生了两个孩子，第一个孩子是女孩，求第二个孩子是女孩的概率。**

**解 1 ：** 显然这两个事件是独立事件，故 $P(第二个孩子是女孩)= \frac{1}{2}$ 。

**例 2 ：一对夫妻生了两个孩子，其中一个孩子是女孩，求另一个孩子也是女孩的概率。**

**解 2 ：** 存在四个基本事件：（男，男）、（男，女）、（女，男）、（女，女）。

则 $P(一个孩子是女孩|另一个孩子也是女孩) = \frac{P(一个孩子是女孩 \cap 另一个孩子也是女孩)}{P(另一个孩子是女孩)} = \frac{\frac{1}{4}}{\frac{3}{4}} = \frac{1}{3}$ 。

#### 贝叶斯公式

$$
P(A|B) = \frac{P(A \cap B)}{P(B)} = \frac{P(B | A) \times P(A)}{P(B)}
$$

推导证明显然。

**例：某种疾病发病率为 $0.01\%$ ，通过某种检测方式可以检测该疾病。若某人患病，则检测结果为阳性的概率为 $99\%$ ；若没有患病，则检测出阳性的概率是 $1\%$ 。求某人检测结果为阳性时患病的概率。**

**解：** 根据题意，易得
$$
P(患病|检测阳性) = \frac{P(患病 \cap 检测阳性)}{P(检测阳性)}
$$
即
$$
P(患病|检测阳性) = \frac{P(检测阳性|患病) \times P(患病)}{P(检测阳性)} = \frac{0.99 \times 0.0001}{0.99 \times 0.0001 + 0.9999 \times 0.01} \approx 0.98\%
$$

### 应用

#### 看电影

在一个电影院举办针对儿童的六一儿童节免费观影活动，有两个影院放映不同的电影，观影儿童通过投掷硬币决定进入哪一个电影院，投到正面的进入 A 影院，反面的进入 B 影院。 两个影院都能容纳 $n$（$0 \leq n \leq 1000$）个人,预计有 $2n$ 个儿童观影。如果一个影院人满了，则接下来的儿童直接进入另一个影院无需投掷硬币。

求排在队尾的两个儿童同时进入同一个影院的概率。

##### 解法一

考虑通过组合数学求解。

显然直接计算进入同一个影院的概率较为复杂，不妨转化为求解进入不同影院的概率。则一个影院内儿童的所有可能情况有 $C^{n - 1}_{2n - 2}$ 种可能，另一个影院的儿童也随之确定。又因为总事件数为 $2^{2n - 2}$ ，故概率为

$$
P(在队尾的两个儿童进入不同影院) = \frac{C^{n - 1}_{2n - 2}}{2^{2n - 2}}
$$

则所求概率为

$$
P(在队尾的两个儿童进入相同影院) = 1 - \frac{C^{n - 1}_{2n - 2}}{2^{2n - 2}}
$$

又
$$
\begin{align}
\frac{C^{n - 1}_{2n - 2}}{2^{2n - 2}} &= \frac{(2n - 2)!}{(n - 1)! \times (n - 1)!} ÷ 4^{n - 1}\\
&=\frac{(2n - 2)!}{(n - 1)! \times (n - 1)!} \times \frac{1}{4^{n - 1}}\\
&=\frac{2n - 2}{4(n - 1)} \times \frac{2n - 3}{4(n - 2)} \times \cdots \times \frac{n}{4 \times 1}
\end{align}
$$
故程序如下：

```cpp
int main() {
    int n;
    cin >> n;
    n >>= 1;  // 输入为2n
    double ans = 1.0;
    for(int i = 1; i < n; i++)
        ans = ans * (i + n - 1) / (i << 2);  // 时间复杂度O(n)
    printf("%.4lf", 1 - ans);
    return 0;
}
```

##### 解法二

考虑使用动态规划。

定义 $f_{n,m}$ 表示影院 A 剩下 $n$ 个位置，影院 B 剩下 $m$ 个位置时最后两个儿童进入同一个影院的概率。

考虑状态转移。显然 $f_{n,m}$ 由 $f_{n - 1,m}$ 或 $f_{n, m - 1}$ 转移而来，则 $f_{n,m} = \frac{1}{2} \times f_{n -  1, m} + \frac{1}{2} \times f_{n, m - 1}$ 。即当前状态为先前两个状态随机 50% 决定。

显然，对于 $0 < n \leq 1$ 或 $0 < m \leq 1$ ，$f_{n,m} = 0$ 。即当剩余座位 $\leq 1$ 时两个人不能同时进入一个影院。

同理，当 $n = 0$ 或 $m = 0$ 时，两人必须进入同一个影院，即 $f_{n,m} = 1$ 。

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;

int n;
double f[N][N];

int main() {
    scanf("%d", &n);
    n /= 2;
    for (int i = 2; i <= n; i++) {
        f[i][0] = f[0][i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = 0.5 * (f[i - 1][j] + f[i][j - 1]);
        }
    }
    printf("%.4lf", f[n][n]);
    return 0;
}
```

#### [Sushi](https://www.luogu.com.cn/problem/AT_dp_j)

现有$N(1 ≤ N ≤ 300)$个盘子，编号为$1,2,3,…,N$。第$i$个盘子中放有$a_i(1≤a_i ≤3)$个寿司。

接下来每次执行以下操作，直至吃完所有的寿司。从第$1,2,3,…,N$个盘子中任选一个盘子，吃掉其中的一个寿司。若没有寿司则不吃。

若将所有寿司吃完，请问此时操作次数的数学期望是多少？

考虑概率 DP 。我们设状态 $f_{i,j,k,l}$ 代表剩余 1、2、3、0 个寿司的盘子的数量为 $i,j,k,l$ 时期望的操作数。

注意到 $l = n - i - j -k$ ，故优化为 $f_{i,j,k}$ 。时间复杂度 $O(300^3) = 2.7 \times 10^7 < 10^8$ ，能过。

考虑状态转移。容易发现对于每一个状态都是由上一个状态吃掉某盘中的一个寿司得来的。故易得
$$
f_{i,j,k} = f_{i,j,k} \times \frac{n - i - j -k}{n} + f_{i - 1,j,k} \times \frac{i}{n} + f_{i + 1,j - 1,k} \times \frac{j}{n} + f_{i,j - 1,k+1} \times \frac{k}{n} + 1
$$
移项通分，得
$$
f_{i,j,k} = f_{i-1,j,k} \times \frac{i}{i + j +k} + f_{i + 1,j - 1,k} \times \frac{j}{i + j + k} + f_{i,j + 1,k - 1} \times \frac{k}{i + j + k} + \frac{n}{i + j + k}
$$
考虑初始状态。显然当所有盘子的寿司都为空时期望操作数为 $0$ ，即 $f_{0,0,0} = 0$ 。

考虑答案。显然答案为 $f_{b_1,b_2,b_3}$ ，其中 $b_i$ 代表初始状态时有 $i$ 个寿司的盘子数量。

需要注意的是，本题为了满足无后效性需要从 $k$ 到 $i$ 倒序枚举。

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 310;

double f[N][N][N];
double n, a[N];
int b[10];

int main() {
    scanf("%lf", &n);
	for (int i = 1; i <= n; i++) {
        scanf("%lf", &a[i]);
		b[(int)a[i]]++;
	}
    f[0][0][0] = 0;
    for (int k = 0; k <= n; k++) {
        for (int j = 0; j <= n; j++) {
            for (int i = 0; i <= n; i++) {
                if (!(i || j || k)) continue;
                if (i >= 1) f[i][j][k] += f[i - 1][j][k] * (double)i / (double)(i + j + k);
                if (j >= 1) f[i][j][k] += f[i + 1][j - 1][k] * (double)j / (double)(i + j + k);
                if (k >= 1) f[i][j][k] += f[i][j + 1][k - 1] * (double)k / (double)(i + j + k);
                f[i][j][k] += (double)n / (double)(i + j + k);
            }
        }
    }
    printf("%.15lf\n", f[b[1]][b[2]][b[3]]);
	return 0;
}
```



[^1]: https://baike.baidu.com/item/%E5%87%A0%E4%BD%95%E6%A6%82%E5%9E%8B/4035773

浅谈概率


## 什么是分层图？

所谓分层图，即通过构建一张新图使得一张图有多个维度。一个典型的例子是使一张图复制出一份或多份，并在复制出的不同的层之间根据要求连接某些点。

一个典型的应用就是在不同路径上有 $k$ 个决策 $p_1,p_2,p_3$ ，那么对于每个决策 $p_i$ ，我们构建一层新的图使得边 $E(u,v)$ 可以用来表示决策 $p_i$ 。后续的操作经常使用最短路/最长路相关算法求解。

## 例题

### [P4568 [JLOI2011] 飞行路线](https://www.luogu.com.cn/problem/P4568)

#### 题目概述

给定一个包含 $n$ 个节点和 $m$ 条边的带权无向图 $G$ （节点由 $0 \sim n - 1$ 编号）和 $k$ 次决策（$0 \leq k \leq 10$），对于每个决策 $D_i$ ，可以以 $0$ 为边权通过任意一条边一次。求从节点 $s$ 到 $t$ 的最小花费。

#### 分析

容易发现在不考虑进行决策的情况下（即 $k=0$ 时），题目转化为求无向图上的最短路径。显然可以通过 Dijkstra 等算法在 $O(m \log m)$ 时间内解决。

![layered-graph-1](https://blog.samzhangjy.com/assets/posts/layered-graph/layered-graph-1.png)

考虑进行决策。对于每一条边，我们都可以有选择按照原有边权走或者按边权为 $0$ 走两种选择。显然后者只能选择**最多** $k$ 次（**不一定要全选完 $k$ 次**）。那么，我们不妨对于每条边 $E(u,v,w)$ 增设一个决策边 $E'(u,v,0)$ ，即选择走边 $E'$ 意味在边 $E$ 上进行一次决策。

![layered-graph-2](https://blog.samzhangjy.com/assets/posts/layered-graph/layered-graph-2.png)

接下来我们需要考虑限定 $k$ 次决策。容易发现，在上图中，我们在下层新建了 $n$ 个节点 $V_0' \sim V_1'$ ，并将决策边的终点设在了第二层对应点上。这样，对于每一次决策，我们都可以保证单向性（上层的点只能到达下层）。同时，因为每一层的节点之间都有来自原始图的连边，所以不会影响正常边的统计。

显然，对于 $k$ 次决策，我们只需要建立 $k$ 层上述的图即可。

![layered-graph-3](https://blog.samzhangjy.com/assets/posts/layered-graph/layered-graph-3.png)

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int n, m, K, s, t;

struct Edge {
    int v, w;
};
vector<Edge> G[N];
int dis[N], vis[N];

void addEdge(int u, int v, int w) {
    G[u].push_back(Edge{v, w});
}

void dijkstra(int u) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    struct Node {
        int dis, u;

        bool operator>(const Node& a) const {
            return dis > a.dis;
        }
    };
    priority_queue<Node, vector<Node>, greater<Node>> q;
    q.push(Node{0, u});
    dis[u] = 0;
    while (!q.empty()) {
        Node curr = q.top();
        q.pop();
        int u = curr.u;
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto edge : G[u]) {
            int v = edge.v, w = edge.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push(Node{dis[v], v});
            }
        }
    }
}

int main() {
    for (int i = 0; i < N; i++) G[i].clear();
    scanf("%d%d%d", &n, &m, &K);
    scanf("%d%d", &s, &t);
    s++, t++;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        u++, v++;
        addEdge(u, v, w);
        addEdge(v, u, w);
        for (int i = 1; i <= K; i++) {
            int uu = i * n + u, vv = i * n + v;
            addEdge(uu, vv, w);
            addEdge(vv, uu, w);
            addEdge((i - 1) * n + u, vv, 0);
            addEdge((i - 1) * n + v, uu, 0);
        }
    }
    dijkstra(s);
    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= K; i++) {
        ans = min(ans, dis[i * n + t]);
    }
    printf("%d\n", ans);
    return 0;
}
```

需要注意的是，在统计答案时我们需要在 $k$ 层中取最小值，因为不一定需要 $k$ 次决策才能到达终点。

### [P3119 [USACO15JAN] Grass Cownoisseur G](https://www.luogu.com.cn/problem/P3119)

#### 题目概述

给定一个 $n$ 个点 $m$ 条边的有向图 $G$ 和 $1$ 次决策，求从 $1$ 号节点返回到 $1$ 号节点的最长路。

定义一次决策为将任意一条边 $E(u,v)$ 变为 $E'(v, u)$ 。

#### 分析

考虑建图。显然可以将决策转化为分层图求解。

对于原图 $G$ ，我们新建一个图 $G'$ 使得 $G'=G$ 。然后，我们对于 $E(u,v) \in G$ ，$E'(u',v') \in G'$ 间建立有向边 $E''(v, u')$ ，即对于原图和复制图中的每个点之间建立反向边。

然后可以考虑求最长路。显然上述做法建出来的图无法保证是 DAG ，故先进行 Tarjan 缩点后重新建带权图，最后使用拓扑排序求最长路。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int n, m;
int dfn[N], low[N], color[N], sccCnt = 0, idx = 0, vis[N];
set<int> scc[N];
stack<int> s;
int dis[N], inDegree[N];

class Graph {
  private:
    vector<int> G[N];

  public:
    int inDegree[N];

    void addEdge(int u, int v) {
        G[u].push_back(v);
        inDegree[v]++;
    }

    vector<int> operator[](int x) {
        return G[x];
    }
} G, G2;

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    vis[u] = 1;
    s.push(u);
    for (auto v : G[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (vis[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        sccCnt++;
        while (!s.empty()) {
            int x = s.top();
            s.pop();
            scc[sccCnt].insert(x);
            color[x] = sccCnt;
            vis[x] = 0;
            if (u == x) break;
        }
    }
}

void toposort(int s) {
    queue<int> q;
    for (int i = 1; i <= sccCnt; i++) {
        if (G2.inDegree[i] == 0) q.push(i);
    }
    dis[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto v : G2[u]) {
            G2.inDegree[v]--;
            if (G2.inDegree[v] == 0) {
                q.push(v);
            }
            if (dis[u] >= 0) dis[v] = max(dis[v], dis[u] + (int)scc[v].size());
        }
    }
}

int main() {
    memset(dis, -0x3f, sizeof(dis));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G.addEdge(u, v);
        G.addEdge(v, u + n);
        G.addEdge(u + n, v + n);
    }
    for (int i = 1; i <= 2 * n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int u = 1; u <= 2 * n; u++) {
        for (auto v : G[u]) {
            if (color[u] == color[v]) continue;
            G2.addEdge(color[u], color[v]);
        }
    }
    toposort(color[1]);
    printf("%d\n", max(dis[color[1]], dis[color[1 + n]]));
    return 0;
}
```

## 总结

分层图是一种实用的建图思想，可以解决多种图上决策问题。实际使用中需要注意层与层之间的联系，必要时可结合 Tarjan 缩点后处理。

浅谈分层图最短路


## 强连通分量

有向图 G 强连通是指，G 中任意两个结点连通。

强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。

## 原理

Tarjan 算法是一种基于 DFS 生成树的回溯算法。在递归搜索图的过程中，Tarjan 主要维护了以下两个变量：

- `dfn[i]` ：时间戳，即按 DFS 序遍历到节点 $i$ 的次序；
- `low[i]` ：在以节点 $i$ 为根的子树中，能够回溯到且仍在栈中的节点的最小时间戳。

其中，在搜索过程中，设当前节点为 $u$ ，会遇到如下情况：

- $u$ 未被访问过：搜索 $u$ 的子树，并用 `low[u]` 更新 `low[i]` ；
- $u$ 已经被访问过，但仍在栈中：用 `dfn[u]` 更新 `low[i]` ；
- $u$ 已经被访问过，且不在栈中：说明 $u$ 所在强连通分量已经搜索完毕，无需做任何操作。

显然，当 `low[i] = dfn[i]` 时，存在一个以 $i$ 为根的强连通分量。我们将 $i$ 及在 $i$ 之后入栈的节点依次出栈并记录，此时这些节点所构成的强连通图即为原图 $G$ 的一个强连通分量。

## 实现

```cpp
int low[N], dfn[N], color[N], idx = 0, sccCnt = 0;
stack<int> s;
set<int> scc[N];

void tarjan(int u) {
    low[u] = dfn[u] = ++idx;
    s.push(u);
    for (auto v : G[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (!color[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        sccCnt++;
        while (!s.empty()) {
            int x = s.top();
            s.pop();
            color[x] = sccCnt;
            scc[sccCnt].insert(x);
            if (x == u) break;
        }
    }
}

int main() {
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    return 0;
}
```

其中，`color[i]` 表示节点 $i$ 所在强连通分量编号，`sccCnt` 表示强连通分量个数。

set `scc[i]` 中存储了编号为 $i$ 的强连通分量所包含的节点。

## 缩点与重新构图

在一些题目中，存在着由多个节点构成的环或连通图。由于强连通分量内每个节点互相可达，我们常常需要使用 Tarjan 或类似算法将这些强连通分量缩为一个点以便使用其他算法求解。这个过程就是**缩点**。

### P2341 受欢迎的牛

题目链接：<https://www.luogu.com.cn/problem/P2341>

在这道题中，奶牛之间的关系显然可以化为有向图求解。显然，在这个有向图中，每个强连通分量里的奶牛都互相喜欢。那么，我们可以对其进行缩点操作。

显然，如果存在明星奶牛，一定存在一个强连通分量，使得该强连通分量缩点后的节点出度为 $0$ 。明星奶牛的个数也就是该强连通分量中的节点数量。

需要注意的是，在缩点后的图中，若存在 $\geq 2$ 个满足上述条件的强连通分量，那么这个图中不存在任何一个明星奶牛，因为无法满足所有其他的奶牛都喜欢该强连通分量中的奶牛。

代码实现：

```cpp
//  P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

#include<bits/stdc++.h>

using namespace std;
const int N = 1e4 + 10, M = 5e4 + 10;

int n, m;

class Graph {
private:
    vector<int> G[N];

public:
    int outDegree[N];

    void addEdge(int u, int v) {
        this->G[u].push_back(v);
        this->outDegree[u]++;
    }

    vector<int> operator[] (int idx) {
        return this->G[idx];
    }
} G1, G2;

int low[N], dfn[N], color[N], idx = 0, sccCnt = 0;
stack<int> s;
set<int> scc[N];

void tarjan(int u, Graph& G) {
    low[u] = dfn[u] = ++idx;
    s.push(u);
    for (auto v : G[u]) {
        if (!dfn[v]) {
            tarjan(v, G);
            low[u] = min(low[u], low[v]);
        } else if (!color[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        sccCnt++;
        while (!s.empty()) {
            int x = s.top();
            s.pop();
            color[x] = sccCnt;
            scc[sccCnt].insert(x);
            if (x == u) break;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G1.addEdge(u, v);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i, G1);
    }
    for (int u = 1; u <= n; u++) {
        for (auto v : G1[u]) {
            if (color[u] != color[v]) {
                G2.addEdge(color[u], color[v]);
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= sccCnt; i++) {
        if (G2.outDegree[i] == 0) {
            if (!ans) ans = scc[i].size();
            else {
                printf("0\n");
                return 0;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}
```



浅谈 Tarjan


## 前言

作为第一次参加这样一个具有广泛辨识性的国际大赛的 OIer ，内心还是相当激动的，故写下这篇游记来记录一下。

笔者初二，作为打星队与其他两个队员一起去参加了 ICPC 区域赛西安站的比赛。赛区选址在西北工业大学长安校区，离西安市区远的不是一星半点，坐车需要一个半小时。

这次队友是：

- 李子晨（六年级）
- 张嘉宁（初一）

没想到我是最大的。。

## 5.13 星期六

从机场坐飞机到西安，大概两个小时就到了。本身打算订火车的，但是下午还有 NOC 的比赛，怕来不及就改了机票。下午 1:00 左右下了飞机，出机场就已经快 2:00 了，准备打车去学校附近的酒店。

下午 3:00 办完入住之后在附近吃了点面，3:30 回酒店打 NOC 的复赛。

NOC 的复赛倒不是很难，1.5h 打满 AK 了，就当是 ICPC 的热身吧。

晚上跟队友去签了到，逛了逛西工大，校园还是挺好看的。

![icpc-1](https://www.samzhangjy.com/assets/posts/icpc/icpc-1.jpeg)

![icpc-2](https://www.samzhangjy.com/assets/posts/icpc/icpc-2.jpeg)

![icpc-3](https://www.samzhangjy.com/assets/posts/icpc/icpc-3.jpeg)

![icpc-4](https://www.samzhangjy.com/assets/posts/icpc/icpc-4.jpeg)

![icpc-5](https://www.samzhangjy.com/assets/posts/icpc/icpc-5.jpeg)

![icpc-6](https://www.samzhangjy.com/assets/posts/icpc/icpc-6.jpeg)

![icpc-7](https://www.samzhangjy.com/assets/posts/icpc/icpc-7.jpeg)

![icpc-8](https://www.samzhangjy.com/assets/posts/icpc/icpc-8.jpeg)

![icpc-9](https://www.samzhangjy.com/assets/posts/icpc/icpc-9.jpeg)

![icpc-10](https://www.samzhangjy.com/assets/posts/icpc/icpc-10.jpeg)

## 5.14 星期日

正式比赛。

早上 7:00 起的，吃了个肉夹馍 9:00 去参加的热身赛。

热身赛没咋好好打，主要就是熟悉了一下 CodeBlocks 该怎么用，顺带培训了一下队友 Ubuntu 的使用方法。

9:30 热身赛结束之后想去看开幕式发现楼下已经坐满了，遂在三楼机房附近围着看了一下。

![icpc-11](https://www.samzhangjy.com/assets/posts/icpc/icpc-11.jpeg)

10:00 正式开赛，我们题还没从袋子里拿出来一刷榜发现已经有人把签到题秒了，遂开了 G 题。

G 题一眼发现性质，答案永远是 $1 \sim n$ 的数列，循环输出就行。于是乎我就打了一个 `for` 循环交上去过了，用时大概 5 min 。

后来发现别的题其他队也没有成功的提交，于是三个人开了三个题，我开 J 题，zjn 开了 I 题，lzc 开了 E 题。

J 题我研究一段时间之后发现没有太多思路，正好 lzc E 题也卡住了就去和他交流一下 J 题。

讨论的过程中我发现可以用类似倍增的方法进行求解，和 lzc 确定了大致思路之后敲了一下代码过掉了 J 题。这里有一个有戏剧性的小插曲就是这份代码由于精度问题甚至没有过第三个 `1 0` 的样例。。但是估计评测的时候有 SPJ ，我们又把精度调高了所以给过了。

这时候已经快 12:00 了，我们刚刚过 2 题。

在此期间 zjn 一直在搞 I 题，发现了一个操作 $2$ 的规律：$\text{round}(\sqrt{2x} + 1)$ 有类似 $[2, 3, 3, 4, 4, 4]$ 的性质，又鼓捣了一下敲了两个二分发现答案一直不对。最后 debug 了半天交了好几发终于过了 I 题。神奇的是这道题在我们过的时候只有 4 个队 A 了，环顾四周发现几乎没有人有 I 题的棕色气球。

此时差不多 12:50 ，过了 3 题，但是罚时由于之前 I 题交的太多很高。

zjn 搞 I 题的时候我和 lzc 在看当时很多队伍过掉了的 A 题。一开始以为是博弈题，一直没有研究明白，后来发现合法的序列是可以通过某些条件构造的，但是没有在限定复杂度内求解的思路。zjn 也来看了 A 题，仍然是没有头绪。最后快 14:00 的时候 lzc 搞了一个我高攀不起的逆元过掉了 A。

在这之前我们暂时放弃了 A ，我开始开 E 题，lzc 开 H 题。E 题一开始脑子一热以为是二维前缀和，写完代码才发现样例都过不去，之后也没有想出来很好的处理方式，摆了。lzc 的 H 题好像发现了一个重要的性质，20 多行的代码就过了 H 题，我和 zjn 直呼牛逼。

最后一个小时 zjn 在用 DP 搞 E 题，我和 lzc 开 D 题。最后 E 题没搞出来，D 题倒是有一个复杂度在边缘的 $O(n^2m)$ 的解法，但是实现的时候只有 20 min ，有个奇怪的 bug 没有找出来，300 分钟的时候交了一发错解 WA 了，比赛结束。

奇怪的是最后竟然过了五题，排名88 ，拿了银牌。神奇的是最后因为失误给我们发了牌子，但是问了一下之后照完相就还给人家了。

![icpc-12](https://www.samzhangjy.com/assets/posts/icpc/icpc-12.jpg)

![icpc-13](https://www.samzhangjy.com/assets/posts/icpc/icpc-13.jpg)

![icpc-14](https://www.samzhangjy.com/assets/posts/icpc/icpc-14.jpeg)

~~总的来说，这场比赛全靠 lzc A 的 3 道题和 zjn 的 I 题~~

ICPC 2023 西安站游记

CSP-J 2022 题解


## 题目描述

### 说明

wjr 最近学习了《树》的概念

他觉得很有趣，于是自己花了一棵包含 n*n* 个节点的树，每条边的边长不一定相同，并且自己指定了一个节点 $p$ 为根节点

为了让这棵树更加有趣，wjr 把每条边设置成了有向边，这条边只允许从父亲走向儿子

现在 wjr 想知道，这棵树上有多少路径长度为 $k$ 的简单路径？

### 输入格式

输入第一行包含三个整数 n,p,k*n*,*p*,*k*，如题意所示。

接下来 n-1*n*−1 行每行包含三个整数 u,v,x*u*,*v*,*x* ，表示节点 u*u* 和节点 v*v* 之间存在一条长度为 x*x* 的边。


对于 $20\%$ 的数据: $10 \leq n \leq 100$。

对于 $50\%$ 的数据: $10 \leq n \leq 3000$。

对于 $100\%$ 的数据: $10 \leq n \leq 200000;1 \leq p \leq n;1 \leq x \leq 10^5;1 \leq k \leq 10^5$。

### 输出格式

输出一行，该行包含一个整数，表示答案

### 样例

#### 输入数据 1

```input1
5 2 2
2 1 2
2 3 1
3 4 1
3 5 1
```

#### 输出数据 1

```output1
3
```

## 题解

昨天%你赛的题，暴力挂了拿了零分。看了题解之后发现好巧妙，于是诞生了这篇文章。

首先肯定这是一道裸的图论题，求树上权值和为 $k$ 的简单路径数目。题目规定每条边是有向边，但是后面能发现这是个巨坑。

首先既然是棵树，我们不难想到跟这道题有关的性质：

- 从根节点到树上任意一个点有且仅有一条唯一路径
- 树上不存在环
- 根节点一定能够到达任意一个节点

首先想到的是考虑枚举每个点从它的祖宗节点经过的每条路径（可能有重合）的权值和，但显然 $O(n^2)$ 的复杂度会超时。

~~考虑到上道题就是滑动窗口，~~考虑使用滑动窗口的方式进行优化。从树上每个叶子节点向上遍历直到根节点的路径是唯一的，所以可以使用树上滑动窗口解决。

具体操作就是找到一个叶子节点后，对从该节点到根节点的这条路径进行滑动窗口，在缩小左端点的同时尽可能缩小右端点。说的形象点就是像蛇一样在这条路径上伸缩，直到总和为 $k$ 或者到达根节点为止。

目前为止，一切看起来都还好，只需要实现树上滑动窗口即可。但是，仔细看题可以发现，给定的边并没有指定位置关系：$u$ 可以是 $v$ 的父亲，也可能是 $v$ 的孩子！例如下面这棵树：

![tree](/assets/posts/solution-root-tree/tree.png)

这时，如果配上这样的输入：

```5 1 3
5 4 1
3 4 2
1 3 1
2 1 3
```

我们的算法就会出现错误的结果。解决方案也很简单，建立双向边即可。这就是这道题最大的坑点，也是最巧妙的点。建立双向边之后我们只需要判断是否走重即可。

## 代码

```cpp
#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 2 * 1e5 + 10;

struct Node {
    int id, w, p;

    Node() {}

    Node(int _id, int _w, int _p) { this->id = _id, this->w = _w; this->p = _p; }
};

queue<Node> q;
int h[N], vtx[2 * N], nxt[2 * N], w[2 * N], idx, vis[2 * N];
int n, p, k, ans, maxEdge, fa[2 * N], sum[2 * N];

void addEdge(int a, int b, int c) {
    vtx[idx] = b, nxt[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dfs(int prev, int cur) {
    fa[cur] = prev;
    int p = h[cur];
    bool isLeaf = true;
    while (p != -1) {
        if (prev == vtx[p]) {
            p = nxt[p];
            continue;
        }
        isLeaf = false;
        sum[vtx[p]] = sum[cur] + w[p];
        dfs(cur, vtx[p]);
        p = nxt[p];
    }
    if (isLeaf) {
        int l = cur, r = cur;
        while (r != p) {
            if (vis[l] || sum[l] < k) break;
            vis[l] = 1;
            while (sum[l] - sum[r] < k) r = fa[r];
            if (sum[l] - sum[r] == k) ans++;
            l = fa[l];
        }
    }
}

int main() {
    memset(h, -1, sizeof(h));
    cin >> n >> p >> k;
    for (int i = 1; i <= n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    dfs(-1, p);
    cout << ans << endl;
    return 0;
}
```

AC++!

wjr的有根树 题解


## 什么是树状数组？

**树状数组**， 或 Binary Indexed Tree（也称 **Fenwick Tree** ），是一种能够高效更新并计算数列前缀和的数据结构。

树状数组的实现主要基于计算二进制 lowbit（也就是值为 $1$ 的最低位）。

## 原理

既然树状数组与线段树类似，我们不妨将线段树的实现方式先搬过来看看。对于一个表示数列 $a_i$ 的线段树 $S$ ，线段树会通过数列 $a$ 递归建树，使用类似归并的思想维护节点。一开始，线段树为空，然后从根节点开始分枝，再进行递归展开，如此往复，直到叶子结点为止。

也就是说，在线段树中每一个非叶子结点都管理着当前孩子结点的信息。这种操作的具体实现就是 `pushup` 操作。这样在查询时，我们只需要找到对应的父亲节点即可。

而树状数组所使用的策略与线段树几乎别无二致：同样适用父亲节点来表示其孩子节点的信息，且同为递归定义。同样地，在查询时只需要查询所属叶子结点的父亲节点即可。显然，对于根节点将会管理数列中的所有节点的信息。

![fenwick-1](https://blog.samzhangjy.com/assets/posts/fenwick-tree/fenwick-1.png)

上图就是一个典型的使用树状数组维护出来的树形结构。最上方的 `a[]` 表示数据数组，一一对于最下方的叶子结点（圆圈）。每一个父亲节点都使用方形表示，控制着至少两个结点。

将上图中的结点进行编号，得：

![fenwick-2](https://blog.samzhangjy.com/assets/posts/fenwick-tree/fenwick-2.png)

每个节点右面的蓝色数字为当前节点的编号。如果将树状数组表达为 $b_i$ ，原始数组为 $a_i$ ，则有：
$$
b_1 = a_1\\
b_2 = a_1 + a_2\\
b_3 = a_1 + a_2 + a_3\\
b_4 = a_4\\
b_5 = a_4 + a_5\\
b_6 = a_4 + a_5 + a_6
$$
如果把下标都转换成二进制，则有：
$$
b_{(1)_2} = a_{(1)_2}\\
b_{(10)_2} = a_{(1)_2} + a_{(10)_2}\\
b_{(11)_2} = a_{(1)_2} + a_{(10)_2} + a_{(11)_2}\\
b_{(100)_2} = a_{(100)_2}\\
b_{(101)_2} = a_{(100)_2} + a_{(101)_2}\\
b_{(110)_2} = a_{(100)_2} + a_{(101)_2} + a_{(110)_2}
$$
不难发现其中的规律：
$$
b_i = a_{i - 2^k + 1} + a_{i - 2^k + 2} + \cdots + a_i
$$
其中 $k$ 为 $i$ 的二进制表示下 $1$ 的最低位的位置。例如 $i = (8)_{10} = (1000)_2$ 时，$k = 3,\ b_8 = a_1 + a_2 + \cdots +a_8$ 。

考虑计算下述表达式：
$$
s_i= \sum_{j=1}^{i} a_j
$$
根据 (3) 式易得：
$$
s_i = b_i + b_{i - 2^{k_1}} + b_{i - 2^{k_1} - 2^{k_2}} + \cdots
$$
其中 $k_j$ 表示当前第 $j$ 次访问时，从 $i$ 一直循环对最低位上的 $1$ 取反后当前 $i$ 的值的 $1$ 的最低位。例如，对于计算 $s_4$ ，我们有：
$$
s_4 = b_4 + b_{4 - 2^0} = b_4 + b_3 = a_4 + a_1 + a_2 + a_3 = 25
$$
其中 $k$ 的二进制变化过程为：
$$
k = (4)_{10} = (100)_2 \rarr k = (100)_2 - (100)_2 = (0)_2 \rarr \text{End.}
$$
这样我们就完成了前缀求和操作。

对于修改操作，我们也可以采用类似的思想。修改操作无非就是将给定的增加值依次向上更新传递。例如，将 $a_5$ 增加 $3$ 我们需要依次向上更新 $b_5$ 与 $b_6$ 。这样的变化过程在求和操作时已经说明，只需要进行反向操作即可。

对于 $a_5 = a_{(101)_2}$  ，我们需要更新其所有祖宗节点，即所有包括 $a_5$ 值的 $b_i$ 。我们不妨从 $i = (5)_{10} = (101)_2$ 进行操作。注意到 $a_5$ 的父亲节点包括 $\{b_5, b_6\} = \{b_{(101)_2}, b_{(110)_2}\}$ 。所以可以将 $i$ 每次增加 $2^k$ ，其中 $k$ 为 $i$ 的二进制表示下 $1$ 的最低位的位置。$i = 5$ 时 $k$ 的变化过程如下：
$$
i = 5 = (101)_2,\ k = 0 \rarr i = i + 2^k = 5 + 1 = 6,\ k = 1 \rarr \text{End.}
$$
这样我们就可以进行单点修改操作。

## 实现

注意到上述所有操作都依赖于一个重要操作：求某数 $x$ 的二进制下最低 $1$ 的位置 $k$。这时不妨引出一个简单的函数 `lowbit` ：

```cpp
int lowbit(int x) {
  return x & -x;
}
```

该函数的返回值即为 $2^k$ ，而树状数组所需操作也仅仅是 $2^k$ 的值。该函数原理如下：

1. 若 $x = (17)_{10}$ ，则其补码为 $(010001)_补$ ，$(-x)_补$ = $(101111)_补$ 。
2. 计算 `x & -x` ，结果为 $(000001)_2 = (1)_{10}$ 。
3. 验证上述操作，$x$ 的二进制最低 $1$ 的位置从零开始计数为 $0$ ，$2^k = 2^0 = 1$ ，结果正确。

于是我们便不难写出模板代码：

```cpp
template <typename T = int>
class FenwickTree {
   private:
    T tr[N];

    int lowbit(int x) { return x & -x; }

   public:
    void add(int x, T k) {
        while (x <= N) {
            tr[x] += k;
            x += lowbit(x);
        }
    }

    T prefix_sum(int x) {
        T ans = 0;
        while (x >= 1) {
            ans += tr[x];
            x -= lowbit(x);
        }
        return ans;
    }
  
    T sum(int l, int r) {
      return prefix_sum(r) - prefix_sum(l - 1);
    }
};
```

不难发现虽然基本操作是前缀和，但仍然可以使用两个前缀和的差求出任意区间和。值得注意的是，虽然 `lowbit` 函数仅支持整数操作，但树状数组支持任意数据类型：`lowbit` 维护的是数组下标，并不对实际内容进行操作。

不难发现求和与修改操作都是 $O(\log n)$ 的：每次操作的最坏情况即为从叶子结点更新至根节点，也就是需要遍历 $h = \text{树高}$ 次。而树状数组又是完全二叉树，所以 $h \leq \log_2(n)$ 。

对比线段树，我们发现树状数组并不能很高效地处理区间更新问题。注意到原本的前缀和操作，我们不妨将其改为差分操作。这样，每次存储 $b_i$ 则为 $a$ 的差分数组，即 $b_i = d_i + d_{i - 1} + \cdots + d_1$ ，其中 $d_i$ 表示 $a$ 的差分数组，即 $d_i = a_i - a_{i - 1}$ 。

这样，对于修改操作我们只需要对 $b_l$ 增加 $x$ ，$b_r$ 减少 $x$ 即可。当前这样的坏处就是无法进行区间查询操作：对差分数组进行求和相对原数组而言已经失去意义。但是，我们仍可以通过差分数组的特性来查询某一节点的值：对前 $i$ 个差分数组元素进行求和即为原数组的第 $i$ 个元素的值。

尽管无法直接进行区间求和的维护操作，我们仍可以通过维护两个树状数组的方式同时进行区间修改与区间查询的操作。参考 [OI-Wiki](https://oi-wiki.org/ds/fenwick/#%E5%8C%BA%E9%97%B4%E5%8A%A0--%E5%8C%BA%E9%97%B4%E6%B1%82%E5%92%8C) 。但是本人认为进行这样的操作不如使用线段树方便。

例题：<https://www.luogu.com.cn/problem/P3368> 。

显然对于这道题，我们需要进行区间修改与单点查询。参考代码如下：

```cpp
// Problem: P3368 【模板】树状数组 2
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3368
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 5 * 1e5 + 10;

int bit[N], n, m, x, y, k, op, a[N];

int lowbit(int x) { return x & -x; }

void add(int x, int k) {
    while (x <= n) {
        bit[x] += k;
        x += lowbit(x);
    }
}

int prefix_sum(int x) {
    int ans = 0;
    while (x >= 1) {
        ans += bit[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        add(i, a[i] - a[i - 1]);
    }
    for (int i = 1; i <= m; i++) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> k;
            add(x, k);
            add(y + 1, -k);
        } else {
            cin >> x;
            cout << prefix_sum(x) << endl;
        }
    }
    return 0;
}
```

注意到核心模板代码无需改变。

## 总结

不难发现，朴素树状数组可以进行大部分线段树可以进行的操作：区间求和与单点更新、区间修改与单点查询。但是，这两组操作却无法使用一个树状数组同时实现。简单来说，树状数组能做的操作线段树也一定能做，但反之却不亦然。

在对于高级操作没有要求的题目下，使用树状数组是一个很好的选择，因为其代码复杂度明显较低。但在复杂的题目时，线段树会略胜一筹。

值得注意的是，虽然线段树与树状数组时间复杂度相同，但树状数组常数略小。在更新操作时，树状数组不一定一定要遍历 $\log n$ 个节点，而线段树却必须遍历所有 $\log n$ 个节点。但是该常数复杂度可以忽略，二者时间消耗均等。但是树状数组在空间消耗上要明显低于线段树：线段树通常需要 $4$ 倍的数组空间，而树状数组仅需要 $1$ 倍。

总之，哪个好用用哪个。

浅谈树状数组


## 什么是堆？

堆是一种特殊的树，其每个节点都有一个权重 $w_i$ ，且每个节点的权重 $w_i$ 均小于/大于其父亲节点。

![heap-1](https://tva1.sinaimg.cn/large/e6c9d24ely1h57n9ki8lhj207w08j3yj.jpg)

上图就是一个典型的堆。如果每个节点的权重都 $\geq$ 其父亲节点的权重，那么这个堆就是一个小根堆，反之则是大根堆。不难发现，上图是一个小根堆。

我们今天所要讨论的二叉堆则是一个用数组维护的完全二叉树，也适用于上述规则。

C++ STL 中的 `priority_queue` 就是一个典型的堆。

## 堆的操作

### 插入

给定一个合法的堆 $H$ ，现在需要插入一个权值为 $x$ 的元素到 $H$ 中，这就是插入操作。还是上面的那棵树，现在我们希望加入一个元素 $5$ 到堆里：

![heap-2](https://blog.samzhangjy.com/assets/posts/heap/heap-2.png)

下方的数组表示当前堆的存储情况。很显然我们可以先随便把这个节点加到堆里，然后再想办法维护整个堆使其合法。那么我们将新节点先挂载到节点 6 的位置（数组下标），然后考虑如何进行维护。

显然对于当前节点无非就有两种情况：

1. 当前节点小于父亲节点，需要向上移动；
2. 当前节点大于等于父亲节点，无需移动。

那么我们就可以一直向上移动新节点直到满足情况 (2) 时为止。

![heap-3](https://blog.samzhangjy.com/assets/posts/heap/heap-3.gif)

对于这个堆，我们只需要将新节点向上移动一层即可。这个操作就叫做 **向上调整** ，或 **Decrease Key** ，代码如下：

```cpp
// 向上调整操作，x 为需要进行调整位置的元素下标
void up(int x) {
  while (x > 1 && H[x] < H[x / 2]) {
    // 遇到不合法的就交换父亲节点与当前节点
    swap(H[x], H[x / 2]);
    x /= 2;
  }
}

// 插入操作，x 为需要插入的值
void insert(int x) {
  n++;
  H[n] = x;
  up(n);
}
```

该算法的时间复杂度为 $O(\log n)$ ，其中 $n$ 为节点数。证明显而易见，`up()` 函数中的 `while` 循环最多执行 $k$ 次，其中 $k$ 为堆的高度。显然，$k = \log n$ 。

### 删除

删除操作将会删除当前堆的根节点，在我们的堆中也就是最小的元素。很明显我们没办法直接删除根节点，因为那样会导致整个堆变成两个堆。我们不妨考虑将根节点与最后一个节点互换，然后再像插入操作那样想方设法维护这个堆使其满足性质。

很明显交换、删除根节点后的堆可能不满足我们小根堆的性质，也就是根节点可能比孩子节点还要大。那么我们就可以按照向上调整的思路，写出 **向下调整** ，来维护我们的堆。

对于向下调整，我们从当前节点的子节点中找到一个最小的元素互换，一直重复此操作到最下层。

![heap-4](https://blog.samzhangjy.com/assets/posts/heap/heap-4.gif)

参考代码：

```cpp
// 向下调整操作，x 为需要调整的下标
void down(int x) {
  while (x * 2 <= n) {
    int cur = x * 2;
    if (cur + 1 <= n && H[cur + 1] < H[cur]) cur++;
    // 当前子树根节点符合条件意味着子树的子树也符合条件了
    if (H[cur] <= H[x]) break;
    swap(H[cur], H[x]);
    x = cur;
  }
}

// 删除根节点操作，返回原根节点的值
int remove() {
  int ret = H[1];
  H[1] = H[n], n--;
  down(1);
}
```

删除操作的时间复杂度同样为 $O(\log n)$ ，其中 $n$ 为元素个数。证明同插入操作。

### 查询

查询操作能够查找当前堆内的最小（或最大，依据大小根）元素。这可能是所有二叉堆操作中最没有脑子的一个了……直接返回根节点即可。代码如下：

```cpp
// 查询操作，返回当前堆内最小值（根节点）
int query() {
  return H[1];
}
```

显然时间复杂度为 $O(1)$ 。

### 建堆

基本的增删改查操作有了，接下来就是如何从一个一直序列中转化为堆了。很显然我们可以从空堆开始逐个进行 `insert` 操作，时间复杂度为 $O(n \log n)$ 。那么，有没有时间复杂度更优的算法呢？

答案是肯定的。如果我们用逆向思维思考整个问题，从最底层的叶子节点开始，进行向下调整的操作，使得当前每个子节点的子树都满足堆的条件。这样，我们变相地合并了两个子堆，从而达到了我们想要的结果。

参考代码如下：

```cpp
// 建堆操作，a[] 为原始序列，n 为序列长度
void build(int a[], int n) {
  for (int i = 1; i <= n; i++) H[i] = a[i];
  for (int i = n; i >= 1; i--) down(i);
}
```

该算法的时间复杂度为 $O(n)$ ，关于时间复杂度的证明可以参见 [OI-Wiki](https://oi-wiki.org/ds/binary-heap/#%E6%96%B9%E6%B3%95%E4%BA%8C%E4%BD%BF%E7%94%A8%E5%90%91%E4%B8%8B%E8%B0%83%E6%95%B4) 或《算法导论》6.3 节。

### 模板题

链接：[洛谷 P3378 堆](https://www.luogu.com.cn/problem/P3378) 。

题目要求增删查三种操作，妥妥的模板。下面给出面向对象版的代码：

```cpp
// Problem: P3378 【模板】堆
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3378
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 1e6 + 10;

int n, op, x;

template <typename T, int N = int(1e6 + 10), typename U = less<int>>
class Heap {
   private:
    int size;
    T H[N];
    U cmp = U();

   public:
    Heap() { size = 0; }

    void up(int x) {
        while (x > 1 && cmp(H[x], H[x / 2])) {
            swap(H[x], H[x / 2]);
            x /= 2;
        }
    }

    void insert(int x) {
        size++;
        H[size] = x;
        up(size);
    }

    void down(int x) {
        while (x * 2 <= size) {
            int cur = x * 2;
            if (cur + 1 <= size && cmp(H[cur + 1], H[cur])) cur++;
            if (cmp(H[x], H[cur])) break;
            swap(H[cur], H[x]);
            x = cur;
        }
    }

    int remove() {
        int ret = H[1];
        H[1] = H[size], size--;
        down(1);
        return ret;
    }

    int query() { return H[1]; }

    bool empty() { return size <= 0; }
};

Heap<int> H;

int main() {
    cin >> n;
    while (n--) {
        cin >> op;
        if (op == 1) {
            cin >> x;
            H.insert(x);
        } else if (op == 2) {
            if (H.empty()) continue;
            cout << H.query() << endl;
        } else {
            if (H.empty()) continue;
            H.remove();
        }
    }
    return 0;
}
```

## 对顶堆

对顶堆，顾名思义，是一种由一对大小根堆结合而成的数据结构，可用于**动态维护序列的第 $k$ 大值**，例如动态维护序列中位数等。

*【详情待补充】*

浅谈堆


看到各位大佬都是用的 Floyd ，让本蒟蒻来~~水~~一篇 SPFA 吧（）

## Description

给定一个边权均为 $1$ 的有向无环图，求该图的最长路。

## Solution

看到题第一反应是这题好难，但其实不然。所谓“最长路”只不过就是把边权都换成负数在新图上面跑一遍最短路而已。

于是，我们就可以开开心心地敲上 SPFA 板子然后取最值啦！

## Code

```cpp
// Problem: UVA10000 Longest Paths
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA10000
// Memory Limit: 0 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 5010, INF = 0x3f3f3f3f;

int n, T = 1, u, v, ans, minn, s;
int h[N], w[N], vtx[N], nxt[N], idx;
long long dis[N], vis[N];
queue<int> q;

// 邻接表存图
void addEdge(int a, int b, int c) {
    vtx[idx] = b, nxt[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// SPFA 板子
void spfa(int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.push(s);
    vis[s] = 1;
    while (!q.empty()) {
        int tmp = q.front();
        vis[tmp] = 0;
        int p = h[tmp];
        while (p != -1) {
            int v = vtx[p];
            if (dis[tmp] + w[p] <= dis[v]) {
                dis[v] = dis[tmp] + w[p];
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
            p = nxt[p];
        }
        q.pop();
    }
}

int main() {
    while (cin >> n) {
        // 输入到0结束
        if (n == 0) break;

        // 初！始！化！
        memset(h, -1, sizeof(h));
        memset(vtx, 0, sizeof(vtx));
        memset(nxt, 0, sizeof(nxt));
        memset(w, 0, sizeof(w));
        idx = 0;

        cin >> s;
        // 存边
        while (cin >> u >> v) {
            if (u == 0 && v == 0) break;
            // 存的是负边权
            addEdge(u, v, -1);
        }

        spfa(s);
        ans = -1, minn = INF;
        for (int i = 1; i <= n; i++) {
            if (dis[i] < minn) {
                ans = i, minn = dis[i];
            }
        }
        cout << "Case " << T << ": The longest path from " << s
             << " has length " << -minn << ", finishing at " << ans << "."
             << endl
             << endl;
        T++;
    }
    return 0;
}
```

## 附：为什么不能用 Dijkstra 求最长路

Dijkstra 使用贪心算法来计算最短路，依赖于最优子结构求解。与存在负边权的图同理，使用 Dijkstra 求最长路不满足最优子结构的条件：选择当前最长的边不一定代表总体最长。

在任意图上求最长路[被证明是 NP-Hard 的](https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs) ，但如果在类似此题中的 DAG（有向无环图）中最长路却可以使用这篇题解中的 SPFA 之类的算法求解。

**参考：**

- <https://en.wikipedia.org/wiki/Longest_path_problem>
- <https://stackoverflow.com/questions/8027180/dijkstra-for-longest-path-in-a-dag>
- <https://blog.csdn.net/hesorchen/article/details/115370721>

如果题解中有错误还请大佬指出qwq

[图论] UVA10000 Longest Paths 题解


## 什么是 ST 表

ST 表，即 Sparse Table ，是一种基于倍增思想的数据结构，常用来解决静态 RMQ（**R**ange **M**inimum / **M**aximum **Q**uery，区间最值询问）问题。

一般来讲，ST 表可用于解决大部分区间可重复贡献问题。此处的**可重复贡献问题**指，对于任意的运算 $\text{opt}$ ，满足 $x\ \text{opt}\ x = x$ 的即为可重复贡献问题，例如对于最值问题有 $\max(x,x) = x$。[^1]

## 浅析 ST 表

ST 表的基本思路基于可重复贡献问题的特性，即两个重叠子问题的重复计算不会影响最终的计算答案。下面是一道 ST 表的模板题：

给定 $N$ 个数字与 $M$ 次询问，求对于任意询问 $i$ ，区间 $[l_i, r_i]$ 内的最大值。

详见 [洛谷 P3865](https://www.luogu.com.cn/problem/P3865) 。

对于这个问题，不难想到暴力的解法：对于每个询问查询最大值，但是在 $M \leq 2 \times 10^6$ 的数据范围下很明显会超时。于是我们考虑倍增的思路：用 $f(i,j)$ 表示第 $i$ 个数往后 $2^j - 1$ 个数的最大值，即区间 $[i, i + 2^j - 1]$ 的最大值。

于是，有了这样的定义，我们不难发现 $f(i,j)$ 的值取决于 $[i, i + 2^{j - 1} - 1]$ 与 $[i + 2^{j - 1}, i + 2^j - 1]$ 的值，如此往复，在实现过程中的时间复杂度约为 $O(N \times \log N)$ 。

构建部分代码如下：

```cpp
void build() {
    int lim = log2(n);
    for (int j = 1; j <= lim; j++) {
        // i + (1 << j) - 1 为当前区间右端点
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            // 当前值取决于左右两子区间的值
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}
```

接下来是询问操作。对于任意区间 $[l,r]$ ，我们一定能够找到两个区间 $A,B$ ，使得 $A$ 与 $B$ 的并集完全覆盖 $[l,r]$ ，$A$ 与 $B$ 之间可以有重合部分。如果设 $A$ 为左子区间，$B$ 为右子区间，不难发现 $A = [l, l + 2^k - 1]$ ，其中 $k = \log_{2}(r - l + 1)$ 。

对于区间 $B$ ，假设需要找到的左端点为 $x$ ，即 $B = [x, r]$ 。显然需要使得 $x + 2^k - 1 = r$ ，移项，得 $x = r - 2^k + 1$ 。所以区间 $B = [r - 2^k + 1, r]$ 。这样，$A + B$ 的覆盖范围一定包含 $[l, r]$ 中的任意元素，取 $\max(A, B)$ 即为答案。

ST 表的查询操作拥有优秀的 $O(1)$ 时间复杂度，每次仅需进行一次 $\log$ 操作与取最值操作。但取对数的步骤显然可以使用预处理进行优化。查询部分代码如下：

```cpp
int query(int l, int r) {
    int k = log2(r - l + 1);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}
```

基于这样的实现方式，ST 表可以做到 $O(n \log n)$ 的预处理与 $O(1)$ 询问，但是不支持修改操作。完整版代码如下：

```cpp
// Problem: P3865 【模板】ST 表
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3865
// Memory Limit: 125 MB
// Time Limit: 800 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 1e5 + 10, M = 20;

int n, m, a[N], f[N][M];

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

void build() {
    int lim = log2(n);
    for (int j = 1; j <= lim; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int l, int r) {
    int k = log2(r - l + 1);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main() {
    // 数据过大需要优化输入输出
    n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        f[i][0] = a[i];
    }
    build();
    for (int i = 1; i <= m; i++) {
        int l = read(), r = read();
        printf("%d\n", query(l, r));
    }
    return 0;
}
```

## 习题

### P2880 [USACO07JAN] Balanced Lineup G

链接：<https://www.luogu.com.cn/problem/P2880> 。

#### 题目大意

给定 $N$ 个整数以及 $M$ 个询问，求对于每个询问 $i$ ，区间 $[l_i, r_i]$ 的最大值与最小值之差。

#### 分析

几乎是 RMQ 模板题，需要支持两种最值操作，数据范围甚至没有模板题严格，使用朴素 ST 表即可。

#### 代码

```cpp
// Problem: P2880 [USACO07JAN] Balanced Lineup G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2880
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 5 * 1e4 + 10, M = 16;

int n, m, a[N];

template <typename T, typename U = less<int>>
class SparseTable {
   private:
    T f[N][M];
    int len;
    U cmp;

   public:
    SparseTable(int _len, int data[]) {
        len = _len;
        cmp = U();
        for (int i = 1; i <= _len; i++) {
            f[i][0] = data[i];
        }
        build();
    }

    void build() {
        int lim = log2(len), a = -1, b = -1;
        for (int j = 1; j <= lim; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                a = f[i][j - 1], b = f[i + (1 << (j - 1))][j - 1];
                f[i][j] = cmp(a, b) ? a : b;
            }
        }
    }

    int query(int l, int r) {
        int k = log2(r - l + 1);
        int a = f[l][k], b = f[r - (1 << k) + 1][k];
        return cmp(a, b) ? a : b;
    }
};

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    SparseTable<int, less<int>> minTable(n, a);
    SparseTable<int, greater<int>> maxTable(n, a);

    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        cout << maxTable.query(l, r) - minTable.query(l, r) << endl;
    }
    return 0;
}
```

更多习题补充中……

[^1]: 参见 [OI-Wiki](https://oi-wiki.org/ds/sparse-table/#_1) 。

浅谈 ST 表


## 题目

链接：<https://www.luogu.com.cn/problem/P1077>

### 题目描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 $m$ 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 $n$ 种花，从 $1$ 到 $n$ 标号。为了在门口展出更多种花，规定第 $i$ 种花不能超过 $a_i$ 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算，一共有多少种不同的摆花方案。

### 输入格式

第一行包含两个正整数 $n$ 和 $m$，中间用一个空格隔开。

第二行有 $n$ 个整数，每两个整数之间用一个空格隔开，依次表示 $a_1,a_2, \cdots ,a_n$。

### 输出格式

一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 $10^6+7$ 取模的结果。

### 样例 #1

#### 样例输入 #1

```
2 4
3 2
```

#### 样例输出 #1

```
2
```

### 提示

【数据范围】

对于 $20\%$ 数据，有 $0<n \le 8,0<m \le 8,0 \le a_i \le 8$。

对于 $50\%$ 数据，有 $0<n \le 20,0<m \le 20,0 \le a_i \le 20$。

对于 $100\%$ 数据，有 $0<n \le 100,0<m \le 100,0 \le a_i \le 100$。

NOIP 2012 普及组 第三题

## 题解

### 分析

第一眼看到以为是暴力 DFS ，看了一下数据范围发现自己错了（虽然记忆化好像也能做），于是容易想到动态规划的解法。

那么接下来就要考虑如何进行状态转移了。设 $dp_{i,j}$ 表示当前选了前 $i$ 种花，总计 $j$  盆。不难想到下述转移方程：
$$
dp_{i,j} = \sum_{k = 0}^{a_i} dp_{i - 1, j - k} \mod{p}
$$
其中 $k$ 表示第 $i$ 种花选多少个，那么答案显而易见，求和即可。

这道题其实还可以用滚动数组降维（毕竟只依赖 $i-1$ 的状态），甚至还有大佬直接降维，本蒟蒻 ~~太懒~~ 就不搞了。

### 代码

```cpp
// Problem: P1077 [NOIP2012 普及组] 摆花
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1077
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 110, MOD = 1e6 + 7;

int n, m, a[N], dp[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // 初始化，0盆花只有一种方案（不摆）
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= a[i]; k++) {
                if (k > j) break;  // 大于能选的就退出
                dp[i][j] += dp[i - 1][j - k], dp[i][j] %= MOD;
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}
```

AC++！

[DP] P1077 [NOIP2012 普及组] 摆花 题解


## 题目

链接：<https://www.luogu.com.cn/problem/P1522>

### 题目描述

Farmer John 的农场里有很多 **牧区**。有的路径连接一些特定的牧区。**一片所有连通的牧区** 称为一个 **牧场**。但是就目前而言，你能看到至少有两个牧区通过任何路径都不连通。这样，Farmer John 就有 **多个** 牧场了。

John 想在牧场里添加 **恰好** 一条路径。对这条路径有以下限制：

一个牧场的 **直径** 就是牧场中 **最远** 的两个牧区的距离（本题中所提到的所有距离指的都是 **最短的距离**）。考虑如下的有 5 个牧区的牧场，牧区用 `*` 表示，路径用直线表示。每一个牧区都有自己的坐标：

```plain
                (15,15) (20,15)
                 D       E
                 *-------*
                 |     _/|
                 |   _/  |
                 | _/    |
                 |/      |
        *--------*-------*
        A        B       C
     (10,10)  (15,10) (20,10)
```
这个牧场的直径大约是 $12.07106$，最远的两个牧区是 A 和 E，它们之间的最短路径是 $A \to B \to E$。

这里是 John 的另一个牧场：

```plain
                         *F(30,15)
                        / 
                      _/  
                    _/    
                   /      
                  *------* 
                  G      H
                  (25,10)   (30,10)
```

在这个例子中，他刚好有这两个牧场。John 将会在这两个牧场中各选一个牧区（即从 $\{A,B,C,D,E\}$ 中选择一个牧区，从 $\{F,G,H\}$ 中选择一个牧区），然后用一条路径将它们连起来，使得连通后这个新的更大的牧场的直径尽可能小。

注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。

输入文件包括牧区、它们各自的坐标，还有一个如下的对称邻接矩阵：

```plain
　 A  B  C  D  E  F  G  H 
A  0  1  0  0  0  0  0  0
B  1  0  1  1  1  0  0  0
C  0  1  0  0  1  0  0  0
D  0  1  0  0  1  0  0  0
E  0  1  1  1  0  0  0  0
F  0  0  0  0  0  0  1  0
G  0  0  0  0  0  1  0  1
H  0  0  0  0  0  0  1  0
```

其他邻接表中可能直接使用行列而不使用字母来表示每一个牧区。输入数据中不包括牧区的名字。

输入文件 **至少** 包括两个不连通的牧区。

请编程找出一条连接属于两个 **不同牧场** 的牧区的路径，使得连上这条路径后，这个更大的新牧场的直径尽可能小。输出在所有合法的连接方案中，新牧场直径的最小值。

### 输入格式

第一行一个整数 $N$（$1 \leq N \leq 150$），表示牧区数。

接下来 $N$ 行，每行两个整数 $X,Y$（$0 \leq X ,Y \leq 10^5$），表示 $N$ 个牧区的坐标。注意每个牧区的坐标都是不一样的。

接下来 $N$ 行，每行 $N$ 个数字，代表邻接矩阵 $M$。第 $i$ 行第 $j$ 列的数字为 $1$，表示 $i$ 号牧区和 $j$ 号牧区之间存在一条道路直接相连；第 $i$ 行第 $j$ 列的数字为 $0$，表示 $i$ 号牧区和 $j$ 号牧区之间不存在直接相连的道路。

保证 $M_{i,j} = M_{j,i}$。

### 输出格式

只有一行，包括一个实数，表示所求直径。数字保留六位小数。

只需要打到小数点后六位即可，不要做任何特别的四舍五入处理。

### 样例 #1

#### 样例输入 #1

```
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
```

#### 样例输出 #1

```
22.071068
```

### 提示

样例对应题目描述中的情况。

最优解是连接 C 牧区和 G 牧区，连接后图上只有一个牧场。这个牧场的直径为 $A \to B \to C \to G \to F$，长度约为 $22.071068$。可以证明不存在更优的方案。

USACO 2.4

## 题解

### 分析

这道题，一个字 —— 绕。先解释一下这道题里各个关键词的意思吧：

- 牧区：一个点
- 牧场：由多个牧区组成的连通块
- 两个牧区之间的距离：两个牧区在图上所对应点点最短路
- 牧场的直径：设两个端点分别为 $i,j$ ，使得牧场 $i$ 和牧场 $j$ 之间的距离最大
- 答案：一条端点为 $i,j$ 的路径，使得新的连通块（牧场）的直径最小（也就是说，使这个连通块内两个最远点的最短距离最大）

那么问题就分成了四个子问题：

1. 通过给定的邻接矩阵求出不同的连通块
2. 求任意点 $i,j$ 之间的最短路
3. 求每个牧场的直径
4. 求从每个点出发所到达的最远距离

对于问题一，显然是一个染色问题，考虑使用并查集求解。

对于问题二，注意到点的数量 $N \leq 150$  ，使用复杂度为 $\Theta(n^3)$ 的 Floyd 求多源最短路完全可以满足需求，故采用 Floyd 求解。虽然可以使用 Dijkstra + 斐波那契堆优化至接近 $\Theta(n^2 \times \log n)$ ，但对于此题来说需求不大。

对于问题三、四，显然有了上述两个子问题的结果后不难实现，采用 $\Theta(n^2)$ 的朴素枚举即可。

需要注意的是，最终的答案需要分为三种情况考虑。设当前答案使用 $i \lrarr j$ 边连接连通块 $A,B$ ，则当前答案 $S$ 为：
$$
S = \max(D_{A}, D_{B}, L_{i} + L_{j} + |i,j|)
$$
其中，$D_x$ 表示连通块 $x$ 的直径；$L_x$ 表示从点 $x$ 出发所到达的最远距离，$|u,v|$ 表示边 $u \lrarr v$ 的边权（即长度）。

最后枚举 $i,j$ 求最优答案即可。

### 代码

```cpp
// Problem: P1522 [USACO2.4] 牛的旅行 Cow Tours
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1522
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 200, M = 1e5 + 10, INF = 0x7f7f7f7f;

int n, bin[N];
// max_to_go[i] 表示从i出发到达的最远距离，diameter[i] 表示连通块i的直径
double g[N][N], max_to_go[N], diameter[N], ans = INF;

struct Point {
    int x, y;
} p[N];

int Find(int x) {
    if (bin[x] == x) return x;
    return bin[x] = Find(bin[x]);
}

void Union(int u, int v) {
    int fu = Find(u), fv = Find(v);
    if (fu != fv) {
        bin[fu] = fv;
    }
}

double get_dis(Point a, Point b) {
    return sqrt(pow(a.x - b.x * 1.0, 2) + pow(a.y - b.y * 1.0, 2));
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) bin[i] = i;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].x >> p[i].y;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            char ch;
            cin >> ch;
            if (ch == '1' || i == j) {
                g[i][j] = get_dis(p[i], p[j]);
                Union(i, j);
            } else {
                g[i][j] = INF;
            }
        }
    }
    // Floyd 板子
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        int fi = Find(i);
        for (int j = 1; j <= n; j++) {
            if (Find(i) != Find(j)) continue;
            // 最远距离
            max_to_go[i] = max(max_to_go[i], g[i][j]);
        }
        // 当前连通块的最远距离就是连通块内所有点所能到达的最远距离的最大值
        diameter[fi] = max(diameter[fi], max_to_go[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (Find(i) == Find(j)) continue;
            // 求 i, j 所在连通块的最大直径
            double max_diameter = max(diameter[Find(i)], diameter[Find(j)]);
            // 求最优答案
            ans =
                min(ans, max(max_to_go[i] + max_to_go[j] + get_dis(p[i], p[j]),
                             max_diameter));
        }
    }
    // 六位精度！！
    cout << fixed << setprecision(6) << ans << endl;
    return 0;
}
```

[图论] P1522 [USACO2.4] 牛的旅行 Cow Tours 题解


## 题目

链接：<https://www.luogu.com.cn/problem/P5837>

### 题目描述

Farmer John 最近为了扩张他的牛奶产业帝国而收购了一个新的农场。这一新的农场通过一个管道网络与附近的小镇相连，FJ 想要找出其中最合适的一组管道，将其购买并用来将牛奶从农场输送到小镇。

这个管道网络可以用 $N$ 个接合点（管道的端点）来描述，将其编号为 $1 \ldots N$。接合点 $1$ 表示 FJ 的农场，接合点 $N$ 表示小镇。有 $M$ 条双向的管道，每条连接了两个接合点。使用第 $i$ 条管道需要 FJ 花费 $c_i$ 美元购入，可以支持每秒 $f_i$ 升牛奶的流量。

FJ 想要购买一条管道组成一条单一路径，路径的两端点分别为接合点 $1$ 和 $N$。这条路径的花费等于路径上所有管道的费用之和。路径上的流量等于路径上所有管道的最小流量（因为这是沿这条路径输送牛奶的瓶颈）。FJ 想要最大化路径流量与路径花费之比。保证存在从 $1$ 到 $N$之间的路径。

### 输入格式

输入的第一行包含 $N$ 和 $M$。以下 $M$ 行每行以四个整数描述一条管道：$a$ 和 $b$（管道连接的两个不同的接合点），$c$（管道的花费），以及 $f$（管道的流量）。花费和流量均为范围 $1 \ldots 1000$ 之内的正整数。

### 输出格式

输出 $10^6$ 乘以最优解的值，并向下取整（也就是说，如果这个数本身不是整数，输出小于它的最接近它的整数）。

### 样例 #1

#### 样例输入 #1

```
3 2
2 1 2 4
2 3 5 3
```

#### 样例输出 #1

```
428571
```

### 提示

在这个例子中，仅由一条路径从 $1$ 到 $N$。 它的流量为 $\min(3,4)=3$，花费为 $2+5=7$。

### 数据范围

测试点 $2\sim 5$ 满足 $N,M\le 100$。

对于 $100\%$ 的数据，$2 \leq N \leq 1000$，$1 \leq M \leq 1000$。

供题：Brian Dean

## 题解

### 分析

第一眼看到这个题目，以为是最短路板子，心想这题也能评绿。再一看发现这个最短路有两个评价指标，花费和流量。

设 $M$ 条管道需要花费 $C = \sum c_i$ ，流量 $F = \min(f_i)$ 。那么题目所求也就是 $\frac{C}{F}$ 的最大值，即 $\frac{\sum c_i}{\min(f_i)}$ ，且至少有一条由 $1$ 通往 $n$ 的路径。

不难发现若直接使用最短路枚举两个条件的最优解极其复杂，固考虑枚举流量 $1 \leq f_i \leq 1000$ ，再用 $c_i$ 为边权跑最短路模板，最后取最大值即可。如果当前边所对应的流量 $< f_i$ ，则跳过当前边。因为答案需要保证连通性，所以最后还需要判断能否到达 $n$ 点。

考虑使用 Dijkstra 堆优化为最短路算法，则时间复杂度为 $\Theta(n^2 \times \log n)$ ，极限情况约为 $10^7$ ，可以接受。

其实这道题也可以不用枚举 $1 \leq f_i \leq 100$ ，直接枚举 $M$ 条管道的流量即可，但对最终复杂度的变化不大，~~加上本人鸽子~~ ，就不优化了。

总的来说这道题没啥坑点，只要能想到枚举 $f_i$ 就不难通过，细节地方在代码里注释了。

## 代码

```cpp
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <memory.h>
#include <queue>
using namespace std;
const int N = 1e6 + 10;
const int M = 1e6;
const int INF = 0x3f3f3f3f;

int n, m, ans;
int h[N], idx = 0;
int dis[N], vis[N];

struct Edge {
    int nxt, v, w, f;

    Edge()
    {
        this->nxt = -1, this->v = -1, this->w = INF, this->f = INF;
    }

    Edge(int _nxt, int _v, int _w, int _f)
    {
        this->nxt = _nxt, this->v = _v, this->w = _w, this->f = _f;
    }
} edges[N];

struct Node {
    int dis, vtx;

    Node(int _dis, int _vtx)
    {
        this->dis = _dis, this->vtx = _vtx;
    }

    friend bool operator<(Node x, Node y)
    {
        // 注意这个符号方向，我因为这个卡了好久
        return x.dis > y.dis;
    }
};

priority_queue<Node> q;

// 邻接表存图
void addEdge(int a, int b, int c, int f)
{
    idx++;
    edges[idx].v = b, edges[idx].nxt = h[a], edges[idx].w = c, edges[idx].f = f, h[a] = idx;
}

// Dijkstra 板子
void dijkstra(int u, int lim)
{
    dis[u] = 0;
    q.push(Node(0, u));
    while (!q.empty()) {
        Node cur = q.top();
        q.pop();
        int tmp = cur.vtx;
        if (vis[tmp])
            continue;
        vis[tmp] = 1;
        int p = h[tmp];
        while (p != -1) {
            // 当前管道流量过小，忽略
            if (edges[p].f < lim) {
                // 下面这行也要注意，我一开始没加就死循环了
                p = edges[p].nxt;
                continue;
            }
            if (dis[tmp] + edges[p].w < dis[edges[p].v]) {
                dis[edges[p].v] = dis[tmp] + edges[p].w;
                if (!vis[edges[p].v])
                    q.push(Node(dis[edges[p].v], edges[p].v));
            }
            p = edges[p].nxt;
        }
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c, f;
        cin >> a >> b >> c >> f;
        addEdge(a, b, c, f);
        addEdge(b, a, c, f);
    }
    for (int i = 1; i <= 1000; i++) {
        // 别忘了初始化
        memset(dis, 0x3f, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        dijkstra(1, i);
        if (dis[n] != INF)  // 判断能否到达 n
            ans = max(ans, i * M / dis[n]);
    }
    cout << ans << endl;
    return 0;
}
```

AC++！

[最短路] P5837 Milk Pumping G 题解


## 题目

链接：<http://182.254.140.138:8888/p/621>

### 说明

有四个人，每人身上的衣服分别有s1,s2,s3和s4处破损,而且每处破损程度不同,破损程度用需修好它用的时间表示(A1...As1,B1...Bs2,C1...Cs3,D1...Ds4)。不过你可以同时修补2处破损。但是这2处破损，只能是同一件衣服上的。就是说你只能同时修补一件衣服，修好了，才能修补下一件。

### 输入格式

本题包含5行数据：第1行，为s1,s2,s3,s4(1≤s1,s2,s3,s4≤20) 第2行，为A1...As1 共s1个数，表示第一件衣服上每个破损修好它所需的时间 第3行，为B1...Bs2 共s2个数，表示第二件衣服上每个破损修好它所需的时间 第4行，为C1...Cs3 共s3个数，表示第三件衣服上每个破损修好它所需的时间 第5行，为D1...Ds4 共s4个数，表示第四件衣服上每个破损修好它所需的时间 (1≤A1...As1,B1...Bs2,C1...Cs3,D1...Ds4≤60)

### 输出格式

输出一行,为修好四件衣服所要的最短时间。

### 样例

#### 输入数据 1

```input1
1 2 1 3		
5
4 3
6
2 4 3
```

#### 输出数据 1

```output1
20
```

## 题解

### 分析

一道 DP 题。

> 就是说你只能同时修补一件衣服，修好了，才能修补下一件。

这段话相当于明示了这四件衣服互不相干，可以拆分成四个子问题分别求解。

注意到可以同时修补一件衣服上的两个破洞，所以枚举情况的时候只需要枚举 $\frac{sum}{2}$ 种时间情况即可。

在进行 DP 之前需要先将 $a$ 数组升序排序，这样后面枚举状况的时候就可以直接枚举一大一小两处破损了。

转移方程式：

$$
dp_{i,j} =
\begin{cases}
dp_{i - 1, j}\hspace{5mm}& j < a_i\\
\max(dp_{i - 1, j}, dp_{i - 1, j - a_i} + a_i) & \text{otherwise}
\end{cases}
$$

注意所有的取最值操作都是 $\max$ ，必须取修复两处破损的最大时间为同时修补这两处破损的总时间。

### 代码

```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <map>
#include <set>
using namespace std;
const int N = 1010;

int a[N], dp[N][N], ans, s[5];

int main() {
    for (int i = 1; i <= 4; i++)
        cin >> s[i];

    for (int k = 1; k <= 4; k++) {
        int n = s[k], sum = 0, partialAns = 0;
        memset(dp, 0, sizeof(dp));

        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            sum += a[i];
        }

        sort(a + 1, a + n + 1);

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= sum / 2; j++) {
                dp[i][j] = dp[i - 1][j];

                if (j >= a[i])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + a[i]);

                partialAns = max(partialAns, dp[i][j]);
            }
        }

        ans += max(partialAns, sum - partialAns);
    }

    cout << ans << endl;
    return 0;
}
```

AC++！


[DP] 补圣衣 题解


## 题目

链接：http://182.254.140.138:8888/p/617

### 说明

你现在拿到了许多的礼物，你要把这些礼物放进袋子里。你只有一个最多装下V 体积物品的袋子，你不能全部放进去。你也拿不动那么重的东西。你估计你能拿的最大重量为 G。现在你了解了每一个物品的完美值、重量和体积，你当然想让袋子中装的物品的完美值总和最大，你又得计划一下了。

### 输入格式

第一行：G 和 V 表示最大重量和体积。 第二行：N 表示拿到 N 件礼物。 第三到N+2行：每行3个数 Ti Gi Vi 表示各礼物的完美值、重量和体积

### 输出格式

输出共一个数，表示可能获得的最大完美值。

### 样例

#### 输入数据 1

```input1
6 5		
4		
10 2 2		
20 3 2
40 4 3
30 3 3
```

#### 输出数据 1

```output1
50
```

### 提示

对于20%的数据 N，V，G，Ti，Vi，Gi≤10
对于50%的数据 N，V，G，Ti，Vi，Gi≤100
对于80%的数据 N，V，G，Ti，Vi，Gi≤300
80%到100%的数据是N，V，G，Ti，Vi，Gi≤380 的离散随机数据。

## 题解

### 分析

第一眼看上去像 01 背包问题，但是仔细一看发现有两个条件（ 01 背包只有一个重量限制，这个有重量和体积）。01 背包的基础上多加一维体积就可以了。

$dp_{i,j}$  表示当前装的重量为 $i$ ，体积为 $j$ 。转移方程式如下：


$$
current_G = gifts_k.g, \ current_V = gifts_k.v
$$

$$
dp_{i,j} = \max(dp_{i,j}, dp_{i - current_G,j - current_V} + gifts_k.t)
$$

### 代码

```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <map>
#include <set>
using namespace std;
const int N = 400;

int g, v, n, ans;
int dp[N][N];

struct Gift {
    int t, g, v;
} gifts[N];

int main() {
    cin >> g >> v >> n;

    for (int i = 1; i <= n; i++) {
        cin >> gifts[i].t >> gifts[i].g >> gifts[i].v;
    }

    for (int k = 1; k <= n; k++) {  // 当前礼物
        for (int i = g; i >= gifts[k].g; i--) {  // 当前重量
            for (int j = v; j >= gifts[k].v; j--) {  // 当前体积
                dp[i][j] = max(dp[i][j], dp[i - gifts[k].g][j - gifts[k].v] + gifts[k].t);
            }
        }
    }

    cout << dp[g][v] << endl;
    return 0;
}
```

AC++, rp++!


[DP] 打包 题解




## 题目

链接：<http://182.254.140.138:8888/p/216>

### 题目说明

很多人都曾经听说过数独，但你是否听说过数谜（Karuro）呢？实际上，数谜是数独的更大（且更难）的兄弟问题，而且在日本也是非常受欢迎的。

数谜问题和填字游戏类似，不过它要填的不是文字而是数字。数谜游戏的目标是用 $1 ～\ 9$ 填满所有空格，且这些数字相加的和满足相应的要求（或者称为“提示”），且在同一栏（“栏”是指一些水平或者竖直的连续的空格，用于提示的格子不算空格）不能填重复的数字。当所有格子按要求被填满后，这个数谜就看作被解决了。图 1 和图 2 是一个可能的数谜游戏示例。

![img](https://www.freesion.com/images/558/786845b3b03367143ec7327c0c169bde.JPEG)

当然，直接求解数谜问题的话会比较困难。所以现在我们需要解决的是一个更简单的数谜问题。简单数谜的形状是一个 $(n+1)$ 行乘 $(m+1)$ 列的矩形。而简单数谜也只有两种要求，就是行要求和列要求，且分别处于第一行和第一列，其他格子则是空格，而左上角是忽略不计的。coolzzz 同学爱好简单数谜，他已经给一些简单数谜填好了其中的一些空格。现在，他想寻求你的帮助，来帮他完成这些简单数谜。如图 3 所示，2 和 9 是 coolzzz 同学已经填好的空格，图 4 则是一个基于图 3 的一个可能的解答。

### 输入格式

输入包含多组测试数据。第一行包含一个正整数 $T$ ，表示测试数据数目。每组数据第一行是 $n\ (n< 10)$ 和 $m\ (m< 10)$，表示数谜的形状的大小。接下来一行有 $n$ 个整数，是相应的行要求；然后一行是 $m$ 个整数，是相应的列要求。接下来的 $n$ 行每行有 $m$ 个小于 $10$ 的非负整数，0 表示该空格还没有被填数字，其他表示 coolzzz 同学已经填好的数字。输入数据保证未填数字的空格不会超过 $16$ 个。

### 输出格式

对于每组测试数据，输出若干行。如果基于 coolzzz 已填的结果，该数谜只有一个解，则输出该解；如果不止一个解，则输出一行 `Not unique.`；如果没有解，则输出一行 `No answer.`。

### 样例

#### 输入样例 1

```
3
3 3
6 6 6
6 6 6
0 0 0
0 3 0
0 0 0
2 3
10 17
5 16 6
2 0 0
0 9 0
2 2
3 5
4 4
0 0
0 0
```

#### 输出样例 1

```
Not unique.
2 7 1
3 9 5
No answer.
```

## 题解

### 分析

空着的格子数量 $\leq 16$ ，果断考虑爆搜。基本上就是八皇后的进阶版，注意每个测试样例的初始化和 DFS 的回溯就行。

### 代码

```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <map>
#include <set>
using namespace std;
const int N = 15;

// ans 答案数目，solved 当前解
int n, m, mp[N][N], T, ans, solved[N][N];
// column_sum[i] 第i行的和，row_sum[i] 第i列第和，exists_on_column[i][j] 在第i行是否存在j这个数字，exists_on_row[i][j] 在第i列是否存在j这个数字
int column_sum[N], row_sum[N], exists_on_column[N][N], exists_on_row[N][N];
// column_req 存储行要求，row_req 存储列要求（分别是输入第1、2行）
int column_req[N], row_req[N];

struct Point {
    int x, y;

    Point(int _x, int _y) {
        this -> x = _x, this -> y = _y;
    }
};

void init() {
    ans = n = m = 0;
    memset(mp, 0, sizeof(mp));
    memset(column_req, 0, sizeof(column_req));
    memset(row_req, 0, sizeof(row_req));
    memset(column_sum, 0, sizeof(column_sum));
    memset(row_sum, 0, sizeof(row_sum));
    memset(solved, 0, sizeof(solved));
    memset(exists_on_column, 0, sizeof(exists_on_column));
    memset(exists_on_row, 0, sizeof(exists_on_row));
}

void dfs(Point cur) {
    // 已经有多个解了就没必要继续搜了
    if (ans >= 2)
        return;

    // 搜到头了
    if (cur.x > n) {
        bool is_valid = 1;

        // 检查当前解是否合规 
        for (int i = 1; i <= n; i++) {
            if (column_sum[i] != column_req[i]) {
                is_valid = 0;
                break;
            }
        }

        if (!is_valid)
            return;

        for (int i = 1; i <= m; i++) {
            if (row_sum[i] != row_req[i]) {
                is_valid = 0;
                break;
            }
        }

        if (!is_valid)
            return;

        // 合规
        ans++;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++)
                solved[i][j] = mp[i][j];
        }

        return;
    }

    // 一行一行地搜
    if (cur.y > m) {
        dfs(Point(cur.x + 1, 1));
        return;
    }

    // 当前数字填过了
    if (mp[cur.x][cur.y] != 0) {
        dfs(Point(cur.x, cur.y + 1));
        return;
    }

    // 没填过，现在填
    for (int i = 1; i <= 9; i++) {
        if (!exists_on_column[cur.x][i] && !exists_on_row[cur.y][i] && column_sum[cur.x] + i <= column_req[cur.x] &&
                row_sum[cur.y] + i <= row_req[cur.y]) {  // 当前值是否合法
            exists_on_column[cur.x][i] = 1;
            exists_on_row[cur.y][i] = 1;
            column_sum[cur.x] += i;
            row_sum[cur.y] += i;
            mp[cur.x][cur.y] = i;
            dfs(Point(cur.x, cur.y + 1));
            // 注意回溯
            exists_on_column[cur.x][i] = 0;
            exists_on_row[cur.y][i] = 0;
            column_sum[cur.x] -= i;
            row_sum[cur.y] -= i;
            mp[cur.x][cur.y] = 0;
        }
    }
}

int main() {
    cin >> T;

    while (T--) {
        init();  // 初始化
        cin >> n >> m;

        for (int i = 1; i <= n; i++)
            cin >> column_req[i];

        for (int i = 1; i <= m; i++)
            cin >> row_req[i];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> mp[i][j];
                column_sum[i] += mp[i][j];
                row_sum[j] += mp[i][j];
                exists_on_column[i][mp[i][j]] = 1;
                exists_on_row[j][mp[i][j]] = 1;
            }
        }

        dfs(Point(1, 1));  // 左上角开始搜

        if (ans == 0) {
            cout << "No answer." << endl;
            continue;
        }

        if (ans > 1) {
            cout << "Not unique." << endl;
            continue;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cout << solved[i][j] << " ";
            }

            cout << endl;
        }
    }

    return 0;
}
```

AC++！

简单数迷 题解


So tomorrow is the final exam for the whole semester. I'd like to summarize what I've done and share some personal thoughts here, ignore if you dislike them. I don't like to write those in Chinese because it feels so shame to write those. But I would like to share those to my friends though. So I wrote this in pure English.

## Past

Generally speaking, I made some improvement on math this year but indeed not for Chinese. Apart from the first mid-term exam taken in the first half of the semester (in which I will talk about it later in this article), my Chinese score had fall a lot comparing to primary school. In elementary school I seldomly get a score lower than 90. Honestly. But now it's like hardly above 80.

So let me make a reasonable guess. Maybe I'm not so good in Chinese - and that's for sure but also awful. But middle school is so different than elementary school for me - in elementary school, I can't do anything aside for learning. But in middle school, it's like - you can do whatever you wanted. I tried to retain my own flow of learning in middle school when I first got there, and it turned out to be working great, at least for that period. So I used the same old method of learning in the first half of the semester and got an acceptable score.

When I say the primary school of learning for me, is just paying attention while having a class and finish the homework, not including doing extra exercises. To be honest, **I'm not really used to having extra exercises, because I've never had them before in primary school**. Although I got a good score on Chinese for that time, I didn't get a good score on math.  (92 I guess?) Through the first grade to the fifth grade, I almost get a perfect score on math every time. But from the sixth grade, my math score fell like crazy. For once I got 80 on math in the sixth grade, which hurts me a lot. And I don't understand why - I know how to solve those problems but couldn't give out the correct answer.

The same happens for me in that mid-term exam. For Chinese, I'm like shocked when I see the score. I never knew that I could get that score in middle school because a lot of my former classmates were complaining about it. I think the main reason of getting this is my attitude. I'm taking the exam as normal and didn't even panic - just like in primary school. That may helped me a lot throughout my childhood. Also because I'm a lucky dog.

## Now

Starting from the last half of the semester (after winter holiday), I started to do more exercises. Partly because I felt helpless on every single subject - I didn't know how to get a better score. I tried to do some math exercises and turned out to be very hard at the beginning. But still, I didn't give up. Thanks to my perseverance, I gradually get better and better in math. The reason I know this and think it as a fact is that at first my math score is way below one of my friend's (and maybe she'll never read this article), but now it's me better than her.

But talking about Chinese, I have only a few words to say. I started to hate it. It's making me very stressed and frustrating. Sometimes I even wish that I'm born in an English country instead of China. It's so hard to understand everything and you just couldn't write it **AS IT**. It's like *guessing* what the author wanted to say and *guessing* what the teacher wanted you to write about. I hate Chinese.

## Future

I guess I have a lot to improve in this summer holiday. Maybe less screen time and more time to do math problems (and physics), in order to perform better at school. For Chinese, I think I may need to read more books in the future and do more specific exercises. I'm way far from being a profession in those. Anyway, good luck tomorrow.

But to be honest, my favorite subject is informatics.

Thanks for taking time to read this article.

Thoughts on the Final Exam


Hey guys, it's Sam Zhang.

如果你看过一些开源项目的源码，或深入研究过 Python 基础，就会发现在 Python 中，下划线无处不在。不仅如此，它的形式还五花八门，让人摸不着头脑。

这期视频，我们就来探讨一下 Python 下划线的那些事。

## 双下划线 —— 私有？

让我们先来讲一讲最有趣的双下划线吧。例如，下面这段代码：

```python
class SampleClass(object):
    def __init__(self):
        super().__init__()
        self.__private_method()

    def __private_method(self):
        print("I'm private!")

if __name__ == "__main__":
    obj = SampleClass()  # works!
    # obj.__private_method()  # AttributeError
    print(dir(SampleClass))
    obj._SampleClass__private_method()  # works!
```

定义了一个 SampleClass 类，并在其中定义了一个名叫 `__private_method` 的方法。

你尝试在 SampleClass 中通过 `self.__private_method` 来访问这个方法，一切正常运行。

但是，如果在已经实例化后的 SampleClass 对象中调用该方法，就会报错 AttributeError ，并不存在这样一个方法。

于是，我们可以提出一个合理猜测：双下划线开头的方法就是 Python 里的私有方法。

但是其实不然。原因很简单，如果你用 `dir(SampleClass)` 来查看这个类的所有成员函数的话，就会发现在其中有一个名叫 `_SampleClass__private_method()` 的方法：

```python
['_SampleClass__private_method', '__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__le__', '__lt__', '__module__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__']
```

如果你尝试从外部调用它，就会发现调用的就是之前定义的私有方法。

同样的，如果你定义了一个类继承自 SampleClass ，会发现它无法调用 `__private_method()` 。但是，如果你调用 `self._SampleClass__private_method()` ，就能够正常调用私有方法：

```python
class SampleClass(object):
    def __init__(self):
        super().__init__()
        self.__private_method()

    def __private_method(self):
        print("I'm private!")

class SampleClass2(SampleClass):
    def __init__(self):
        super().__init__()
        # self.__private_method()  # AttributeError
        self._SampleClass__private_method()  # works!

if __name__ == "__main__":
    obj = SampleClass()  # works!
    # obj.__private_method()  # AttributeError
    print(dir(SampleClass))
    obj._SampleClass__private_method()  # works!
    obj2 = SampleClass2()  # works!
```

值得一提的是，Python 中所谓的“私有方法”并不是其他语言中私有方法的概念。

在 Python 中，前置双下划线的标准说法叫做 **名称修饰** ，或 *name mangling* 。解释器会在运行过程中自动将前置双下划线的方法转换为 `_CurrentClassName__method_name` 的形式，且子类无法直接通过 `self.__method_name` 访问父类方法。但是，子类仍然可以通过上面所说的 `self._CurrentClassName__method_name` 访问父类的双下划线方法，其中 CurrentClassName 为父类名称。

所以，Python 中以双下划线开头命名的成员函数，从某种意义上讲只是被解释器替换了名字，并没有真正“私有化”。如果你想要在子类中复写、调用这些经过命名修饰后的方法的话，也是完全可行的。但是，在一般情况下来说，你可能并不想这么干 —— 如果你复写了别人写的内部方法，很可能会导致意料之外的后果。

## 单下划线 —— 只是命名规范？

讲了这么多双下划线，来看看单下划线吧。在 Python 中，单下划线更倾向于一种命名规范，指明当前方法为私有方法，不建议进行改动且随时可能进行 API 更新。它并没有像双下划线那样有着解释器自动的名称修饰，意味着子类仍然可以直接复写或调用单下划线开头的方法。

但是，单下划线与普通方法还是有区别的。如果你在一个文件顶层定义了一个单下划线开头的方法，类或变量，当其他模块使用 `from xxx import *` 这种导入方式导入该文件中的成员的时候，将不会导入单下划线开头的成员。例如：

```python
_radius = 100
PI = 3.14

def _calc():
    return PI * _radius * _radius
```

然后，你在另一个文件中尝试导入这些变量：

```python
from my_file import *

print(PI)  # 3.14
print(_radius)  # NameError
print(_calc())  # NameError
```

你无法通过 `import *` 这个语法糖导入单下划线开头的对象。

也就是说，解释器自动将单下划线开头的对象从模块的 `__all__` 中移除了。但是，如果你手动定义 `__all__` 的话，仍然可以覆盖解释器的默认操作：

```python
# 手动复写 __all__
__all__ = ["PI", "_radius", "_calc"]

_radius = 100
PI = 3.14

def _calc():
    return PI * _radius * _radius
```

再进行导入的话：

```python
from my_file import *

print(PI)  # 3.14
print(_radius)  # 100
print(_calc())  # 31400.0
```

就可以正常运行啦！

## 后缀下划线 —— 规避重名

在 Python 中，你也许还见到过类似 `variable_` 这种命名方法，以单下划线结尾。一个最常见的例子就是 BeautifulSoup 中 `find()` 方法里 `class` 参数的命名被改成了 `class_ `。

这种单下划线后缀的命名方法通常是用来规避与内置关键词重名导致语法错误。常见的还有 `float_` ，`int_` ，`str_` 等。

当然，能不用这种命名方法就不用，尽量规避内置关键词，以免造成代码可读性降低。

## 两侧双下划线 —— 魔法函数

最后，在 Python 的类中还有一种奇特的下划线命名，形式如 `__method__` 。这种双前导双末尾下划线的形式在 Python 中通常为语言内置的魔法方法，例如 `__init__` ，`__add__` 等。

通常来讲，我们不建议将自己写的函数以这种形式命名，以免造成不必要的误解。当然，在需要自定义这些方法的时候，复写还是非常有必要的。

一些常见的魔法方法如 `__init__` ，`__del__` ，`__repr__` ，`__getattr__` 等。如果你想要了解更多魔法函数相关内容，可以去看一看 [这篇文章](https://segmentfault.com/a/1190000040286979) 。

## 写在最后

说了这么多，下划线的作用其实主要就是规范代码命名。这样，当你发布的包被其他人使用时，别人就能很轻松地知道这个方法能不能复写，该不该直接调用等等。

写好 Python 代码，从遵循 PEP8 开始。

那么以上就是本期视频的全部内容了，如果你觉得还不错的话，也请三连转发关注我，这对我创作都会是很大的动力。如果你发现了本期视频中的错误，也欢迎私信或者在评论区中留言，我也会及时改正。

我是 Sam Zhang ，我们下期再见！

## 参考资料

- Aggarwal, N. (2019, November 26). Private Methods in Python. Geeks for Geeks. https://www.geeksforgeeks.org/private-methods-in-python/
- Alya. (2003, September 16). Why are Python's 'private' methods not actually private? - Stack Overflow. Stack Overflow. https://stackoverflow.com/a/70900/13266491
- (2008, December 3). 9. Classes — Python 3.10.5 documentation. Python Documentation. https://docs.python.org/3/tutorial/classes.html#private-variables
- (2021, May 18). Private Methods in Python. DelftStack. https://www.delftstack.com/howto/python/python-private-method/
- Hettinger, R. (2013, March 21). Python's Class Development Toolkit. Next Day Video. https://www.youtube.com/watch?v=HTLu2DFOdTg&t=1988s
- 清风Python. (2020, September 13). 关于Python的前后、单双下划线作用，看完这篇文章吊打面试官. 简书. https://www.jianshu.com/p/f642ab3ec614

你真的会用 Python 里的下划线吗？


## 前言

Rollup 是我在重构 [TNT.js](https://github.com/Bug-Duck/tntjs/tree/dev) 这个玩具框架时忽然发现的一个构建工具。因为需要升级整个 codebase 到 ES Modules ，所以一个好的构建工具十分重要。但是，这个项目之前用的“构建工具”就是把 TypeScript 编译成 JavaScript ，可变性并不强。在尝试使用 Webpack 的时候，我无论如何也没办法让编译产物通过 HTML 的 `script` 标签导入到页面中（这个项目是一个小前端框架，要能够在浏览器中运行，就必须使用 `script` 标签倒入，没有打包 HTML）。

然后在一位大佬的指引下，我发现了 [Rollup.js](https://github.com/rollup/rollup) ，原生支持 ESM ，感觉十分不错。于是，就诞生了这篇文章！

## 安装

```bash
$ npm i -g rollup
```

## 配置 Rollup

跟 Webpack 一样，Rollup 也用一个独立的 JS 配置文件存放自己的运行设置。在 Rollup 里，配置文件的名字是 `rollup.config.js` 。

我在这个项目里使用的配置文件长这样：

```js
import alias from "@rollup/plugin-alias";
import resolve from "@rollup/plugin-node-resolve";
import typescript from "@rollup/plugin-typescript";
import serve from "rollup-plugin-serve";

export default {
  input: "src/index.ts",
  preserveModules: true,
  treeshake: false,
  output: {
    format: "esm",
    sourcemap: true,
    dir: "./dist",
    name: "TNT"
  },
  plugins: [
    alias({
      entries: [
        { find: "runtime", replacement: "src/runtime" },
        { find: "plugins", replacement: "src/plugins" },
      ],
    }),
    resolve(),
    typescript(),
    serve(),
  ],
};
```

Rollup 也支持许多的插件，比如我这里用的 `plugin-alias` ，就是把 Webpack 里面的 `alias` 配置项移植了过来。这里需要注意，Rollup 原生并不支持 TypeScript ，需要单独安装 `@rollup/plugin-typescript` 插件才能使用。

我还是用了 `plugin-node-resolve` ，这个插件是用来解析导入 `node_modules` 中的模块的。最后的 `rollup-plugin-serve` 的作用就是在你运行 Rollup 时，自动启动一个开发服务器，提供预览。

在这里，我选用了 ESM 的打包方式，仅仅为了让我这个项目变得好玩点。`output.dir` 指定了输出目录。还需要注意的是，我关闭了摇树优化，因为我需要把所有的东西整体打包，而不是打包特定的部分。但是这带来的坏处就是需要手动检查导入，防止导入未使用的模块。

`preserveModules` 代表保留当前的所有模块，这样我就可以在构建后的代码中使用 `import` 语句了。

配置完了 Rollup 之后，可以用 `rollup -c` 来打包。当然，这样并不会热更新，你还需要指定 `-w` 参数来启动热更新。

至此，Rollup 已经完成了基本配置。但是，为了更好的开发体验，我还需要一个东西来热加载我的 HTML 文件 —— 但是并不是使用 Rollup（当然 Rollup 也支持导入 HTML ，只不过不符合我的需求）。

## 在 HTML 中使用 ESM 并热加载

在 HTML 里导入 ESM 还是比较简单的。在 `<script></script>` 标签上加入 `type="module"` 就行啦。然后，就可以在 `script` 标签里面使用 `import` 语句了：

```html
<script type="module">
  import TNT from "./dist/src/runtime/TNT.js";
  import { Value } from "./dist/src/plugins/tntjsapi-simp/ValueState.js";
  import { Globals } from "./dist/src/runtime/GlobalEnvironment.js";
  import { NumberType } from "./dist/src/runtime/SymbolTable.js";
  import { PluginMain as TemplatePlugin } from "./dist/src/plugins/TemplateLanguage/PluginMain.js";
  import { PluginMain as DebugPlugin } from "./dist/src/plugins/debug/PluginMain.js";
  import { PluginMain as TNTScriptPlugin } from "./dist/src/plugins/tntscript/PluginMain.js";

  window.onload = () => {
    console.log(Globals.getAllPlugins())
    const t = new TNT();
    new Value("testValue", NumberType).setValue(23333)
    console.log(Globals.symbolTable);
  };
</script>
```

需要注意的是，你不需要提前使用 `<script src="dist/xxx" />` 来加载 ESM 文件。

但是，如果你现在打开配置好的 HTML 文件，会得到一个错误：

```
index.html:1 
        
Access to script at 'file:///Volumes/Data/Develop/Nodejs/tntjs/dist/src/runtime/TNT.js' from origin 'null' has been blocked by CORS policy: Cross origin requests are only supported for protocol schemes: http, data, chrome-extension, edge, https, chrome-untrusted.
```

看来是直接使用文件协议传输不受 ESM 的支持。

解决方法就是启动一个热加载服务器来伺服我们的 HTML 文件。我选用了 [live-server](https://github.com/tapio/live-server) 包来解决这个问题。

首先，安装 live-server ：

```
npm install -g live-server
```

然后，就可以在项目目录里直接运行 `live-server` 启动开发服务器啦！现在到 <http://localhost:8080/> 去看看吧。

## 总结

总的来说，Rollup 是一个非常好的构建工具，它可以让我们在编写代码的时候更加简单，省去繁琐的配置过程。但是，它的社区可能还不如 Webpack 成熟，所以目前来说 Webpack 可能略占上风。

最后放一下我一直提到的小项目的 GitHub 吧：<https://github.com/Bug-Duck/tntjs/tree/dev>

欢迎 star & fork ！


Rollup.js 初体验

Hey guys, I'm Sam Zhang.

**Edit: since a lot of you are commenting about it, I would like to mention one thing though that this "portfolio" is just made for fun and not recommended to use in a real world application if you're really looking for a job.**

Recently I've updated my personal website. Originally I used [LogTure](https://github.com/samzhangjy/logture) as my primary website, but I think it's not "cool" enough.

So I started building a cooler one. After Googling around, I decided to make a terminal-like site similar to [yasfu.net](https://yasfu.net/portfolio/) with Vue 3.

Vue 3 is still new to me though. I mainly work on React projects recently and didn't explore the new features introduced in Vue 3. So this time I decided to give it a try. And after struggling with errors, I finally finished this project.

**Demo: <https://samzhangjy.com/>**

**GitHub: <https://github.com/samzhangjy/VueTerm>**

And of course, feel free to report issues to me!

However there're some downsides about this project. One is that the current bash-like command system has some trouble handling complicated paths. So for example, when you type in `cd ../folder/subfolder` will cause an inner failure of `cd`.

Recursive might be a good way to solve this problem and I'll try to implement it into this project in the near future.

And here is the end of the article. Feel free to play around with my project!

I built a terminal-like portfolio with Vue 3


Hey guys, it's Sam Zhang.

So in the previous post we finished a simple Hello World request using Golang and Gin. Today it's time for us to build something more complex - CRUD with Gin!

## Table of Contents

- [Getting started](#getting-started)
- [Installing GORM](#installing-gorm)
- [Defining database models](#defining-database-models)
- [Connecting to database](#connecting-to-database)
- [RESTful APIs](#restful-apis)
  - [Create](#api-create)
  - [Read](#api-read)
  - [Update](#api-update)
  - [Delete](#api-delete)
- [Conclusion](#conclusion)

## Getting started <a name="getting-started"></a>

**This tutorial is made for developers who have some experience in programming but relatively new to Go/Gin. You might want to learn some common programming concepts if you're a total beginner.**

So to start up, you'll need to have the hello world program finished from our last post. Or of course you could clone it from [GitHub](https://github.com/samzhangjy/go-blog/tree/1533c8d1db504b2c7f44c0919cc5f2bc91269d9b) to continue.

Then let's get started!

CRUD stands for **C**reate, **R**ead, **U**pdate and **D**elete. Those are the four basic operations in the database and we will be implementing it into our Go app today.

When dealing with databases, you could just write some plain old SQL commands and execute directly it using the database drivers. But there's a problem with it: SQL injection attack. So using ORMs is normally a better option. We will be using [GORM](https://gorm.io/docs/index.html) throughout this series just because it's popular and easy to get started with.

## Installing GORM <a name="installing-gorm"></a>

As it described in the [docs](https://gorm.io/docs/index.html), simply use `go get gorm.io/gorm` to install it.

However, GORM needs database drivers in order to connect to databases and do operations. I will be using [Postgres](https://www.postgresql.org/) for now and you can use whatever database you wanted.

**Note: Sqlite is not recommended since it doesn't support some complex operations natively. But for now, you can use it since we don't have the need of complex operations and you can migrate to others in the future.**

So let's install the database driver too:

```bash
$ go get -u gorm.io/driver/postgres  # or other database provider
```

...and GORM is ready to use!

## Defining database models <a name="defining-database-models"></a>

Like other ORMs, GORM defines a table using [*models*](https://gorm.io/docs/models.html).

To define a model, you need to declare a [`struct`](https://go.dev/tour/moretypes/2) containing the information about the table. For example:

```go
type <name> struct {
    <field>  <field_type>
}
```

is the most basic form of defining a struct in Go. I assume that you have some basic knowledge about relational database storage so we won't discuss it very much here.

In order to create a GORM model, we simply need to fill in the information required. If we wanted to store a blog post in the database, then the following fields might be helpful:

- ID (unsigned integer, primary key, auto increment, required)
- Title (string, required)
- Content (string, required)
- Created at (time, defaults to current time)

So let's create a model for blog posts based on the above fields:

```go
// models/post.go
package models

import "time"

type Post struct {
	ID        uint      `json:"id" gorm:"primaryKey"`
	Title     string    `json:"title"`
	Content   string    `json:"content"`
	CreatedAt time.Time `json:"created_at"`
}
```

Okay so let me explain all these.

We defined a GORM model using a struct and declared several fields. Here `uint` is `unsigned int` in other languages and `time.Time` is the datetime format in Golang.

But the backticks after the field type might be a little weird for new Go users. Those strings are called [**tags**](https://towardsdev.com/golang-struct-tags-explained-ccb589dcbb98). They are using [backtick annotation](https://stackoverflow.com/questions/46917331/what-is-the-difference-between-backticks-double-quotes-in-golang?rq=1) to define key-value pairs.

> Struct `tags` are small pieces of metadata attached to fields of a `struct` that provide instructions to other Go code that works with the struct.[^1]

The `json` defines with key should the JSON encoder use when serializing the current field into JSON format. And the `gorm` key will let GORM know some extra information about this field. For example, here we defined `ID` as a primary key for the model.

## Connecting to database <a name="connecting-to-database"></a>

So now we successfully created the database schema, let's connect it to a real database:

```go
// models/setup.go
package models

import (
	"gorm.io/driver/postgres"
	"gorm.io/gorm"
)

var DB *gorm.DB

func ConnectDatabase() {
	dsn := "host=localhost user=postgres dbname=go_blog port=5432 sslmode=disable timezone=Asia/Shanghai"
	database, err := gorm.Open(postgres.Open(dsn), &gorm.Config{})  // change the database provider if necessary

	if err != nil {
		panic("Failed to connect to database!")
	}

	database.AutoMigrate(&Post{})  // register Post model

	DB = database
}
```

In function `ConnectDatabase()`, we first defined our data source name and established the database connection. Here I used the Postgres driver and you might change it to fit your own need.

If there's any problems when connecting to our database, `err` will point to the error. In this case, we will call `panic()` to terminate the whole process. `panic()` is a builtin function that acts similar to `raise` in Python and `throw` in JavaScript.

Then we registered our `Post` model to the database and "exported" the database variable.

Note that `DB` is a global variable that is accessible in every file of package `models`, making operations with database easier without importing everything.

...and then let's call the connection function in our `main.go`:

```go
// main.go
package main

import (
	"samzhangjy/go-blog/models"

	"github.com/gin-gonic/gin"
)

func main() {
	router := gin.Default()

	models.ConnectDatabase()  // new!

	// ...

	router.Run("localhost:8080")
}
```

And now we've finally made a connection to the database. Time to code the request controllers!

## RESTful APIs <a name="restful-apis"></a>

Unlike the first post, we are going to put all of our request logic into a separate folder called `controllers` and import them later in `main.go` to define the routes.

### Create <a name="api-create"></a>

Let's start by adding a `create` method:

```go
// controllers/post.go
package controllers

import (
	"net/http"
	"samzhangjy/go-blog/models"

	"github.com/gin-gonic/gin"
)

type CreatePostInput struct {
	Title   string `json:"title" binding:"required"`
	Content string `json:"content" binding:"required"`
}

func CreatePost(c *gin.Context) {
	var input CreatePostInput
	if err := c.ShouldBindJSON(&input); err != nil {
		c.AbortWithStatusJSON(http.StatusBadRequest, gin.H{"error": err.Error()})
		return
	}

	post := models.Post{Title: input.Title, Content: input.Content}
	models.DB.Create(&post)

	c.JSON(http.StatusOK, gin.H{"data": post})
}
```

You might be wondering, why is there `struct` again? Well structs is an important concept in Go and you will see it a lot throughout this series. In this case, our struct `CreateBlogInput` defines body schema for request `CreateBlog`. The new tag `binding` is a Gin validation tag based on [Validator](https://github.com/go-playground/validator). If you wanted to know something about Gin bindings, here's a great read: <https://blog.logrocket.com/gin-binding-in-go-a-tutorial-with-example>.

Then let's focus on `CreateBlog()`. We first validated the request body (variable `input` here) using `context.ShouldBindJSON()`. If the body is invalid, `err` would contain some error messages. If `err` contains something, then we will simply return a 400 HTTP status code and abort the request. This `if err = statement; err != nil {}` statement is a commonly used [error handling technique](https://go.dev/blog/error-handling-and-go#simplifying-repetitive-error-handling) in Go.

If the input is valid, we will first create a `Post` model with data given from the input. Then we will call `database.Create()` to put this record into the Post table.

Finally, we will return HTTP 200 with the newly created post schema if everything goes as expected.

And let's bind our controller to a route:

```go
// main.go
package main

import (
	"samzhangjy/go-blog/controllers"
	"samzhangjy/go-blog/models"

	"github.com/gin-gonic/gin"
)

func main() {
	router := gin.Default()

	models.ConnectDatabase()

	router.POST("/posts", controllers.CreatePost)  // here!

	router.Run("localhost:8080")
}
```

Notice that we're passing the controller function **itself** to `router.POST()`, without parentheses.

Run your app with `air` and use tools like Postman to play around with this endpoint!

### Read <a name="api-read"></a>

Then let's quickly add an endpoint to view every post created:

```go
// controllers/post.go

// ...

func FindPosts(c *gin.Context) {
	var posts []models.Post
	models.DB.Find(&posts)

	c.JSON(http.StatusOK, gin.H{"data": posts})
}
```

Unlike the previous request, this one has no request body. We defined array `posts` to store the posts created with type `models.Post`. `DB.Find(&posts)` means to find every entry that exists in the database and store the fetched result to `posts`. Remember to pass in the **pointer** instead of the actual variable!

And then quickly bind it to our router:

```go
// main.go
package main

import (
	"samzhangjy/go-blog/controllers"
	"samzhangjy/go-blog/models"

	"github.com/gin-gonic/gin"
)

func main() {
	router := gin.Default()

	models.ConnectDatabase()

	router.POST("/posts", controllers.CreatePost)
	router.GET("/posts", controllers.FindPosts)

	router.Run("localhost:8080")
}
```

And now you could see the posts you created using `CreateBlog`!

Then let's create a route that fetches only one specified post by URL param:

```go
// controllers/post.go

// ...

func FindPost(c *gin.Context) {
	var post models.Post

	if err := models.DB.Where("id = ?", c.Param("id")).First(&post).Error; err != nil {
		c.AbortWithStatusJSON(http.StatusNotFound, gin.H{"error": err.Error()})
		return
	}

	c.JSON(http.StatusOK, gin.H{"data": post})
}
```

The new methods here is `DB.Where` and `DB.First`. `DB.Where()` lets you write SQL query commands, replacing the dynamic data with `?` and passing the actual data as the second argument. `DB.First(&post)`, like its name, selects the first name of the given collection of data and stores the result inside `post`.

`context.Param("<param-name>")` is a Gin method to fetch the URL parameter by param name. The param name is defined like:

```go
// main.go
package main

import (
	"samzhangjy/go-blog/controllers"
	"samzhangjy/go-blog/models"

	"github.com/gin-gonic/gin"
)

func main() {
	router := gin.Default()

	models.ConnectDatabase()

	router.POST("/posts", controllers.CreatePost)
	router.GET("/posts", controllers.FindPosts)
	router.GET("/posts/:id", controllers.FindPost)  // here!

	router.Run("localhost:8080")
}
```

The slug starting with a colon `:` is defined as `url parameters` in Gin. The string after the colon is the parameter's name, which we'll use to fetch the param value.

A route `/posts/:id` will match the following:

- `/posts/1`
- `/posts/1/`

But won't match:

- `/posts/1/abcd`
- `/posts/`

### Update <a name="api-update"></a>

Then it's time for updating posts:

```go
// controllers/post.go

// ...

type UpdatePostInput struct {
	Title   string `json:"title"`
	Content string `json:"content"`
}

func UpdatePost(c *gin.Context) {
	var post models.Post
	if err := models.DB.Where("id = ?", c.Param("id")).First(&post).Error; err != nil {
		c.AbortWithStatusJSON(http.StatusNotFound, gin.H{"error": "record not found"})
		return
	}

	var input UpdatePostInput

	if err := c.ShouldBindJSON(&input); err != nil {
		c.AbortWithStatusJSON(http.StatusBadRequest, gin.H{"error": err.Error()})
		return
	}

	updatedPost := models.Post{Title: input.Title, Content: input.Content}

	models.DB.Model(&post).Updates(&updatedPost)
	c.JSON(http.StatusOK, gin.H{"data": post})
}
```

So we defined a struct containing request body schema again, but this time without any validation, since everything is optional. We copied the code to validate if the current post exists from the previous `FindPost()` method.

And if the post exists and the request body is valid, we will define a new model containing the contents of the newly generated post data. In this case, its name is `updatedPost`. Then we will fetch the model for the original post using `DB.Model(&post)` and update is using `model.Updates(&updatedPost)`.

`model.Updates()` will update multiple fields and won't modify the fields that didn't defined in the updated schema (`updatedPost`). `model.Update()` will only update one field at a time.

And bind it to the router:

```go
// main.go
package main

import (
	"samzhangjy/go-blog/controllers"
	"samzhangjy/go-blog/models"

	"github.com/gin-gonic/gin"
)

func main() {
	router := gin.Default()

	models.ConnectDatabase()

	router.POST("/posts", controllers.CreatePost)
	router.GET("/posts", controllers.FindPosts)
	router.GET("/posts/:id", controllers.FindPost)
	router.PATCH("/posts/:id", controllers.UpdatePost)

	router.Run("localhost:8080")
}
```

### Delete <a name="api-delete"></a>

And finally here comes the `DELETE` operation at last:

```go
// controllers/post.go

// ...

func DeletePost(c *gin.Context) {
	var post models.Post
	if err := models.DB.Where("id = ?", c.Param("id")).First(&post).Error; err != nil {
		c.AbortWithStatusJSON(http.StatusNotFound, gin.H{"error": "record not found"})
		return
	}

	models.DB.Delete(&post)
	c.JSON(http.StatusOK, gin.H{"data": "success"})
}
```

And we need to ensure that the currently given post ID is valid. Then we will call `DB.Delete(&post)` to delete the `post` entry from our database.

Then finally, bind it to our router:

```go
// main.go
package main

import (
	"samzhangjy/go-blog/controllers"
	"samzhangjy/go-blog/models"

	"github.com/gin-gonic/gin"
)

func main() {
	router := gin.Default()

	models.ConnectDatabase()

	router.POST("/posts", controllers.CreatePost)
	router.GET("/posts", controllers.FindPosts)
	router.GET("/posts/:id", controllers.FindPost)
	router.PATCH("/posts/:id", controllers.UpdatePost)
	router.DELETE("/posts/:id", controllers.DeletePost)

	router.Run("localhost:8080")
}
```

Congrats! You've successfully built a collection of simple but working CRUD restful API routes! Play it around and try to modify some parts or add some new operations!

## Conclusion <a name="conclusion"></a>

This is Part 2 of my learning Go web development. I actually learned a lot from writing this series and if there's any mistakes in the post, plz point them out!

I uploaded all the source code used in this post to [GitHub](https://github.com/samzhangjy/go-blog/tree/efc3ca87db71b3c954e894534aa4893b5fec8353). Feel free to clone it and play around with it!

I'm Sam Zhang and I'll see you guys next time!

[^1]: From [[Golang] Struct Tags explained](https://towardsdev.com/golang-struct-tags-explained-ccb589dcbb98).

Restful CRUD with Golang for beginners


Hey guys, I'm Sam Zhang.

Today I wanted to explore the field of backend development - so I chose Go. The main reason I chose Go instead of other languages (such as Java), is because Go is kinda a new language (at least in my opinion) .

And sadly, I have absolutely no experience in Go development before. So I started this series of blog in order to keep track on myself. I will try to "record" what I've done and write some main concepts in my posts.

Of course, because I'm still a beginner (or newbie?) in Go, so there might be some incorrect stuff here. If so, please leave me a comment to help me improve!

Then let's get started!

## Installing Go

Unlike many other languages, installing Go is quite simple, at least for me.

Go ahead and download the official installer at the [Go download page](https://go.dev/dl). Run it, then you're all set!

Go comes with its command line tool `go` by default. It includes a set of commands such as `run`, `get`, `mod`, etc. For sure, I'm going to use those command a lot in this series. Check out the full list of commands [here](https://pkg.go.dev/cmd/go).

## Installing Gin

I Googled about which Go web framework is the best for beginners, but turned out to be not that helpful. However, a lot of them mentioned [**Gin**](https://gin-gonic.com/) and has almost 60k stars on [GitHub](https://github.com/gin-gonic/gin). So I chose Gin as my framework to get started.

Create a new folder to contain your project and follow the [instructions](https://gin-gonic.com/docs/quickstart/#installation) of installation.

### Troubleshooting

If you're a total beginner like me, you might be facing the following problem when running `go get`:

```bash
$ go get -u github.com/gin-gonic/gin
go: go.mod file not found in current directory or any parent directory.
        'go get' is no longer supported outside a module.
        To build and install a command, use 'go install' with a version,
        like 'go install example.com/cmd@latest'
        For more information, see https://golang.org/doc/go-get-install-deprecation
        or run 'go help get' or 'go help install'.
```

This means that you don't have a module created in the current folder. `go mod` is a command for managing Go modules. We'll use `go mod init` command to generate a new module.

The `go mod init` command accepts one argument, *module-path* . I'm not so sure about this argument right now and I understand it like the name of the module. The format of *module-path* should be as follows:

```
lorem/ipsum/dor
```

Then run `go mod init <module-path>` , replacing `<module-path>` with your own module path. After that, you should be able to install `gin-gonic` correctly.

## Writing the first Gin request

So now we're all set with environments. Let's write a simple "Hello World" request in Go.

Create a new file named `main.go` in the root folder and fill in the following code:

```go
package main

import (
	"net/http"

	"github.com/gin-gonic/gin"
)

func main() {
	router := gin.Default()  // router with default middleware installed
	// index route
	router.GET("/", func(c *gin.Context) {
		c.JSON(http.StatusOK, gin.H{
			"message": "Hello World",
		})
	})
	// run the server
	router.Run()
}
```

Then run `go run main.go` and open up <http://localhost:8080> . Hopefully a Hello World will come up all right:

```json
{
    "message": "Hello World"
}
```

### Understanding the Hello World code

So... what the hell is going on here? Let's take a look at our code.

We've declared package `main` and imported some useful packages to our code. I'll try my best to explain code in `main()` function line by line.

So on line 10 we've declared a variable called `router`. `gin.Default` returns a router with default middleware (stuff like Logger and Recovery middleware) attached. You might be wondering, what in the world is `:=` ? Well, it's similar to `=` in other programming languages. In Golang, a single `=` means **assignment** and `:=` means **declare and assignment**. E.g:

```go
var router = gin.Default()
```

Is equivalent to:

```go
router := gin.Default()
```

The `:=` operator is called [**Short variable declarations**](https://go.dev/ref/spec#Short_variable_declarations). More information see [this StackOverflow question](https://stackoverflow.com/questions/17891226/difference-between-and-operators-in-go).

On line 12 ~ 16, we defined a GET request mapping to `/` and returns a JSON response. `router.GET()`, of course, defines a GET request. Its second argument accepts a callable function whereas that function will receive an argument with type `gin.Context`.

The context variable is named `c` in this case. `*gin.Context` is a pointer to the `gin.Context` value. The contexts in Gin provides a lot of features such as middleware and responses. For Chinese readers, you can take a look at [this article](https://www.topgoer.com/gin%E6%A1%86%E6%9E%B6/gin%E6%BA%90%E7%A0%81%E8%A7%A3%E8%AF%BB/gin%E7%89%9B%E9%80%BC%E7%9A%84context.html) for a more in-depth view of `gin.Context`.

On line 13 we called `c.JSON()` to response this request with content whose MIME type is `application/json`. `http.StatusOK` is a constant variable for the HTTP status code `200 success`, which is from the builtin package `net/http`.

`gin.H` is a short-handed version of defining type for JSON data. If you'd like to nest JSON objects inside JSON objects, you can write something like:

```go
gin.H{
    "some-data": gin.H{
        "message": "success"
    }
}
```

And finally on line 18, we run the server on the default port 8080.

### Live reloading

Now if you wanted to change the content of your Go application, you need to restart the development server every time you change something in order to test the newly added code.

So some web frameworks (such as Python Flask) has a builtin hot reloader for the development server. Unfortunately, Gin doesn't come with that. I chose to use [air](https://github.com/cosmtrek/air) as my auto reloader and of course you can use others.

Setting up Air is quite simple. Run the following command to install it:

```bash
curl -sSfL https://raw.githubusercontent.com/cosmtrek/air/master/install.sh | sh -s -- -b $(go env GOPATH)/bin
```

This will install Air to your `$GOPATH`, which is default to `~/go` . Then append it to your `$PATH` by adding the following line to your `.bashrc` (or `.zshrc`):

```bash
export PATH=$PATH:$(go env GOPATH)/bin
```

...and you're all set! Run `air init` to generate a default Air configuration.

Using Air is even simpler. Just run `air` in your command line and Air run `main.go` in the current folder and will automatically watch for changes in your source code.

> Tip for macOS users: if you don't want to see the annoying popup every time Air reloads your code, simply replace

```go
router.Run()
```

with

```go
router.Run("localhost:8080")
```

## Conclusion

So... I finally finished the Gin hello world! I put all my source code to [GitHub](https://github.com/samzhangjy/go-blog) and hopefully I will be updating it. Clone it if you found something useful or just to play around!

I'm Sam Zhang and I'll see ya next time!

Learning Go Web Development From Zero


此为我在 B 站上发布的视频 [你真的会写 Git 提交信息吗?](https://www.bilibili.com/video/BV1NU4y1U7KT) 的文字稿。

<iframe src="//player.bilibili.com/player.html?aid=684168548&bvid=BV1NU4y1U7KT&cid=724729363&page=1" scrolling="no" border="0" frameborder="no" framespacing="0" allowfullscreen="true"> </iframe>

## 前言

Git - 相信大家对这个工具都不陌生。作为当今最为流行的开源版本控制系统，Git 几乎是每个项目的必备工具。

Git 最主要的功能就是记录版本差异，每一次的版本更新被称作 `commit` 。每一个 `commit` 都有自己的一串 commit id 和描述此次更新内容的 commit message 。而其中对于浏览项目历史记录最重要的一项当然就是 commit message 了。写好，写清楚 commit message ，将会极大的提高合作开发效率。这期视频，我们就来深入研究 commit message 这个字符串，到底该怎么写。

## `git commit`

当你兴高采烈地重构好了你的开源项目的时候，你在终端里敲下了 `git commit` 。Git 自动打开了你最喜欢的编辑器 —— Vim。你在 Vim 中写下了：

> Refactored frontend code and updated `config` format.

随后，你按下 `esc` ，输入 `:wq` 退出了 Vim。终于，你把此次更新上传到了 GitHub 。

但是，你写的这句 commit message ，真的规范吗？

从某种意义上来讲，你写的还不错 —— 很清楚地表述了此次更新的主要内容。但是，却又不够好 —— 你并没有一套明确的规则规定如何表述每一次的 commit message ，导致你的 commit history 变得混乱不堪。

更有些时候，因为着急，你只写了一个 `fix` 就 commit 了 —— 这是不可取的。如果你之后想要知道到底你修复了哪里，还需要 checkout 那个 commit 并逐个翻阅修改的文件。

如果你是刚刚情境中的“我”，那么请继续往下看，相信你会收获很多。

## Conventional Commits

没错，前面所说的那个“规则”已经出现了，并且非常成熟 —— 大部分开源项目都会遵守这个 commit message rule 。而它，就是 Conventional Commits（约定式提交） ，一个人和机器都能读懂的 commit message 规范。

它的大致写法长这样：

```
<类型>[可选 范围]: <描述>

[可选 正文]

[可选 脚注]
```

其中，提交类型可以是下面的几种：

- `fix` ：修复了某个 bug
- `feat` ：新增了某个功能
- `build` ：一些影响构建系统的更新
- `chore` ：一些不重要的、不更改核心代码的更新
- `ci` ：变更了一些 CI 系统的配置
- `docs` ：对文档做出了一些修改
- `test` ：新增或修改测试文件
- `refactor` ：重构了代码（没有新增或修复任何东西）
- ……等等

更完整的提交类型列表请前往 <https://github.com/pvdlg/conventional-changelog-metahub#commit-types> 查看。

在类型后面的范围是可选的，指定了当前变更所作用的域，一般使用括号紧跟在提交类型的后面，例如：

```
build(npm): commit description
```

随后的提交描述是一小段对代码变更的简短总结，紧跟在类型（或作用范围）的后面，使用冒号 + 空格分割。

下面的提交正文也是可选的，可以写一些较长的上下文信息，与描述用一个空行隔开。紧接着的脚注用一个空行与正文分隔开来，包含着一些额外的令牌（例如 `Co-authored-by: user1, user2` 表示此提交是由提交者， `user1` 和 `user2` 共同修改的。

有一个特殊的脚注是 `BREAKING CHANGE` ，表示破坏性变更，必须使用**全部**大写的字母，后面跟着一串描述破坏性更新的文本，例如：

```
BREAKING CHANGE: environment variables now take precedence over config files
```

至此，我们一开始的提交：

```
Refactored frontend code and updated `config` format.
```

就可以变为：

```
refactor(frontend): improved structure of frontend code

Improved code quality of frontend code and removed unused imports.

BREAKING CHANGE: Format of the configuration file now changed to JSON instead of JavaScript files.
```

怎么样，是不是明了了很多？

当然，上面介绍的还只是约定式提交的冰山一角。如果你想要了解更多有关约定式提交的内容，可以去官方文档看一看：<https://www.conventionalcommits.org/zh-hans/v1.0.0/> 。视频中所有提到的链接我也都会放到视频底部的简介中。

ok，那么以上就是本期视频的全部内容了。如果你喜欢的话，不妨来个三连+关注支持一下，这对我创作都会是很大的动力。我是 Sam Zhang，我们下期再见。Bye bye！

你真的会写 Git 提交信息吗?


Hi，欢迎来到 Sam Zhang 的小站！我是 Sam Zhang ，一个喜欢编程的初中生。

我热爱开源，目前也独立制作了一些小的 side-project ，欢迎到[我的 GitHub](https://github.com/samzhangjy)上面查看！

## 技术栈

鄙人不才，目前只会一点前端和 Python 脚本。我主要的技术栈是：

- JS / TS
- Vue
- React
- Nextjs
- Python
- 爬虫 / 数据分析

因为参加算法竞赛（CSP），所以也会使用 C++ 和 C ，但相比较而言在语法上不如 JavaScript 和 Python 熟练。

目前我在学习一些新的技术，例如 Nestjs 。我也会一些最基础的算法，比如搜索、基础图论等。但是，在图论方面我认为我还有很大的进步空间。

最开始提到我做的一些小项目，在这里举几个例子吧：

- [BaiduSpider](https://github.com/BaiduSpider/BaiduSpider) ：一个开源百度爬虫，最初是由我本人维护，目前已经移交给其他开发成员。
- [LogTure](https://github.com/samzhangjy/logture) ：一个基于 Next.js 的静态博客框架，SEO 友好。你现在所看到的博客就是用它搭建的！
- [VueBlogger](https://github.com/samzhangjy/VueBlogger) ：一个基于 Vue.js 的静态博客框架，最初是用于我在 [DEV](https://dev.to/samzhangjy) 上的教程示例代码 ，后来不再更新教程转为开源项目。

剩余的项目真的有点拿不出手…… 就先列这些吧。

## 自媒体

除了在我自己的博客发布内容，我也喜欢在下面这些平台发视频 / 文章：

- [知乎](https://www.zhihu.com/people/samzhangjy)
- [Bilibili](https://space.bilibili.com/522408191?spm_id_from=333.788.0.0)
- [掘金](https://juejin.cn/user/3940246036417406)
- [DEV](https://dev.to/samzhangjy)

## 联系我

- Email：[samzhangjy@outlook.com](mailto:samzhangjy@outlook.com)
- GitHub：<https://github.com/samzhangjy>
- Twitter：<https://twitter.com/samzhangjy>
- QQ：2947602769

欢迎找我来玩！


欢迎来到我的小站


此为我在 B 站上发布的视频 [TCP | 你真的懂 HTTP 吗？](https://www.bilibili.com/video/BV1RU4y1R7Kv) 的文字稿。

<iframe src="//player.bilibili.com/player.html?aid=682385745&bvid=BV1RU4y1R7Kv&cid=554442259&page=1" scrolling="no" border="0" frameborder="no" framespacing="0" allowfullscreen="true"> </iframe>

## 前言

Hello 大家好，我是 Sam Zhang。

HTTP 相信是每个 Web 开发者都耳熟能详的名词了。但是，新手开发者想要完全理解 HTTP 协议却需要时间。这期视频，我就来带大家入门 HTTP 协议。

话不多说，我们直接进入正题！

## TCP / IP 模型

在真正讲解 HTTP 协议之前，我们先来看一下更为底层的 TCP / IP 模型。

### TCP / IP 模型的四个层次

![TCP / IP 模型](https://tva1.sinaimg.cn/large/e6c9d24ely1h09fe7w3qaj208x08xt90.jpg)

正如大家所看到的，TCP / IP 模型分为四层，由下到上依次是：

1. 链路层（Link Layer）
2. 网络层（Internet Layer）
3. 传输层（Transport Layer）
4. 应用层（Application Layer）

#### 链路层

链路层处于 TCP / IP 模型的最底层。它负责管理数据如何与物理媒介进行交互，例如 Wi-Fi 定义了数据如何进行无线传输。

#### 网络层

链路层只能在局域网中工作，而网络层定义了 IP 协议，主要负责寻址操作。

#### 传输层

传输层主要负责提供应用程序接口，为应用程序提供接入网络的途径。除此以外，这一层还出现了端口，也就是客户端与服务器连接的频道。

最主要的是，这一层有可靠传输的 TCP 协议。通过 TCP 协议传输的数据都能保证按照顺序抵达，内容正确且没有重复。大多数网络请求都是通过 TCP 传输的。

#### 应用层

这一层包括了主要为应用软件使用的协议，例如负责文件传输的 FTP 协议，负责电子邮件的 SMTP 协议和负责域名系统的 DNS 等。最经常出现的 HTTP / HTTPS 协议也是在这一层下的，在浏览器中使用非常广泛。WebSocket 协议也同属于这一层。

## HTTP / HTTPS 协议

### 基础概念

![A Web document is the composition of different resources](https://mdn.mozillademos.org/files/13677/Fetching_a_page.png)

> HTTP（**HyperText Transfer Protocol**）是万维网（World Wide Web）的基础协议。自 Tim Berners-Lee 博士和他的团队在1989-1991年间创造出它以来，HTTP已经发生了太多的变化，在保持协议简单性的同时，不断扩展其灵活性。如今，HTTP已经从一个只在实验室之间交换文件的早期协议进化到了可以传输图片，高分辨率视频和3D效果的现代复杂互联网协议。

HTTP 从 HTTP / 0.9 的单行协议演变到现在 HTTP / 2 的数据帧，HTTP 协议在不断地变化并发展着。这个最初从 CERN 实验室中走出来的小东西，最终被几乎所有人每天每刻地使用着。这，就是我们今天的主角 —— HTTP 协议。

HTTP 是一个 client-server 协议。也就是说，请求由客户端发出，被服务器处理后返回一个响应。在这之间，可能存在着许多代理 - 例如网关。这些代理是建立在应用层上的。代理的作用包括缓存，过滤，负载均衡等功能。

### HTTP 设计理念

#### HTTP 是简单的

HTTP 的设计理念是简单易读 —— 这就使得 HTTP 报文能被人类读懂，而不只是机器。

#### HTTP 是可扩展的

请求头的存在使得扩展 HTTP 变得更简单了。只要服务端和客户端对某一个 header 达成一致的语义，那么这个新 header 的功能就可以很轻松被接入进来。

#### HTTP 是无状态，有会话的

HTTP 本身是无状态的。即使在同一连接中，两个请求之间也是没有关系的。但是，通过 Cookies 创建一个会话，就能够让请求共享同样的上下文信息。

也就是说，HTTP 本身是无状态的，但因为 Cookies ，你可以在 HTTP 中创建有状态的会话。

#### HTTP 和连接

HTTP 在底层使用 TCP 传输协议，而不是 UDP 协议 —— 因为 TCP 是可靠的，不丢失消息的。

#### 数据 URL

数据 URL 是一种特殊的 URL 。他使用 `data:` 协议，允许嵌入小文件。

它的定义形式如下：

```
data:[<mediatype>][;base64],<data>
```

其中 `mediatype` 是一个 MIME 类型的字符串，用于判断数据的类型。默认为 `text/plain;charset=US-ASCII` ，即 ASCII 编码的纯文本文档。

除此以外，你还可以选择使用 `base64` 编码来存储数据。这在存储二进制文件（例如视频和图片）时非常有用。加入 `;base64` 标识符即可存储 base64 数据。

例如，`data:,Hello%20World!` 就是一个纯文本类型数据，而 ``data:text/plain;base64,SGVsbG8sIFdvcmxkIQ%3D%3D`` 则是刚刚 Hello World 的 `base64` 形式。

除此以外，还有几点注意事项：

1. 虽然 Firefox 支持无限长度的 `data` URLs，但是标准中并没有规定浏览器必须支持任意长度的 `data`URIs。比如，Opera 11浏览器限制 URLs 最长为 65535 个字符，这意味着 data URLs 最长为 65529 个字符。
2. 因为数据 URL 是没有结束标记的，所以如果你尝试使用 Query String 添加查询字符串会导致浏览器认为加入的查询字符串也是数据的一部分。
3. data URL 的格式虽然很简单，但 `<data>` 前面的逗号 `,` 却很容易被人忽略，从而导致错误。

#### MIME 类型

MIME（**Multipurpose Internet Mail Extensions**）类型，又称媒体类型，用来表示特定数据的性质和格式。

一个 MIME 类型的结构很简单：

```
type/subtype
```

其中 `type` 代表类别，`subtype` 代表子类别。注意，MIME 类型中不允许空格存在。

虽然 MIME 类型不区分大小写，但传统写法都是小写。

常见的类型有 `text` , `image` , `audio` , `video` , `application` 等。每个类别下还有不同的子类别，可谓种类繁多，绝对能找到你想要的。

刚才说的那几个类型都是**独立**类型，还有另外一种 Multipart 类型。它通常在 HTML 表单中出现，类型是 `multipart/form-data` 。

更详细的 MIME 类型表可以在 [MDN](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Basics_of_HTTP/MIME_types) 中找到。

### 请求

一个典型的 HTTP 请求应该包括以下几个部分：

1. 请求行
2. 请求头
3. 请求体，如果有的话

#### 请求行

HTTP 请求的启始行叫做请求行。它由下面几个部分组成：

```
<命令> <路径> <版本>
```

例如：`GET /user/register.html HTTP/1.1`

1. `<命令>` ：是 HTTP 请求方式的其中之一，常见的有 `GET` 、`POST` 、`PUT` 等。
2. `<路径>` ：要获取的资源等路径，通常是上下文中就很明显的元素资源的 URL 。*需要注意的是，它没有 `protocol`（`https://`），`domain`（`samzhangjy.github.io`），抑或是 TCP 协议的 `port`（`80`）。*
3. `<版本>` ：HTTP 协议版本号。

#### 请求头

请求头是一行不区分大小写的字符串。它遵循如下规范：

```
<请求头名称>: <请求头值>
```

举个栗子：

```
Accept-Language: zh-CN, en-US
```

这个 header 表示客户端接受简体中文和英文。HTTP 协议支持许多不同的请求头，大致分类有：

- [General headers](https://developer.mozilla.org/zh-CN/docs/Glossary/General_header)：同时适用于请求和响应消息，但与最终消息主体中传输的数据无关的消息头。
- [Request headers](https://developer.mozilla.org/zh-CN/docs/Glossary/Request_header)：包含更多有关要获取的资源或客户端本身信息的消息头。
- [Response headers](https://developer.mozilla.org/zh-CN/docs/Glossary/Response_header)：包含有关响应的补充信息，如其位置或服务器本身（名称和版本等）的消息头。
- [Entity headers](https://developer.mozilla.org/zh-CN/docs/Glossary/Entity_header)：包含有关实体主体的更多信息，比如主体长度 (Content-Length) 或其 MIME 类型。

完整的列表可在 [MDN](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Headers) 查看。

#### 请求体

不是所有的请求都必须有请求体：获取数据的请求，例如 `GET` , `HEAD` , `DELETE` , `OPTIONS` 等，通常都不需要请求体。某些请求可能需要上传数据到服务器（最典型的例子就是 `POST` 请求），就需要有请求体来装载数据，例如 `FormData` 。

请求体可以大致分为两种：

- Single-resource bodies，由一个单文件组成。该类型的请求体由两个 header 定义：`Content-Type` 和 `Content-Length` 。
- Multiple-resouce bodies，由多部分 body 组成，每一部分包含不同的信息位，通常和 HTML 表单数据结合在一起。

### 响应

HTTP 响应，跟 HTTP 请求一样，分为三个部分：状态行，响应头和响应体。

#### 状态行

HTTP 响应的第一行就是状态行（status line）。它的模式是：

```
<版本> <状态码> <状态文本>
```

例如：`HTTP/1.1 200 OK` 。

1. `<版本>` ：协议版本，通常情况下是 `HTTP/1.1` 。
2. `<状态码>` ：表明请求的状态，成功还是失败等。常见的有 200 ，404 ，403 等。
3. `<状态文本>` ：一条描述当前状态码的简短明确的文本。

#### 响应头

跟 HTTP 请求头的格式完全一样，HTTP 响应头也不区分大小写并使用逗号和冒号分割数据。整个 header（包括其值）表现为单行形式。

有许多响应头可用，这些响应头可以分为几组：

- *General headers*，例如 [`Via`](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Headers/Via)，适用于整个报文。
- *Response headers*，例如 [`Vary`](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Headers/Vary) 和 [`Accept-Ranges`](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Headers/Accept-Ranges)，提供其它不符合状态行的关于服务器的信息。
- *Entity headers*，例如 [`Content-Length`](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Headers/Content-Length)，适用于请求的 body。显然，如果请求中没有任何 body，则不会发送这样的头文件。

更多响应头可以在 [MDN](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Headers) 找到。

#### 响应体

响应体是可选的，例如有着 HTTP 状态码 201 或 204 的请求大多数情况下不会有响应体。

常用的 Single-resource bodies 响应体可分为两类：

- 由已知长度的单个文件构成的，由 `Content-Type` 和 `Content-Length` 响应头定义。
- 由未知长度的单个文件构成的，通过将 `Transfer-Encoding` 设为 `chunked` 来使用 chunks 编码传输。

属此以外，还有 Multiple-resource bodies ，由多部分响应体组成，每部分包含不同的信息段，但十分少见。

### HTTP / 2

HTTP / 2 修复了 HTTP / 1.1 的许多性能问题：例如在 HTTP / 2 中，可以压缩 header 了。如果你想用 HTTP / 2 协议，你完全不需要更改你的任何 API - 当用户的浏览器和你的服务器都支持 HTTP / 2 时，它会自动取代 HTTP / 1.1 。

如果你想要了解 HTTP / 2 的具体优化，请参考 [MDN](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Messages#http2_帧) 。

### 认证

![img](https://tva1.sinaimg.cn/large/e6c9d24ely1h0anyizllbj20jq09b3yw.jpg)

一个初始 HTTP 请求是不包括任何认证信息的，可以被认为是一个匿名请求。当服务器接收到此请求且客户端要访问的路由是受保护的，服务器就会返回 401 状态码，并使用 `WWW-Authenticate` 响应头告知客户端需要进行相应的认证。下面是它的语法形式：

```
WWW-Authenticate: <type> realm=<realm>
```

其中，`<type>` 表示验证方案（例如 `Basic` ）。`<realm>` 是一段用于描述进行保护区域的文字，例如 Access to the staging site ，使用户能够知晓他们正在访问的空间。

这时，当客户端（浏览器）接收到此消息后，会弹出密码框，让用户输入密码。输入完成后，客户端将所获的认证信息通过 `Authorization` 请求头传回服务器。

服务器验证当前认证信息后，会根据实际情况返回数据。

一个最基础的 HTTP 认证方式是 Basic 认证方式（基本验证方案）。

#### Basic Authentication

基本验证方案使用用户的 ID 或密码作为认证信息，并使用 base64 算法对其进行编码。

但是，由于 base64 算法的可逆性，基本验证方案并不安全。如果在非 HTTPS 的请求中使用会导致信息泄漏等安全风险。由此，Basic 认证方式不应该用来传输敏感的信息。

### 缓存

HTTP 缓存允许用户复用之前的资源来显著提高性能。

当缓存发现当前请求已经被存储，就会自动拦截请求并返回存储的资源。这跳过了请求源服务器的步骤，大大提升了访问速度。However，不是所有的缓存都是永久不变的：我们需要对缓存的截止时间作出相应的调整，使其不缓存过期的资源。

缓存分为两种，一种是私有的浏览器缓存，另一种是共享的代理缓存。

浏览器缓存，顾名思义，就是将缓存直接存储在浏览器中。而代理缓存，就是在目标服务器和用户之间添加一个代理。它将会把经常访问的资源缓存，并以此减少网络拥堵。

虽然 HTTP 缓存不是必须的，但重用缓存的资源通常是必要的。常见的 HTTP 缓存只能存储 GET 请求的相应，对其他类型的请求稍显无能为力。

客户端可以通过设置 `Cache-Control` 请求头来控制缓存。

`Cache-Control` 的常见取值由 `no-store` , `no-cache` , `max-age=<seconds>` , `must-revalidate` , `private` , `public` 等。

其中，`no-store` 代表不进行任何缓存，`no-cache` 代表缓存但重新验证是否过期，`max-age` 代表缓存保持 fresh 状态的最长时间。

更详细的缓存的信息可以在 [MDN](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Caching) 找到。

### Cookie

正如我们一开始所说的，HTTP 是无状态的。但是我们可以通过 Cookies 创建有状态的会话。

服务端可以直接使用 `Set-Cookie` 响应头来给客户端发送 Cookie 信息。一个最基础的 Cookie 可以这样设置：

```
Set-Cookie: <name>=<value>
```

客户端会将服务器给定的值存储到本地。Cookies 一旦存储，每次请求客户端都会发送 `Cookies` 请求头给服务器：

```
Cookie: <name1>=<value1>; <name2>=<value2>; ...
```

#### Cookies 的生命周期

Cookie 的生命周期可以通过 `Expires` 或 `Max-Age` 设置。E.g:

```
Set-Cookie: fruit=orange; Expires=Wed, 21 Oct 2022 07:28:00 GMT;
```

更多信息请参考 [MDN](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Cookies) 。

## 参考资料

### 文档

- [TCP/IP四层模型](https://zhuanlan.zhihu.com/p/57936826), [勤劳的小手](https://www.zhihu.com/people/duan-pan-ykjym), 2021.
- [HTTP概述](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Overview), MDN contributors, 2022.
- [Data URLs](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Basics_of_HTTP/Data_URIs), MDN contributors, 2022.
- [HTTP响应](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Messages), MDN contributors, 2022.
- [HTTP基础](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Basics_of_HTTP/MIME_types), MDN contributors, 2022.
- [HTTP缓存](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Caching), MDN contributors, 2022.
- [HTTP Cookies](https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Cookies), MDN contributors, 2022.

### BGM

- [Creative Minds](https://www.bensound.com/royalty-free-music/track/creative-minds), *Benjamin Tissot* .
- [Punky](https://www.bensound.com/royalty-free-music/track/punky), *Benjamin Tissot* .
- [Energy](https://www.bensound.com/royalty-free-music/track/energy), *Benjamin Tissot* .

TCP｜你真的懂 HTTP 吗？


此为我在 B 站上发布的视频 [JS 花式输出 | 你真的会用 console.log 吗？](https://www.bilibili.com/video/BV1Eq4y1t7C1) 的文字稿。

<iframe src="//player.bilibili.com/player.html?aid=594140875&bvid=BV1Eq4y1t7C1&cid=514614537&page=1" scrolling="no" border="0" frameborder="no" framespacing="0" allowfullscreen="true"> </iframe>

## 引言

`console.log` 是每一个 JavaScript 开发者都会经常用到的函数。可能很多初学者第一次使用 JS 时，就是调用的它。

`console.log` 可能最广泛的用途就是输出调试信息了吧：

```js
console.log(current_processing);
```

当然，还有招聘信息：

![image-20220221194418180](https://s2.loli.net/2022/02/21/RiKjwpfabPA1xDu.png)

但是，你可能注意到了，百度这招聘信息写的挺花哨啊，这字还是红色的！

不知道各位会不会写，反正我第一次看见的时候是不会弄的。无论你会不会打印出这样的效果，继续往下看，一定会有所收获的。

## 彩色字？搞定！

首先，我们来看一下怎么来打印彩色字。

```js
console.log(msg)
```

这，是 JS `console.log` 的最基本形式，也可能是大部分人所熟知的形式。

但是，其实这个 msg 后面是有东西的 —— 正是那些不起眼的参数，能够让我们的 log 变得“上档次”。

根据 [MDN](https://developer.mozilla.org/en-US/docs/Web/API/console/log#syntax) 的定义，`console.log` 的定义如下：

```js
console.log(obj1 [, obj2, ..., objN]);
console.log(msg [, subst1, ..., substN]);
```

其中，`obj1 - objN` 代表的是要输出的 JS 对象。

而 `msg` 则是一个包含着各种控制字符的字符串，也是我们今天的主角。而后面跟着的 `subst1 - substN` 都是用来替换控制字符的特殊字符串。

首先，我们来看看怎么打印彩色字符吧。

```js
console.log("Hello, World")
```

这，是最基础的 Hello World 。如果你现在运行，会得到一个纯正血统的 JS HelloWorld。

但是，我们想要的是彩色输出！别急，我们先来认识一下第一个控制字符 —— `%c` 。有了它，你就可以随意往 console 里面堆积 CSS 了 —— 没错，这个 `%c` 代表着 CSS ！

只要把 `%c` 放在你要使用 CSS 的字符的前面，就能开始写 CSS 了。例如：

```js
console.log("%cHello, World")
```

下一步就是加上样式了。还记得之前的 `subst` 吗？它们现在可以派上用场了：

```js
console.log("%cHello, World", "color: red")
```

对，你没看错，就是 CSS ！一个 `%c` 对应着一个样式，而每一个 `%c` 都将会把从当前字符到下一个 `%c` 之前的一个字符渲染上对应的 CSS 样式。如果你用的是电脑端的话，可以按下 F12 试一试，就是这么简单！

![image-20220221201116931](https://s2.loli.net/2022/02/21/aAkF5poZmQNu9HJ.png)

如果你会一点 CSS 的话……你甚至可以弄成这样：

![image-20220221202058862](https://s2.loli.net/2022/02/21/inwxVNJ376uWame.png)

但是，这玩意更普遍的用途是这样的：

![image-20220221202230330](https://s2.loli.net/2022/02/21/FbGuKjq4pfmy7Tr.png)

这样的：

![image-20220221202319713](https://s2.loli.net/2022/02/21/wMCX6yHvkWcZi1r.png)

既然上面说了可以添加自定义 CSS ，那么我们应该能够完成这个挑战。

理论存在，实践开始。

先上最基础的无样式版本：

```js
console.log(
  `Powered by VueBlogger v0.1.0\n
GitHub: https://github.com/samzhangjy/VueBlogger\nPlease star & fork to support the author!`);
```

按照刚才说的方法，在 `VueBlogger` 前面加上 `%c` ，并添加相对应的样式：

```js
console.log(
  `Powered by %cVueBlogger v0.1.0\n
GitHub: https://github.com/samzhangjy/VueBlogger\nPlease star & fork to support the author!`,
  "background-color: #1A55ED; padding: 7px; color: #fff;"
);
```

但是，如果仅仅是这样，你会得到一个非常蓝的 console ：

![image-20220221202832979](https://s2.loli.net/2022/02/21/VkKgR3dUQEmotjO.png)

还记得刚才说的吗？

> 一个 `%c` 对应着一个样式，而每一个 `%c` 都将会把从当前字符到下一个 `%c` 之前的一个字符渲染上对应的 CSS 样式。

所以，我们只需要在 `v0.1.0` 前添加 `%c` 控制字符就 ok 啦：

```js
console.log(
  `Powered by %cVueBlogger%cv0.1.0\n
GitHub: https://github.com/samzhangjy/VueBlogger\nPlease star & fork to support the author!`,
  "background-color: #1A55ED; padding: 7px; color: #fff;",
  "background-color: #FCBF23; color: #000; padding: 7px;"
);
```

但是，这样还是会出现刚才的情况，只不过变黄了……

于是，我们可以再加个 `%c` ：

```js
console.log(
  `Powered by %cVueBlogger%cv0.1.0%c\n
GitHub: https://github.com/samzhangjy/VueBlogger\nPlease star & fork to support the author!`,
  "background-color: #1A55ED; padding: 7px; color: #fff;",
  "background-color: #FCBF23; color: #000; padding: 7px;",
  ""
);
```

现在我们的 console 输出正常了。是的，你可以通过把对应的 CSS 置空来消除前面的 CSS 效果！

那么第二个输出也就迎刃而解了，此处不再赘述。

哦对了，不是所有的 CSS 都能够移至到 console 里的 —— 请看 [MDN](https://developer.mozilla.org/en-US/docs/Web/API/console#outputting_text_to_the_console) 的详细说明。

当然，`console.log` 还有其他的控制字符 —— 例如 `%o, %d, %s, %f` 等，此处不再赘述，可以参见 [MDN](https://developer.mozilla.org/en-US/docs/Web/API/console#outputting_text_to_the_console) 查看更多信息。其中，`%d, %s, %f` 与其他语言中的格式化字符串很相似（例如 `C++` 的），作用也是格式化字符串、数字等信息。

## `console.assert ` —— 调试神器

如果你用过 Python 的话，你肯定会对 `unittest` 中形如 `assertXxxx` 的函数十分熟悉。现在，甚至有一部分灵魂跑到 JS 上了！没错，这就是 `console.assert` 。

按照惯例，先看定义：

```js
console.assert(assertion, obj1 [, obj2, ..., objN]);
console.assert(assertion, msg [, subst1, ..., substN]); // C-like message formatting
```

跟 `console.log` 差不多 —— 但是多了一个 `assertion` 。而它，就是要 assert 的对象。如果 `assertion` 的结果不为真，那么将会以类似 `console.error()` 的样式打印出后面的错误信息 `msg` 。

来看一个最简单的栗子：

```js
console.assert(![], "Yep, that's falsy.")
```

如果 `![]` 的值是非真的，那么我们将会收到一个自定义的报错：

![image-20220221205718474](https://s2.loli.net/2022/02/21/wb3uEgFGqW2mxJn.png)

那么，如果 assert 的结果是真的，就会正常执行，没有输出：

![image-20220221210046788](https://s2.loli.net/2022/02/21/qRXGbOc82KuiCTj.png)

同理，`console.assert` 也能使用 CSS：

```js
console.assert(0.1 + 0.2 === 0.3, "%cYou can't even can't get 0.1 + 0.2 right in js.", "font-weight: bold; font-style: italic; background-color: orange; color: #000")
```

![image-20220221210210114](https://s2.loli.net/2022/02/21/EFOWpIQVUxiykTS.png)

## `console.count` —— 计数神器

语法：

```js
console.count([label]);
```

`console.count` 函数接收一个字符串列表，列表中的元素表示一个标签。每次计数时，`console.count` 都会输出当前标签列表被计数的次数，并持续累积。如果没有给出任何标签，则会使用 `default` 默认标签。

这东西用起来也很简单，喂给它一些数据就行了：

```js
console.count("A");
console.count("B");
console.count("A");
```

![image-20220221211134769](https://s2.loli.net/2022/02/21/czUSn9j4vb8PEiL.png)

来做个示例：

```js
for (var i = 1; i <= 10; i++) {
	for (var j = 1; j <= i; j++) {
    	if (i % j == 0) console.count(i)
    }
}
```

这段代码会输出 1 - 10 这些数字的因数个数。

![image-20220221211731024](https://s2.loli.net/2022/02/21/FhHqOQtP3RS4p7J.png)

## `console.group` —— 没啥特别的，感觉会有用

`console.group` 允许你在 console 中输出层级嵌套的信息。

你可以使用 `console.group` 来创建一个新层，然后使用 `console.log` 、`console.warn` 、`console.error` 等函数在该层级下进行输出，最后使用 `console.groupEnd()` 来结束当前层。

示例：

```js
console.log("I'm here at the top level");
console.group("Level 2 group here!");
console.log("I'm in level 2!");
console.group("Level 3!");
console.log("You know what, [] is really weird in JS.")
console.error("0.1 + 0.2 !== 0.3 in JS =(");
console.groupEnd();
console.log("Back at level 2!");
console.groupEnd();
console.info("Wow, what a trip up there!");
```

![image-20220221212457244](https://s2.loli.net/2022/02/21/JiILZ9QAC4domM1.png)

函数太多，不放定义啦，大家应该参照运行结果就能看懂啦。

## 小结

这篇文章简单介绍了一下 `console` 的各种使用方法。但是，像一些过于普通的（例如 info、error、warning 等），我没有在这里一一介绍。

如果有小伙伴想要了解这方面的更多知识，可以前往 [MDN](https://developer.mozilla.org/en-US/docs/Web/API/console) 进行查阅，相信你一定会有新的收获。

我是 samzhangjy ，我们下期再见！

Sam Zhang.

Monalisa. // Heavenly questions.

博客

在博客页面查看所有的博客存档