微分符号和积分符号

准备工作:

  • 了解极限的定义以及相关的无穷小等概念。
  • 了解导数是什么。
  • 了解极限运算法则和求导法则。
  • 理解“微分是函数的线性近似”

很多人都说《高等数学》难学,一部分缘于求极限、求导和积分是全新的、之前没有接触过的运算,要掌握和熟练运用需要不少苦功夫;另一部分就要归结于编书者用“惯例”来搪塞各种解释的高傲态度。

第二章中,先介绍导数,再介绍微分。这导致前面突然就冒出个\(\dfrac{\mathrm{d}}{\mathrm{d}x}\)求导符号。然而介绍微分的时候又草草带过。基本上,书中是这样定义微分运算的:对函数\(y=f(x)\),如果\(x_0\)\(x_0+\Delta x\)在定义域内且 \[ \Delta y=f'\left( x\right) \Delta x+o\left( \Delta x\right) \] 那么记作 \[ \mathrm{d}y=A\Delta x. \] 并且通常把自变量\(x\)的增量\(\Delta x\)称为自变量的微分,记作\(\mathrm{d}x\),即\(\mathrm{d}x=\Delta x\). 所以函数\(y=f(x)\)的微分记作 \[ \mathrm{d}y=f'(x)\mathrm{d}x. \] 嗯?这就结束了?

所以微分是什么呢?难道跟我们学的加减乘除一样,就是一个运算符号?

是,也不完全是。

回想书中前面的内容,我们一直把求导符号\(\dfrac{\mathrm{d}}{\mathrm{d}x}\)称为“算子”。其实这个概念在第一章第一节早有介绍,只不过大部分人都会忽略:

映射又称为算子。根据集合\(X\)\(Y\)的不同情形,在不同的数学分支中,映射又有不同的惯用名称。例如,从非空集\(X\)到数集\(Y\)的映射又称为\(X\)上的泛函,从非空集\(X\)到它自身的映射又称为\(X\)上的变换,从实数集(或其子集)\(X\)到实数集\(Y\)的映射通常定义为\(X\)上的函数

那么求导是怎样的一种映射?显然是一个原函数映射成一个导函数。那微分呢? \[ \begin{align} y&=x^2\\ \mathrm{d}y&=2x\mathrm{d}x \end{align} \] 是函数映射成函数吗?看着不像啊!这怎么又有\(x\)又有\(\mathrm{d}x\),难道是二元函数?

你可以这么理解,但是我认为一个(在数学上是等价的)更好的理解是:对于每一个\(x\),都有一个对应的函数\(g(\mathrm{d}x)=2x\mathrm{d}x\). 这个函数是\(y\)\(x\)附近的线性近似。微分就是把一个函数映射到这样一个实数到函数的映射(若嫌麻烦也可以理解成二元函数)上面。

到这里,有必要解释一下为啥书里面不先介绍微分了。这其实是个历史遗留问题。微分的符号\(\mathrm{d}\)最早是莱布尼茨发明的(顺便一提,积分符号也是他发明的),他把\(\Delta x\)\(\Delta y\)当成是有限的增量,对应的\(\mathrm{d}x\)\(\mathrm{d}y\)就是无穷小增量。然而麻烦的是,莱布尼茨对于无穷小和微分的定义是很不精确的(莱布尼茨发明微积分的时候还没有极限的严格定义,具体可以参考这里的回答),所以我们现在学习的并不是他的理论。然而我们要学他的符号,因为这已经是“惯例”了。我们学习的是 \[ \dfrac{\mathrm{d}}{\mathrm{d}x}y=\lim _{\Delta x\to 0}{\frac {\Delta y}{\Delta x}} \] 其中\(\dfrac{\mathrm{d}}{\mathrm{d}x}\)就是一个写得比较奇怪的记号。那么你可能会问:先讲微分,不就没这么多破事了吗?不好意思,不行。因为我们现在采用的是柯西给出的微积分定义(极限的严格定义也是柯西给出的)。他是用导数定义微分的: \[ \mathrm{d}y=f'(x)\mathrm{d}x. \] 这下死循环了。所以编书者没办法,就这么将就学吧。

有人会问:不是说牛顿和莱布尼茨同时发明了微积分吗?牛顿的符号为啥没流传下来呢?其实现在也在用,就是\(\dot {y}\),表示\(y\)的一阶导数,二阶就是加两个点,三阶就是加三个点,以此类推。但是这样写并没有显式地指明自变量是什么,容易造成误解。

莱布尼茨符号流行的另外一个原因是它能辅助记忆用于微分和积分的公式。比如链式法则:假设函数\(g\)\(x\)处可微,\(y = f(u)\)\(u = g(x)\)处可微。那么复合函数\(y = f(g(x))\)\(x\)处是可微的,其导数用莱布尼茨符号表示为: \[ \dfrac{\mathrm{d}y}{\mathrm{d}x}=\dfrac{\mathrm{d}y}{\mathrm{d}u}\cdot \dfrac{\mathrm{d}u}{\mathrm{d}x} \]\(\mathrm{d}u\)消……等等!谁告诉你能这么消的? \[ \dfrac{\mathrm{d}y}{\mathrm{d}x}=\lim _{\Delta u\to 0}{\frac {\Delta y}{\Delta u}} \cdot \lim _{\Delta x\to 0}{\frac {\Delta u}{\Delta x}} \] 用极限形式写出来。显然,这两个极限的变量都不一样,不可以消去。

如果要证明链式法则,我们可以利用微分的概念。 \[ \begin{align} \Delta y&=f'(u)\Delta u+o(\Delta u)\\ &=f'(u)\left[g'(x)\Delta x+o(\Delta x)\right]+o(\Delta u)\\ &=f'(u)g'(x)\Delta x+f'(u)\cdot o(\Delta x)+o(\Delta u) \end{align} \] 所以 \[ \mathrm{d}y=f'(u)\mathrm{d}u=f'(u)g'(x)\mathrm{d}x \] 书中用导数定义微分,因此复合函数的微分法则就是由链式法则推出。但是我个人感觉这样的写法更自然好懂:既然我要的是线性近似,那么自变量\(u\)当然也可以被它自己的线性近似替代。

有了链式法则,我们就有了一阶微分形式不变性:对于上面的自变量的微分\(\mathrm{d}u\),我们原先把它看作自变量的增量\(\Delta u\),但是现在我们发现如果\(u\)又作为另外一个函数\(g\)的因变量,\(\mathrm{d}u\)可以直接被替换成它求微分的结果\(g'(x)\mathrm{d}x\).

那既然对谁微分都是一样的形式,岂不是自变量就不重要了?所以\(\mathrm{d}\)无论出现在哪里都是一个意思,无论\(y\)对应的自变量是\(x\)还是\(v\)

错。我们上面说的微分形式不变性是对于一阶微分而言的,对于二阶微分会是什么样的情况呢?

对于二阶导数,书中是这么写的 \[ f''(x)=\dfrac{\mathrm{d}}{\mathrm{d}x}\left(\dfrac{\mathrm{d}y}{\mathrm{d}x}\right)=\dfrac{\mathrm{d}^2y}{\mathrm{d}x^2} \]

看着也挺怪的,我们用微分写 \[ \begin{align} \mathrm{d}^2y&=\mathrm{d}(\mathrm{d}y)\\ &=\mathrm{d}(f'(x)\mathrm{d}x)\\ &=\mathrm{d}(f'(x))\mathrm{d}x+f'(x)\mathrm{d}(\mathrm{d}x)\\ &=(f''(x)\mathrm{d}x)\mathrm{d}x+f'(x)\mathrm{d}^2x\\ &=f''(x)\mathrm{d}x^2+f'(x)\mathrm{d}^2x \end{align} \]

好像多了一项\(f'(x)\mathrm{d}^2x\)

这就是为什么微分形式不变性对于二阶微分不成立!二阶微分不但会受\(\mathrm{d}x^{2}\)影响,也会受\(\mathrm{d^2}x\)影响。

我们若是想得到二阶导数的形式,就必须把\(x\)看成自变量而不是一个可微的函数,我们实际上求的是对\(\mathrm{d}x\)的偏微分

\[ \left(\partial ^ 2 y\right) _ {\mathrm{d}x}=f''(x)\mathrm{d}x^2 \]

所以,二阶微分不具有形式不变性。

现在来说积分。这里直接跳过书上的“记作”论调,重新定义:积分就是微分的逆运算。回想起我们对微分的理解:微分就是把一个函数映射到一个“实数到函数的映射”(若嫌麻烦也可以理解成二元函数)上面。那么积分就是微分的逆映射。给一个实数到函数的映射(二元函数),就能对应回一个函数上。嗯?等等,微分这个映射并不是单射,不同的函数也可能有相同的微分。那怎么办呢?我们给它打个补丁:由于有相同微分的原函数互相都只相差某个常数,我们就把积分定义成一个实数到函数的映射对应一个函数集合。这个函数集合中的函数互相都只相差某个常数,我们就用\(F(x)+C\)来表示这个函数集合。

从定义立即可以得到,如果在区间\(I\)上可导函数\(F(x)\)的导函数为\(f(x)\),对任一\(x\in I\),都有 \[ \int \mathrm{d}F(x)=\int f(x)\mathrm{d}x=F(x)+C. \] 回到上面的复合函数,如果\(f(u)\)具有原函数\(F(u)\),由微分形式不变性,有 \[ \int f(g(x))g'(x)\mathrm{d}x=\int f'(u)\mathrm{d}u=F(u)+C \] 这就是换元积分法中的第一类换元法。其实,这就是对被积表达式部分积分。

我们也可以反向操作:

\(t=\phi ^{-1}(x)\),则\(x=\phi (t)\),有 \[ \int f(x)\mathrm{d}x=\int f(\phi (t))\mathrm{d}\phi (t)=\int f(\phi (t))\phi '(t)\mathrm{d}t \] 这就是换元积分法中的第二类换元法

微分法则能启发我们计算积分,比如:对于在区间\(I\)上的可微函数\(f(x)\)\(g(x)\)\[ \begin{aligned} \mathrm{d}\left[f(x)g(x)\right]&=f(x)\cdot \mathrm{d}g(x)+\mathrm{d}f(x)\cdot g(x)\\ &=f(x)g'(x)\mathrm{d}x+f'(x)g(x)\mathrm{d}x \end{aligned} \] 两边积分得 \[ \int \mathrm{d}\left[f(x)g(x)\right]=\int f(x)g'(x)\mathrm{d}x+\int f'(x)g(x)\mathrm{d}x \]\[ \int f(x)g'(x)\mathrm{d}x=f(x)g(x)-\int f'(x)g(x)\mathrm{d}x \] 这就是分部积分法。也可以写成简洁形式 \[ \int u\mathrm{d}v=uv-\int v\mathrm{d}u \] 如果你想要理解这些积分法则,这里有一个线索:第一、第二类换元法对应的是复合函数,分部积分法对应的是两个函数的乘积运算。这个视频 也许也能帮助你更直观地理解。

学积分的时候应该注意思考积分法则的逆运算(逆操作)是什么。如果能明白简单的积分形式是怎么变复杂的,看到复杂的积分也就不难化简了。上面这三种积分法则的逆运算是什么呢?

很容易发现第一类、第二类换元法是互为逆运算的。而分部积分法的逆运算是它自己 \[ \int u\mathrm{d}v=uv-\int v\mathrm{d}u=uv-\left(uv- \int u\mathrm{d}v \right)=\int u\mathrm{d}v \]

References:

  1. 迷之记号 dx 到底是什么鬼
  2. 什么是微分形式不变性?一阶微分形式不变性与链式法则是等价的吗(两者可互推?)?两者有什么区别? - 马同学的回答
  3. 微分符号 dx、dy 表示什么含义?
  4. Is d/dx not a ratio?
  5. The second differential versus the differential of a differential form

积分中的魔法

积分有什么用呢?

要解释积分的用途,我们要提一个很经典的问题:求曲边梯形的面积。也就是说,我们想知道由两条垂直于\(x\)轴的直线,一条函数曲线\(y = f(x)\)\(x\)轴围成区域的面积。

首先我们得岔开话题,先讲积分的一个有趣的性质。

我们学过拉格朗日中值定理(均值定理):函数\(f(x)\)若在\([a,b]\)内连续,\((a,b)\)内可导,存在\(\xi \in (a,b)\)使 \[ f(b)-f(a)=f'( \xi )(b-a) \] 我们可以尝试把这个定理应用到原函数\(F(x)\)\[ F(b)-F(a)=F'( \xi )(b-a)=f( \xi )(b-a) \] 等式右边是什么意思呢?它看着像是长为\(f(\xi )\)宽为\(b-a\)的长方形的面积。

微积分的核心思想之一,是把宏观的、难以解决的问题转化为很多局部的、近似的问题。

我们可以这么写 \[ F(x+\Delta x)-F(x)=f( \xi )\Delta x \] 等式右边的意思是说,在一个很小的宽为\(\Delta x\)的区间内,其中一点\(\xi\)的函数值为长,\(\Delta x\)为宽围成的面积。

微积分的核心思想之二是极限。在不断趋近的过程中证明要多近有多近。

在这里我们首先要做的是趋近。证明当\(\Delta x \to 0\)\(f( \xi )\Delta x\)可以任意的接近\(\Delta x\)为宽的那个区间内的曲边梯形面积。也就是说 \[ \Delta A=\lim_{\Delta x \to 0}{f( \xi )\Delta x} \] 好吧,这个证明有点冗长,有时间再补。

下一步,就是积。把区间\([a,b]\)分成\(n\)份,每一份的宽度为\(\Delta x = \frac{b-a}{n}\),左右端点为\([x_{i-1},x_i]\),有 \[ F(x_n)-F(x_{n-1})+F(x_{n-1})-F(x_{n-2})+\cdots+F(x_1)-F(x_0)=\sum ^{n}_{i=1}\left[f\left( \xi _{i}\right) \Delta x \right] \] 这时候,奇迹发生了: \[ F(x_n)-F(x_0)=F(b)-F(a)=\sum ^{n}_{i=1}\left[ f\left( \xi _{i}\right) \Delta x \right] \] 左边中间的项全部被消掉,这时候我们发现,等式左边跟\(n\)无关了。也就是说,我们可以自信地写下 \[ F(b)-F(a)=\lim_{n\to \infty}{\sum ^{n}_{i=1}{\frac{f\left( \xi _{i}\right) (b-a)}{n}}}=\lim_{n\to \infty}{\sum ^{n}_{i=1}{\Delta A_i}}=A \] 原本看上去不可能的问题,就这么被轻易解决了。

由于很多问题都可以用类似求曲边梯形的方法解答,我们专门给\(F(b)-F(a)\)分配了符号,并称之为\(f(x)\)在区间\([a,b]\)上的定积分\[ \int_{a}^{b} f(x)\mathrm{d}x=F(b)-F(a) \] 上面的性质也成了积分中值定理 \[ \int_{a}^{b} f(x)\mathrm{d}x=f( \xi )(b-a) \]

从等价无穷小到泰勒公式

启程

在第 1.7 节 无穷小的比较中就介绍了等价无穷小:

如果 \(\lim \dfrac{\beta}{\alpha}=1\),那么就说 \(\beta\)\(\alpha\) 是等价无穷小,记作 \(\alpha \sim \beta\).

比如 \[ \sin x \sim x \ (x\to 0) \] 等价无穷小有什么特别的,以至于要专门给他分配个符号呢?

由极限运算法则,如果 \(\lim f(x)=A\)\(\lim g(x)=B\),那么 \[ \lim[f(x)\cdot g(x)]=\lim f(x)\cdot \lim g(x)=A\cdot B \] 所以 \[ \lim_{x\to 0} f(x) = \lim_{x\to 0} f(x) \cdot \lim_{x\to 0}\dfrac{\sin x}{x} = \lim_{x\to 0} \left[ f(x) \cdot \dfrac{\sin x}{x} \right] \] 来看个实际用例: \[ \lim _{x\rightarrow 0}\dfrac{\sin x}{x^{3}+3x}=\lim _{x\rightarrow 0}\left( \dfrac{\sin x}{x^{3}+3x}\cdot \dfrac{x}{\sin x}\right) = \lim _{x\rightarrow 0}\dfrac{x}{x(x^{2}+3)} = \dfrac{1}{3} \] 常用的等价无穷小还有 \[ \begin{aligned} e^x-1&\sim x\ (x\to 0)\\ \ln (1+x)&\sim x\ (x\to 0) \end{aligned} \]

岔路

过了一段时间,你学到了拉格朗日中值公式。如果(省略)则 \[ f(b)-f(a)=f'( \xi )(b-a) \] 回到上面那个实际用例。我们可以说,由 \(\sin x\)\(x=0\) 的某一去心邻域内可导,所以存在 \(\xi \in \mathring{U}(0,x)\) 使得 \[ \sin x-\sin 0=\cos \xi(x-0) \]\(x\to 0\) 时有 \[ \lim_{x\to 0}\dfrac{\sin x}{x}=\lim_{x\to 0}\dfrac{\sin x-\sin 0}{x-0}=\lim_{x\to 0}\cos \xi=1 \] 看起来有点意思?还有更有意思的。

如果 \(f(x)\)\(g(x)\)\(a\) 的某去心邻域内可导,当 \(x\to a\) 时函数 \(f(x)\)\(g(x)\) 都趋于零,对于下面这个极限 \[ \lim_{x\to a}\frac{f(x)}{g(x)} \] 我们可以把上面的方法同时应用到分子分母上。我们为了连续性假定 \(f(a)=g(a)=0\) 则此时两函数在 \(a\) 的某邻域内连续。

存在 \(\xi_1 \in \mathring{U}(a,x), \xi_2 \in \mathring{U}(a,x)\)​ 使得 \[ \begin{aligned} f(x)-f(a)&=f'(\xi_1)(x-a)\\ g(x)-g(a)&=g'(\xi_2)(x-a) \end{aligned} \]

\(g'(x)\neq 0\),有 \[ \lim_{x\to a}\dfrac{f(x)}{g(x)}=\lim_{x\to a}\dfrac{f(x)-f(a)}{g(x)-g(a)}=\lim_{x\to a}\frac{f'(\xi_1)(x-a)}{g'(\xi_2)(x-a)}=\lim_{x\to a}\frac{f'(x)}{g'(x)} \] 洛必达法则!实际上证明洛必达法则并不依赖柯西中值定理。

上面的推导启示我们,洛必达法则和等价无穷小有某种意义上的联系。若函数 \(f(x)\)\(g(x)\)\(x=x_0\) 的某邻域内 \(n\) 阶可导,且当 \(x\to x_0\)\(f(x)\sim g(x)\)\[ \lim_{x\to x_0}\dfrac{f(x)}{g(x)}=\lim_{x\to x_0}\frac{f^{(n)}(x)}{g^{(n)}(x)}=1 \] 另外,在这个过程中你可能会发现 \[ \frac{f(b)-f(a)}{g(b)-g(a)}=\frac{f'(\xi_1)(b-a)}{g'(\xi_2)(b-a)}=\frac{f'(\xi_1)}{g'(\xi_2)} \] 柯西中值定理?其实并不是,柯西中值定理还需要 \(\xi_1=\xi_2\)​,构造 \[ h(x) = [f(x) - f(a)][g(b) - g(a)] - [g(x) - g(a)][f(b) - f(a)]. \] 显然 \(h(a)=h(b)=0\)​,由罗尔中值定理得 \[ 0 = h'(\xi) = f'(\xi)(g(b) - g(a)) - g'(\xi)(f(b) - f(a)) \]

为什么同济高数书上要写成这么别扭的样子呢? \[ h(x)=f(x)-\frac{f(b)-f(a)}{g(b)-g(a)}g(x) \] 我猜大概是为了强调 \(g(b)-g(a)\neq 0\) 吧(由 \(g'(x)\neq 0\) 推出)

再来看一个洛必达法则的证明:

\(f, g : (a, b) \to R\)\(x_0 \in (a,b)\) 上可导,且 \(f(x_0)=g(x_0)=0\)\(g'(x_0)\neq 0\). 则 \[ \frac{f'(x_0)}{g'(x_0)}=\frac{\lim_{x\to x_0}{\frac{f(x)-f(x_0)}{x-x_0}}}{\lim_{x\to x_0}{\frac{g(x)-g(x_0)}{x-x_0}}}=\lim_{x\to x_0}{\frac{f(x)-f(x_0)}{g(x)-g(x_0)}}=\lim_{x\to x_0}{\frac{f(x)}{g(x)}} \] 这就证完了?能用一行证明,为什么上面要绕一大圈?

请注意洛必达法则的条件

  1. \(x\to x_0\) 时,函数 \(f(x)\)\(g(x)\) 都趋于零.
  2. 在点 \(x_0\)某去心邻域内\(f'(x)\)\(g'(x)\) 都存在且 \(g'(x)\neq 0\).
  3. \(\lim_{x\to x_0}{\frac{f'(x)}{g'(x)}}\) 存在(或为无穷大).

其中第 1、2 点都不一样,但是证明时假定了 \(f(x_0)=g(x_0)=0\) 所以实际上第 1 点没有区别。最关键的是第 2 点:\(f(x)\)\(g(x)\) 只需要在 \(x_0\) 的某去心邻域可导,不需要在 \(x_0\) 可导。与之相对应,公式中也是取两函数导数的比值的极限。

迷途

我们来看一道 经 典 例 题: \[ \lim_{x\to0}\left(\frac{e^x +xe^x}{e^x-1}-\frac{1}{x}\right) \] 你可能会这么写: \[ \begin{aligned} \lim_{x\to 0}\left(\frac{e^x +xe^x}{e^x-1}-\frac{1}{x}\right)&=\lim_{x\to 0}\frac{e^x +xe^x}{e^x-1} - \lim_{x\to 0}\frac{1}{x} \\ &=\lim_{x\to 0}\frac{e^x +xe^x}{e^x-1}\times \lim_{x\to 0}\frac{e^x-1}{x}-\lim_{x\to 0}\frac{1}{x} \\ &=\lim_{x\to 0}\left(\frac{e^x +xe^x}{e^x-1} \times \frac{e^x-1}{x}\right)-\lim_{x\to 0}\frac{1}{x} \\ &=\lim_{x\to 0}\left(\frac{e^x +xe^x}{x}-\frac{1}{x}\right) \\ &=\lim_{x\to 0}\frac{e^x +xe^x-1}{x} \\ &=\lim_{x\to 0}\left(2e^x-xe^x\right) \\ &=2 \end{aligned} \]

然而!答案是 \(\frac{2}{3}\).

错在哪呢?其实第一步就错了,拆出来成了 \(\infty -\infty\),而极限运算法则只在两极限存在时才成立,不能拆。如果你不是这么做的但是得到了错误的结果,请自行根据 这篇文章 对号入座。

辅导书和老师可能会告诉你,等价无穷小的用法仅限于极限值整体乘以 1 再代换!这种说法确实没错,但是事情是不是就这么简单地结束了呢?为什么有的情况下替换不会出现问题呢?

请看同济高数第 1-7 节定理 1: \(\beta\)\(\alpha\) 是等价无穷小的充分必要条件为 \[ \beta=\alpha + o(\alpha) \] 可以看出,两个等价无穷小之间差了一个高阶无穷小。那么什么时候不能用等价无穷小呢?

就是除了无穷小以外的量全部都被消去的情况,这时候高阶无穷小才会左右极限的结果,而它会受到等价无穷小替换的影响而不准确。

也就是说

已知 \(\lim_{x\to x_0}{\frac{\alpha_1}{\alpha_2}}\) 存在, \(\alpha_1,\alpha_{2},\beta_{1},\beta_{2}\) 都是 \(x\rightarrow x_0\) 的无穷小量,且 \(\alpha_1\sim\beta_1\)\(\alpha_{2}\sim\beta_{2}\).

\(\lim_{x\rightarrow x_0}{\frac{\alpha_1}{\alpha_2}} \neq 1\) (两者的泰勒展开的第一项不相同),则 \(\alpha_1-\alpha_2\sim \beta_1-\beta_2\);

\(\lim_{x\rightarrow x_0}{\frac{\alpha_1}{\alpha_2}} \neq -1\)(两者的泰勒展开的第一项不互为相反数),则 \(\alpha_1+\alpha_2\sim\beta_1+\beta_2\).

终点

上面看似已经把等价无穷小的用法说清楚了,但是还有很多隐藏的问题。比如说,极限运算法则必须要两个极限存在才成立,那么如果我要求的极限本来就不存在呢?难道我每次用之前还要证明这个极限存在?

所以我们不如用回等价无穷小的充要条件 \[ \alpha \sim \beta \Leftrightarrow \beta=\alpha + o(\alpha) \] 等价替换永远是最直接、最少出错的。

而实际上我们用等价无穷小的时候几乎从来都是换成多项式函数,因为它好化简、好求极限。

又过了一段时间,你学到了泰勒公式,它是拉格朗日中值公式的推广(令 \(n=2m\)\[ \begin{align} \sin \left(x\right)&= x-{\frac {x^{3}}{3!}}+{\frac {x^{5}}{5!}}-{\frac {x^{7}}{7!}}+\cdots +(-1)^{m-1}\dfrac{x^{2m-1}}{(2m-1)!}+o(x^{2m})\\ e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+\cdots +\frac{x^{n-1}}{(n-1)!} +o(x^n)\\ \ln(1+x)&=x-{\frac {x^{2}}{2}}+{\frac {x^{3}}{3}}-\cdots+(-1)^{n-1}\dfrac{1}{n}x^n+o(x^n) \end{align} \]

接下来不用多说了吧。用泰勒公式,别用等价无穷小。

后记:这篇文章写的很混乱,中途删了又写,写了又删。最后终于在高数期末考前仓促结尾,行文思路混乱,更别说严谨性。现在回头反思,总感觉自己太过于相信自己的所谓直觉,推导一番后又发现和目标不搭边。总结:想的太多,读的太少,算的更少。

References:

  1. Cauchy's Mean Value Theorem and L'Hopital's rule
  2. (PDF)Lecture 7 : Cauchy Mean Value Theorem, L'Hospital Rule
  3. 高数常见坑点:等价无穷小
  4. “等价无穷小量的替换”的详析 - 李亦督的文章 - 知乎

学习算法的过程中看题解是很重要的一环,但往往题解只提供一种解法,角度难免片面。因此这里主要以题目为中心,整理我看到的各种解法以及一些个人感想。

P1115 最大子段和

这题贪心应该是最直接的方法,也同时可以用前缀和的思想做。

题目要求的是选连续的一段,而且不限制长度,如果我们又枚举起点又枚举长度就会 \(O(n^2)\) .

起点不确定的情况不好控制,我们可以把子段和转化成:第 \(1\)\(x\) 个数之和减去第 \(1\)\(y\) 个数之和,其中 \(x > y\) . 对于每一个 \(x\) ,问题就转换成了求最小前缀和。时间复杂度 \(O(n)\).

贪心就更直接了。设当前以第 \(i\) 个数结尾的子段最大和为 \(dp[i]\) ,我们可以看出若是 \(dp[i - 1] + a[i] < 0\),我们就还不如不选第 \(i\) 个数,直接 \(dp[i] = 0\) 即可。其他情况下就必然是 \(dp[i] = dp[i - 1] + a[i]\). 最后找出最大的 \(dp[i]\) 就可以了。由于 \(dp[i]\) 可以直接由一个变量存储,空间复杂度 \(O(1)\). 时间复杂度 \(O(n)\).

CF1573B Swaps

这题看起来很复杂,其实就一个关键点:\(a\) 都为奇数而 \(b\) 都为偶数,因此这两个数组从第一个数开始就不一样。想让 \(a\) 字典序小于 \(b\) 的话,就需要且仅需要 \(a_1<b_1\). 所以只要找到一对 \(a_i\)\(b_j\) 满足 \(a_i<b_j\) 并一个一个把这两个数分别移到最前面就好了。此时问题就转化为找最小的 \(i+j-2\). (若下标从 \(0\) 开始则为最小的 \(i+j\)

假设我们一定要选某个 \(b\) 中的偶数 \(b_j\),此时我们只需要找满足 \(a_i<b_j\) 的下标最小的 \(a_i\) 即为最优解。因此我们可以这样做:开一个数组 \(p\) 记录某个数 \(n\) 在数组 \(a/b\) 中的位置 \(p_n\). 从大到小遍历所有的数,然后用一个变量 \(l\) 记录当前遍历到的 \(a\) 中最小的下标,若当前数 \(n\) 为奇数则 \(l=min(l, p_n)\),若当前为偶数则更新答案为 \(min(answer, p_n + l)\). (注意这里认为下标从 \(0\) 开始)

ABC223B String Shifting

不知道是不是受到之前做的一道很类似的题的影响,这题想了很久很久。

首先分析问题:题目中的平移可等价为把字符串的前\(n\)个字符移到最后或者把字符串的后\(n\)个字符移到最前。那么我们首先会发现把前\(n\)个字符移动到最后等价于把后\(length-n\)个字符移动到最前,我们只用关心移动到最前(或最后)的情况。由于每次只能操作最后的\(n\)个字符,无论操作多少次都可等价于操作一次。那么问题转化为:

给定非空字符串\(S\),选择\(S\)的后\(n\)个字符移动到首端。分别求移动后使得\(S\)字典序最大和最小的\(n\)

剩下的就很简单了:鉴于\(n\leq1000\),我们直接枚举所有可能的\(n\),把最大的和最小的找出来就好了。(然而因为没注意到这个题允许\(O(n^2)\)时间复杂度我卡了1hr多)

2019年广东工业大学新生赛 F 失踪的玫瑰

参考:【题解】2019年广东工业大学腾讯杯新生程序设计竞赛

题面可以等价转换为:有\(n\)个山洞,初始状态下每个山洞里都有一只狐狸,每天晚上每只没抓住的狐狸都会分身去两边的洞,每天白天都有一个猎人去查看一个山洞,求抓住全部狐狸的方案数。以下用x代表一定没有狐狸的洞口,用o代表有狐狸的洞口。对于\(n=5\)的情况,我们从右往左依次检查试试:

检查洞口 白天抓捕完后 过了一晚上后
5 oooox ooooo
4 oooxo oooox
3 ooxox oooxo
2 oxoxo xoxox

可以看出最后一次抓捕的下一个白天,所有奇数洞都没有狐狸。

下面有一个重要的结论:

每天检查之后,被检查的洞的右边不会存在开局位于奇数洞的狐狸。

为什么呢?

因为开局在奇数洞的狐狸,在奇数次抓捕时必定在奇数洞里,在偶数次抓捕时必定在偶数洞里。开局在偶数洞的狐狸正好相反。而从奇数洞走到旁边的奇数洞需要2个晚上,被检查的洞的左边的狐狸若是想走到右边,必定会在移动时遇到抓捕。

这里还应注意到的是,我们第一天检查5号洞口后,4号洞口的狐狸当晚就会分身去5号洞口,也就是说检查两边的洞口是无效的。因此3天即可抓捕完奇数洞狐狸。

如果要抓开局位于偶数洞的狐狸呢?

检查洞口 白天抓捕完后 过了一晚上后
4 oooxo oooox
3 ooxox oooxo
2 oxoxo xoxox

3天即可抓捕完。

然后呢,抓奇数洞狐狸?诶奇数洞怎么已经没有狐狸了?这是因为我们花了奇数天抓捕,开局偶数洞的狐狸一晚上后都在奇数洞。那么我们能不能把这个当作开局状态,再来一次偶数洞狐狸抓捕?

当然可以!最后答案是\(\{4,3,2,4,3,2\}\),但是这不是字典序最小的方案。因为选择从左到右给洞穴标号还是从右到左给洞穴标号是不重要的,所以答案为\(\{2,3,4,2,3,4\}\).

再经过一些推导,洞穴个数\(n\)为奇数时都为这种情况,即\(\{2,3,4,\cdots ,n-1,2,3,4,\cdots ,n-1\}\).

\(n\)为偶数时,比如\(n=4\)时,因为\(n-1=3\)为奇数,我们就先抓开局奇数洞狐狸:

检查洞口 白天抓捕完后 过了一晚上后
3 ooxo ooox
2 oxox xoxo
3 xoxo(?) oxox
2 oxox(?) xoxo

诶诶诶等一下!这最后两次都抓了个空气啊!

这是因为\(n\)为偶数时抓奇数洞狐狸所需天数不是奇数天而是偶数天了。开局偶数洞的狐狸一晚上后都在偶数洞。我们要抓偶数洞狐狸,但是不能检查两边的洞口(也就是第1个洞口不能是\(n\)),所以我们调换方向,从2号洞口开始。

检查洞口 白天抓捕完后 过了一晚上后
2 oxoo xooo
3 xoxo oxox

成功!最后结果是\(\{3,2,2,3\}\),调换一下编号方向就是\(\{2,3,3,2\}\). 所以\(n\)为偶数时答案为\(\{2,3,\cdots n-1,n-1,n-2,\cdots ,1\}\).

CF1584B Coloring Rectangles

刚看到这题的时候没什么想法,就乱试。试了半天发现似乎\(1\times 3\)是最优的切法。然后就开始纠结在特判两条边都不能被\(3\)整除的情况上。现在回想起来,自己的思维还是太窄了。

然后就想了个DP做法。对于\(1\times n\)的长方形而言,只需要贪心尽可能多地切成\(1\times 3\)即可。模拟一下就会发现答案是\(\lceil \frac{n}{3} \rceil\)​. 于是就可以用DP做了:

1
2
3
4
5
for (int i = 1; i < MAXNM; i++) {
for (int j = 1; j < MAXNM; j++) {
dp[i][j] = min(dp[i - 1][j] + ((j + 3 - 1) / 3), dp[i][j - 1] + ((i + 3 - 1) / 3));
}
}

然而看数据范围\(1 \leq n, m \leq 3 \cdot 10^4\),被卡了。所以下面是官方题解:

首先找上色后矩形的性质:若一个矩形按照题目要求上色,则相邻的行/列的上色图案正好相反,相邻两行的上色和未上色方块数相同。若长和宽都为偶数,则每两行和列的上色图案将会完全相同。若一个为偶数一个为奇数,则每两行或列的上色图案将会完全相同,这两行内部互相上色方块数将相差1. 这两种情况下上色和未上色方块数都相同,即上色方块占所有方块的\(\frac{1}{2}\)。但若长和宽都为奇数,上色和未上色方块数将会相差1. 令方块总数(面积)为\(S\), 则上色方块数为\(\frac{S - 1}{2}\), 占所有方块的\(\frac{S - 1}{2 \cdot S}\).

我们的期望是上色方块的比例尽可能小。根据题目条件\(S\geq 2\),因此当\(S=3\)\(\frac{S - 1}{2 \cdot S}=\frac{1}{3}\)为可能的最小值。因此,这就是对答案的最小估计:\(n \cdot m \cdot \frac{1}{3} \leq answer\).

现在,如果我们构造出一个要求必须给\(cnt\)个方块上色的剪切方案,且\(\frac{n \cdot m}{3} \leq cnt < \frac{n \cdot m}{3} + 1\),那么答案就是\(cnt\). (也即这个剪切方案就是最优方案)因为\(cnt\)是满足我们估计的最小的整数。

如果一条边能被3整除,那么很明显你可以把它全部切成\(1\times 3\)的矩形然后得到最优解。

如果这两条边被3除后余1和1,或者余2和2,那么你可以把它切成一些\(1\times 3\)的矩形,加上一个\(1\times 4\)\(2\times 2\)的矩形。多出来的这个矩形里要给2个方块上色,显然满足要求。

如果这两条边被3除后余1和2,那么你可以把它切成一些\(1\times 3\)的矩形,加上一个\(1\times 2\)的矩形。多出来的这个矩形里要给1个方块上色,显然满足要求。

由答案必须是整数,可得答案为\(\lceil \frac{n \cdot m}{3} \rceil\).

P5824 十二重计数法

自己做的,好像有些错误。先记着吧。

  1. 问题可转化成有\(n\)个有编号的格子,每个格子可填入\(1\sim m\)的任意整数。题目正好对应为\(m\)进制下\(1\sim n\)位数的个数,也即\(n^m\).(可重复排列
  2. 先从\([1,n]\)中选出\(m\)个数,然后全排列。即\(C_n^m\cdot A_m^m\).
  3. 可拆分成:先从\([1,n]\)中选出\(m\)个数,使它们装到\(m\)个盒子中,每个盒子至多装一个球,也即问题2;剩下的\(n-m\)个球可以任意装到盒子中,也即问题1. 答案\(C_n^m\cdot A_m^m\cdot (n-m)^m\).
  4. 盒子全部相同,意味着哪些球在一个盒子里重要,但是具体在哪一个盒子不重要。问题1除以盒子的排列数\(A_m^m\)即可。但是我们也可以用隔板法:\(1,2,\cdots ,n\)编号的小球打乱顺序后之间放上\(m-1\)个隔板。即为\(A_n^n\cdot C_{n+1}^{m-1}\).
  5. 不可重复组合\(C_n^m\).
  6. 先从\([1,n]\)中选出\(m\)个数直接装到盒子中,剩下的\(n-m\)个球任意装。\(C_n^m\cdot A_{n-m}^{n-m}\cdot C_{n-m+1}^{m-1}\).
  7. 球全部相同,意味着盒子里有多少球重要,但是具体是哪些球不重要。可用隔板法:\(n\)个小球中间放上\(m-1\)个隔板,即\(C_{n+1}^{m-1}\).
  8. 盒子只有两种状态:装了一个球/没装球。选出装了球的盒子即为\(C_m^n\).
  9. 每个盒子都装一个球后剩下的球有\(n-m\)个,回到问题7,即\(C_{n-m+1}^{m-1}\).
  10. 从这开始就有点难了,先模拟一下:设装球最少的盒子装了\(x\)个球,那么装球第二少的盒子可以装\([x,m]\)个,

2021广东工业大学新生赛初赛题解与反思

初赛结果不理想,只出了5个题。

其实回想起来有些题赛时本来能做出来的,但是因为各种原因没做好,在此纪录。也一并为以后的学习指明方向。

A 简单的求零点问题

很显然,用二分找零点。但是我一看到这题就有点犯难,为什么呢?因为我连二分都不能熟练地码出来

所以今天整理一下二分。(参考这篇文章

如何快速判断自己的二分程序是否正确

我们知道二分的思想就是每次取一半,想象一下,不管给我们的数组有多长,每次取一半,最终都会被压缩成长度为 1 的数组,然后在这个长度为 1 的数组里判断并返回,所以我们可以直接用长度为 1 的数组来测试程序。

二分查找

给定长度为n的数组(\(n\geq 1\)

问题1:找到值为value的元素的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int BinarySearch(int array[], int n, int value) {
int left = 0;
int right = n - 1;
while (left <= right) {
// 注意防止溢出
int middle = left + ((right - left) >> 1);
if (array[middle] > value) {
right = middle - 1;
} else if (array[middle] < value) {
left = middle + 1;
} else {
return middle;
}
}
return -1;
}

问题2:找到第一个值为value的元素的下标

这时候遇到相等也不能直接返回,只能排除掉右侧的所有数。

数组的长度为 1 或 2 时,middle为 0. 若array[0]为要找的数,则right将被赋值为 -1,循环结束,left为答案。数组长度为 2 且array[1]为要找的数时,left将被赋值为 1,回到数组长度为 1 的情况。

因此最后再判断一下left是否为要找的数,如果是则返回,否则答案不存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int BinarySearch(int array[], int n, int value) {
int left = 0;
int right = n - 1;

while (left <= right) {
int middle = left + ((right - left) >> 1);

if (array[middle] >= value) {
right = middle - 1;
} else {
left = middle + 1;
}
}

if (left < n && array[left] == value) {
return left;
}
return -1;
}

问题3:找到最后一个值为value的元素的下标

这就是问题2的倒序版本。改动两个地方即可

  1. if (array[middle] >= value) 中的等号去掉;

  2. if (right >= 0 && array[right] == value) {return right;}

问题4:找到第一个大于等于value的下标

在问题2中,我们的策略是让left刚好为第一个大于等于value的数的下标,而让right刚好为第一个小于value的数的下标。因此只需要去掉最后判断答案存在的array[left] == value条件即可。

问题5:找到最后一个小于等于value的下标

与问题4同理,去掉问题3中最后判断答案存在的array[right] == value条件。

B a+b(easy)

这题能卡我,题面也要背点锅。赛时的样例1输入为1 2输出为3. 而我又对位运算不够熟悉,在无论如何也找不到对应的x和y时陷入了自我怀疑之中。

题目本身确实很简单。取或运算可以看成不进位,只把每一位单独加起来。取和运算就看成每一位会不会进位(二进制加法只有进位/不进位两种可能)。那么加起来自然就与这两个数本身加起来相等。

C 百家姓与年龄

这道题题面看起来有点混乱……本来不复杂的描述参杂了3个人进来,还有两个人名字就差一个字母。当时愣是来回看了三四遍才明白意思。下次读题要冷静,快速排除无关信息。

读完题,把式子列出来一算就很显然了。令\(x\)为出生年份,\(y\)为排位。 \[ \begin{aligned} a&=50(2y+5)+1771-x\\ &=100y+2021-x \end{aligned} \] 联想到今年是2021年,\(2021-x\)为年龄,且年龄小于100岁。年龄即为\(a\)的最后两位数,排位为余下的数。

所以这道题的保质期已经不足两个月了。

所以居然是年龄小于100而不是百家姓排位小于100。

D 帮助小鱼

接下来 \(n\) 个数,第 \(i\) 个数代表第 \(i\) 个部长摸了那一条鱼。

又懵逼半天,这到底输入的啥。

最后就是开个桶或者map记录鱼被谁摸,然后顺序输出就好了。

E 上楼方式

整个比赛中做的最错误的决定就是第二个读这道题。

当时自己晚了3分钟开始(定了个开始前20分钟的闹钟,响了以后就坐在电脑前等,然后居然忘记定开场时的闹钟了),然后眼看着其他题都被人AC过了,这道题还没有。再加上有上楼梯这种经典递推板题的存在,我信 心 满 满地准备试一试。

这题怎么也有3个莫名其妙的名字。

然后就读错题了,3步登上教堂我想当然地以为是踩3阶楼梯。其实是指在楼梯上移动三次,比如1-2-3-4.

第一阶必定是1,最后一阶必定是\(n\),所以上楼方案数为 \[ C_{n-2}^2=\dfrac{n\times (n-1)}{2} \] 但是还有一个细节:不能直接对被除数取模。一个 workaround 是判断当前\(n\)的奇偶性然后先除后乘,避免溢出。

F 气球

先看两种买法折算的单价:

  • 3 * a < 2 * b:两件买法更优。这时最多可能买1个三件,因为买2个三件时显然不如买3个两件。
  • 3 * a > 2 * b:三件买法更优。这时可能买1或2个两件,买3个两件时就必定不如买2个三件。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int ans = 0;
if (3 * a < 2 * b) {
// choose 2
ans = a * ((n + 2 - 1) / 2);
if (n >= 3) {
ans = min(ans, a * ((n - 3 + 2 - 1) / 2) + b);
}
} else {
// choose 3;
ans = b * ((n + 3 - 1) / 3);
if (n >= 2) {
ans = min(ans, b * ((n - 2 + 3 - 1) / 3) + a);
}
if (n >= 4) {
ans = min(ans, b * ((n - 4 + 3 - 1) / 3) + 2 * a);
}
}

G zrgg出题

\(x\)个数中\(a_i\)的倍数的个数为:\(\left\lfloor\dfrac{x}{a_i}\right\rfloor\),容斥一下就可得到\([l,r]\)之间的倍数个数为\(\left\lfloor\dfrac{r}{a_i}\right\rfloor-\left\lfloor\dfrac{l-1}{a_i}\right\rfloor\).

但是需要注意,三个\(a_i\)之间有公倍数,这些公倍数被重复计算了,所以我们需要减回去。但是减回去的时候同时为三个数的公倍数又被多减了,所以需要再加回去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n, l, r, k;
int multiple_count(int a) {
return (r / a) - ((l - 1) / a);
}
void solve() {
cin >> n >> l >> r >> k;
int a[3];
int ans = 0;
for (int i = 0; i < k; i++) {
cin >> a[i];
ans += multiple_count(a[i]);
}
for (int i = 0; i < k; i++) {
for (int j = i + 1; j < k; j++) {
ans -= multiple_count(lcm(a[i], a[j]));
}
}
if (k == 3) {
ans += multiple_count(lcm(a[0], lcm(a[1], a[2])));
}
cout << ans << endl;
}

H a+b(hard)

基于B题的铺垫,可以直接想到把\(b_i\)\(c_i\)加起来得到 \[ d_i= \begin{cases} a_i+a_{i+1}&1\leq i<n\\ a_i+a_1&i=n \end{cases} \]\(2\leq i< n\)时,\(d_i-d_{i-1}=a_{i+1}-a_{i-1}\). 由\(n\)为奇数,得 \[ d_{n-1}-d_{n-2}+d_{n-3}-d_{n-4}+\cdots +d_{2}-d_{1}=a_n-a_1 \] 并且\(d_n=a_n+a_1\),所以可以直接求出\(a_1\). 之后就很简单了。

I 定向越野是世界上最好的运动

这题看起来就很吓人,有点让人无所适从。但是我们注意数据范围:\(2\leq n\leq 12\),时间限制3秒。这数据范围一看就是妥妥的NP问题,不是多项式时间能解决的。所以我们可以直接从比较暴力的思路想。

先看一个简化的问题:如果两人速度相同,那么问题可以转化成:经过所有点位(包括起点终点)且不重复走某个点位的最优方案。这样走出来的路径将是一个环,而我们从起点和终点分割这个环得到的就是两人的行走路线。这就是著名的“旅行商问题(Travelling salesman problem)”。我们可以使用状态压缩动态规划来求解。

啥是状态压缩呢?很简单,本来我们有\(n\)个点位,那么对于每个点位是否经过就一共有一个\(n\)维的状态,每个维度只能取经过/没经过两个值。那么现在我们可以用一个二进制数来对应一种状态,用0和1表示没经过和经过。这样就把\(n\)维的状态压缩成了一维。

定义\(dp(S,i)\)表示当前在点位\(i\),已访问点位集合为\(S\)​(用二进制表示)的最短路程,那么状态转移方程为 \[ dp(S,i)=\min\left\{d(S-\{i\},j)+dist(j,i)\mid j\in S\right\} \] 对于这道问题,我们只需要一点点适配:设没经过终点(最后一个点位)之前是第一个人A在走,经过终点回到起点时是第二个人B在走。那么修改求两点距离的函数\(dist(j,i)\)为此人走过这段距离所需时间即可。

CF1603A Di-visible Confusion

首先分析操作:决定一个数能否被删除的只有它的序号,因此删除某个数对它左边的数没有影响,而右边的数也不会关心具体是哪个数被删除了。所以,从右往左贪心删除一定是最优的方案。

题目问的是一个序列能不能被全部删除,所以我们就要找反面:从右往左贪心删除时会遇到所有数都无法被删除的局面。再联系刚才说了删除操作对左边的数没影响可知,如果一个序列前面某几项都被\((i+1)\)整除,那么这个序列必定无法被全部删除。即若第一项被\(2\)整除,整个序列必定无法被全部删除。

继续推广,如果第\(i\)项被\((i+1)!\)整除,那么整个序列必定无法被全部删除。由于阶乘的增长速度是很大的,而\(a_i\leq 10^9\),所以一旦阶乘超过\(10^9\)就不用看后面的了。

写出来一交,Wrong Answer.

上面推广的过程是错误的。应该把\((i+1)!\)换成\(LCM(2,3,\cdots,i+1)\). 把最小公倍数当成乘法这个操作在新生赛初赛中已经搞过一次,现在印象够深刻了。说到底,还是数论相关题目自己做得太少,知识也不牢固。

最大公因数(Greatest Common Divisor)

最大公因数的算法是辗转相除法,基于一个原理:如果\(a>b\)\(gcd(a,b)=gcd(b,a-b)\). 我们可以验证一下正确性 \[ \begin{aligned} a&=2^2\times 3^2\times 7=252\\ b&=2\times 3^3\times 5=270\\ b-a&=2\times 3^3\times 5-2^2\times 3^2\times 7\\ &=2\times 3^2\times (3\times 5-2\times 7)\\ &=2\times 3^2\times 1 \end{aligned} \] 两个互质的数相减,得到的数也和小的那个数互质(证明)。\(gcd(a,b)=gcd(b,a-b)=1\).

如果\(a-b>b\),那么就继续相减到\(a-b<b\)为止,所以直接\(gcd(a,b)=gcd(b,a\bmod b)\).

代码:

1
2
3
4
5
6
7
8
9
int gcd(int a, int b) {
int tmp;
while (b != 0) {
tmp = a;
a = b;
b = tmp % b;
}
return a;
}

最小公倍数(Least Common Multiple)

考虑两个数\(a\)\(b\),将这两个数分解质因数 \[ \begin{aligned} a&=2^2\times 3^2\times 7=252\\ b&=2\times 3^3\times 5=270 \end{aligned} \] 这两个数的最大公因数(Greatest Common Divisor)就是它们质因数的交集的乘积 \[ gcd(252,270)=2\times 3^2 \] 考虑最小公倍数的性质。最小公倍数必须被\(a\)\(b\)​整除,也就是说最小公倍数必须同时包含这两数的所有质因数,所以是它们质因数的并集的乘积。怎样得到这个乘积?\(a\times b\),然后容斥除掉共同的质因数\(gcd(a,b)\)就好了。 \[ \begin{aligned} lcm(252,270)&=\dfrac{252\times 270}{gcd(252,270)}\\ &=\dfrac{2^2\times 3^2\times 7\times 2\times 3^3\times 5}{2\times 3^2}\\ &=3780 \end{aligned} \] 实际编程中一般先除后乘,防止溢出。

代码:

1
2
3
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}

CF1601A Array Elimination

拿到题目简单分析一下:按位取AND,任意下标选择。所以其实数组的排列以及二进制下每一位整体的排列都不重要。由于取AND的性质,每次消去操作对于某一位来说要么消去\(k\)个1要么无影响。所以,实际上每一位内部0和1是怎样排布的也无任何影响。

那问题就很简单了,某个\(k\)能够单独消掉每一位的所有1,就等价于能消掉所有位。设第\(i\)位有\(n_i\)个1,则对任意\(i\)需满足\(k\mid n_i\). 也就是说\(k\bmod gcd(\{n\})=0\).

CF1515A Phoenix and Gold

从反面分析,假如现在有长为\(k\)的重量子序列使得\(\sum\limits_{j = 1}^{k}w_j = x\),那么要避免这种情况只需要从余下的重量中找出一个不等于\(w_k\)的重量替换即可。由于该子序列可以任意重新排列,所以只要子序列中任意两项不相等就一定可以找到符合要求的排列。综上,无法避免的情况为整个序列全部相等,且存在\(i\)使得\(\sum\limits_{j = 1}^{i}w_j = x\);或者此时已经没有可用于替换的重量了,也即\(\sum\limits_{j = 1}^{n}w_j = x\).

具体怎么实现呢?我又卡了。因为我没注意到这句话:

It is guaranteed that the weights are pairwise distinct.

所以其实只要看后一种情况是否出现就好了,否则都是可以的。我们从前往后加,如果遇到放不了的就先放它的下一个就好了。

我说为啥800难度的会这么复杂。

CF1515C Phoenix and Towers

不允许任意两个塔楼高度差严格大于\(x\),相当于不允许最高的塔楼和最低的塔楼的高度差严格大于\(x\). 联系\(1 \le h_i \le x\)的条件,如果高度差大于\(x\),超出的部分必定不止一个块。那么此时显然可以把多出来的那些块补到最低的塔楼上面。因此,不存在无法达到要求的情况。

然后就不知道怎么写了。

官方题解:上述那种情况是因为有一次或以上未把块加到当前最矮的塔楼上,因此只需一直贪心把块加到当前最矮的塔楼即可。

CF1606C Banknotes

某面值的钞票数量不能比较它更大一级的一张钞票能表示的还多 \[ 10^{a_{i+1}}>x_i\cdot 10^{a_i} \] 所以 \[ x_i\leq \frac{10^{a_{i + 1}}}{10^{a_i}} - 1 \] 所以我们只需要贪心给到\(x_i=\min(\mathit{left}, \frac{10^{a_{i + 1}}}{10^{a_i}} - 1)\),其中\(left\)是剩余可以分配的钞票数目。

CF1610C Keshi Is Throwing a Party

考虑从穷到富决策是否邀请第\(i\)个人,我们需要知道邀请后是否满足要求。我们从穷到富枚举所以前面有多少比他穷的人已经确定了,但是我们并不知道后面还会邀请多少比他富的人。所以这里还缺个信息:我们一共要邀请多少个人?这就又增加一个变量,整体时间复杂度达到\(O(n^2)\),我们需要用二分优化。

为什么呢?题目要求的是输出最大的能邀请的人数,而如果能邀请人数\(n\),那么也一定能邀请比\(n\)小的人数。所以人数是从0开始连续增大的(单调性),某人数下无法邀请那么比该人数还大时也无法邀请(局部舍弃性)。

P1439 【模板】最长公共子序列

这题虽然是个模板题,但是解法还是挺有趣的。

首先能想到的应该是DP(好吧这就是动态规划模板题)。注意到子序列不要求相邻。那么我们从前往后,分别枚举找两个序列的前 \(i,j\) 位的最长公共子序列,然后加上记忆化试试:

1
2
3
4
5
6
7
8
@lru_cache(maxsize=10000)
def LCS(i, j):
if i == 0 or j == 0:
return arr1[i] == arr2[j]
if arr1[i] == arr2[j]:
return LCS(i-1, j-1)+1
else:
return max(LCS(i-1, j), LCS(i, j-1))

(由于在准备蓝桥杯所以就用 Python 写了)

交上去以后发现不行,显然空间时间都是\(O(n^2)\),太大了。

如果转换成自底向上的for循环模式写,可以很容易优化一下空间。具体来说就是滚动数组,只把当前时刻需要的状态保留

1
2
3
4
5
6
7
8
dp = [[0 for x in range(n+1)] for y in range(2)]
for i in range(1, n+1):
for j in range(1, n+1):
if arr1[i] == arr2[j]:
dp[i % 2][j] = max(dp[i % 2][j], dp[(i % 2) ^ 1][j-1]+1)
else:
dp[i % 2][j] = max(dp[(i % 2) ^ 1][j], dp[i % 2][j-1])
print(dp[n % 2][n])

空间优化成了\(O(n)\),但是时间仍然是\(O(n^2)\). 有一半的测试点超时。

这时候算法本身已经没有什么好优化的了。但是你可能感觉有点奇怪,题目中有一个条件我们还没有用到

给出 \(1,2,\ldots,n\) 的两个排列 \(P_1\)\(P_2\)

这两个数列是排列数,也就是 \(1\)\(n\) 的每个数都出现且仅出现一次。

从我们上面提到的子序列的要求来看,如果 \(P_2\) 是单调递增的数列(也就是它的子序列一定是单调递增的),那么 \(P_1\) 中若有它的公共子序列,这个子序列显然得是单调递增的。结合 \(P_2\) 是排列数的条件,\(P_2\) 一定形如 \(\left\{ 1, 2, 3, \cdots, n \right\}\),所以 \(P_1\) 中单调递增的子序列就一定是这两个序列的公共子序列。

如何把 \(P_2 = \left\{ 1, 2, 3, \cdots, n \right\}\) 推广到更一般的情况呢?回到这道题中,注意到这里面的数字其实只是一个符号,我们完全可以用任何符号代替某个数字。也就是说,我们可以直接拿 \(1, 2, 3, \cdots, n\) 映射到 \(P_2\) 中对应位置的数字,然后把两个数列都按照这种规则替换。通过这种做法,我们人为地引入了单调性

这时候,问题就转化成了求 \(P_1\) 中的最长的单调递增子序列(longest increasing subsequence, LIS)。

LIS 怎么求解?最简单的方式还是直接 DP

1
2
3
4
5
6
7
8
9
10
11
@lru_cache(maxsize=10000)
def LIS(i):
if i == 1:
return 1
res = 1
for j in range(1, i):
if marr[j] < marr[i]:
res = max(res, LIS(j)+1)
return res

print(max([LIS(i) for i in range(1, n+1)]))

但是时间复杂度仍然是\(O(n^2)\),所以介绍一种\(O(n\log n)\)的算法。

设输入的数组为\(\left\{a_1, a_2, \cdots, a_n\right\}\),令\(A_{i,j}\)为在前\(i\)个数字中,长为\(j\)的上升子序列的末位之中的最小值。那么显然对于任意给定的\(i\)\(j<J_i\),有 \(A_{i, j}<A_{i, j+1}\).

我们现在枚举数组的第\(i\)位,假设我们要找以\(a_{i+1}\)为结尾的最长的上升子序列。很自然的想法是我们要把\(a_{i+1}\)附到它前面尽可能长的上升子序列的末尾。所以我们需要找到临界值\(j\),使得 \[ A_{i,j} < a_{i+1} \leq A_{i,j+1} (j \leq J_i-1)\\ A_{i,j} < a_{i+1} (j=J_i) \]\(a_{i+1}\)刚好可以附到\(A_{i,j}\)所代表的那个子序列末尾了。 \[ A_{i+1,j+1}=a_{i+1} \] 这时我们还发现,剩余的\(A_{i,k}\)要么已经比\(a_{i+1}\)小了,要么比\(a_{i+1}\)大即不满足单调性,因此对于\(k \neq j+1\)\[ A_{i+1,k}=A_{i,k} \] 怎样找到临界值\(j\)呢?由于\(A_{i,j}\)的单调性,我们直接二分搜索即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from bisect import bisect_left
import sys
def get_ints(): return map(int, sys.stdin.readline().strip().split())


[n] = get_ints()
a = [0] + list(get_ints())
b = [0] + list(get_ints())
map = [0 for i in range(n+1)]
for i, v in enumerate(a):
map[v] = i

f = []
for i in range(1, n+1):
pos = bisect_left(f, map[b[i]])
if pos == len(f):
f.append(map[b[i]])
else:
f[pos] = map[b[i]]
print(len(f))

P2419 Cow Contest

首先观察题目要求,可得排名可以确定的奶牛的定义为:如果奶牛 \(i\) 的排名确定为 \(r\) 则必定有 \(r-1\) 只奶牛与它直接或间接地比赛并获胜,\(N-r\) 只奶牛与它直接或间接地比赛并失败。

从定义直接想到,我们可以枚举奶牛(节点),然后递归找比它强的和比它弱的,如果两者数目加起来为 \(N-1\) 则满足要求。仔细思考一下,其实不需要递归,我们从入度为 0 和出度为 0 的点开始,累加途中的点并记录即可。

时间复杂度 \(O(1)\) ,分为感性认识和理性认识。

如无特别注明,下文所指均为二进制下的数位。按位逻辑运算符号表在此处

感性认识

由于 \(0\oplus 1=1\),问题也可以转化成求 \([1, n]\) 的异或值。

1
2
3
4
5
6
7
8
9
10
11
12
13
Number Binary-Repr  XOR-from-1-to-n
1 1 [0001] 1
2 10 [0011] 3
3 11 [0000] 0 <----- We get a 0
4 100 [0100] 4 <----- Equals to n
5 101 [0001] 1
6 110 [0111] 7
7 111 [0000] 0 <----- We get 0
8 1000 [1000] 8 <----- Equals to n
9 1001 [0001] 1
10 1010 [1011] 11
11 1011 [0000] 0 <------ We get 0
12 1100 [1100] 12 <------ Equals to n

所以我们可以这么写:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// C++ program to find XOR of numbers
// from 1 to n.
#include<bits/stdc++.h>
using namespace std;

// Method to calculate xor
int computeXOR(int n)
{

// If n is a multiple of 4
if (n % 4 == 0)
return n;

// If n%4 gives remainder 1
if (n % 4 == 1)
return 1;

// If n%4 gives remainder 2
if (n % 4 == 2)
return n + 1;

// If n%4 gives remainder 3
return 0;
}

// Driver method
int main()
{
int n = 5;
cout<<computeXOR(n);
}


// This code is contributed by rutvik_56.

理性认识

\(f(x,\ y)\)\(x\)\(y\) 的所有整数的异或值。

现在考虑 \(f(2^k,\ 2^{k+1}-1)\). 令 \(k\geq 1\),则 \(2^k\) 为偶数。且这里面的 \(2^k\) 个数从左往右第 \(k+1\) 位(最高位)都为 \(1\). 再结合异或运算法则我们就知道,将这 \(2^k\) 个数的最高位去掉,异或值不变。也就是说, \[ f(2^k,\ 2^{k+1} -1) = f(2^k - 2^k,\ 2^{k+1} -1 -2^k) = f(0,\ 2^k -1). \] 所以, \[ \begin{aligned} f(0,\ 2^{k+1} -1)&=f(0,\ 2^k -1)\oplus f(2^k,\ 2^{k+1} -1)\\ &=f(0,\ 2^k -1)\oplus f(0,\ 2^k -1)\\ &=0. \end{aligned} \] 也就是, \[ f(0,\ 2^k - 1) = 0\ (k >= 2). \]

对于 \(f(0,\ n)\ (n\geq 4)\) ,设 \(n\) 的最高位在第 \(k\)\((k \geq 2)\). 则 \[ f(0,\ n) = f(0,\ 2^k - 1)\oplus f(2^k,\ n) = f(2^k,\ n). \] \([2^k,\ n]\) 共有 \(n+1-2^k\) 个数,设为 \(m\). 这些数的第 \(k\) 位(最高位)共有 \(m\)\(1\).

(a)\(n\) 为奇数时,\(m\) 为偶数,则最高位有偶数个 \(1\) ,所以 \[ f(0,\ n) = f(2^k,\ n) = f(0,\ n - 2^k). \]\(n-2^k\)\(n\) 同奇偶,我们可以递推: \[ f(0,\ n) = f(0,\ n - 2^k) = f(0,\ n - 2^k - 2^{k-1}) = \cdots = f(0,\ n \bmod 4). \] 注:\(n\geq4\). 每一步递推都将最高位去掉。

\(n \bmod 4= 1\) 时, \(f(0,\ n) = f(0,\ 1) = 1\).

\(n \bmod 4 = 3\) 时, \(f(0,\ n) = f(0,\ 3) = 0\).

(b)\(n\) 为偶数时,\(m\) 为奇数,则最高位有奇数个 \(1\) ,所以 \[ f(0,\ n) = f(2^k,\ n) = f(0,\ n - 2^k) \vee 2^k. \] 注:最高位的 \(1\) 我们先提出来,最后用取或(\(\vee\))加回去。

(a)那样递推时,我们会发现每一步都保留了当前最高位,所以除了 \(n\) 的最后两位其余都会被保留下来,我们记这个数为 \(n'\). \[ f(0,\ n) = f(2^k,\ n) = f(0,\ n \bmod 4) \vee n'. \]

\(n \bmod 4=0\)\(n\) 的后两位是 \(00\),所以 \(n=n'\). \[ f(0,\ n) = f(0,\ n \bmod 4) \vee n' = f(0,\ 0) \vee n = n. \]\(n \bmod 4 = 2\)\(n=n'+2\),所以 \[ \begin{aligned} f(0,\ n) &= f(0,\ n \bmod 4) \vee n'\\ &=f(0,\ 2) \vee n'\\ &=3 \vee n'\\ &=3 \vee 2 \vee n\\ &=n+1. \end{aligned} \] 综上所述, \[ f\left( 0,\ n\right) =\left\{ \begin{array}{l} n&, n \bmod 4=0\\ 1&, n \bmod 4=1\\ n+1&, n \bmod 4=2\\ 0&, n \bmod 4=3. \end{array} \right. \] Q.E.D.

参考文献

  1. 求1到n这n个整数间的异或值 (O(1)算法)
  2. Calculate XOR from 1 to n - GeeksforGeeks (异或值表格及代码)
  3. 问题:求1到n这n个整数间的异或值,即 1 xor 2 xor 3 … xor n

这篇文章的起因是《算法导论》中的一段话:

"It may seem strange that dynamic programming relies on subproblems being both independent and overlapping. Although these requirements may sound contradictory, they describe two different notions, rather than two points on the same axis. Two subproblems of the same problem are independent if they do not share resources. Two subproblems are overlapping if they are really the same subproblem that occurs as a subproblem of different problems" (CLRS 3rd edition, 386).

这里的independent和overlap都是啥意思呢?下面是我查了StackOverflow以后得到的结果:

「独立」的意思是说:如果我们说一个解是最优的,那么这个最优的性质并不依赖任何我们要解决的母问题。也就是说不管我们是为了哪个更大的问题来解这个子问题,都会得到这个解。举个简单的例子:从A到B的最短路径经过C,那么我直接求从A到C的最短路径,后者答案应该是前者答案的一部分。这就是最优子结构(optimal substructure)的定义。

「重叠」的意思就很自然:不同的子问题会解多个子子问题,而其中很多子子问题是重复的。有意思的是由于我们刚才的「独立」性质,这些重复的子子问题就算有不同的母问题,他们的解也应该是相同的。因此我们就可以开个数组把这些解存下来。

最近有了在终端中SSH远程开发的需求,又想起之前看别人写代码时用Vim或Emacs灵活地在编辑器中定位,羡慕手不离开键盘的效率,于是决定好好学一下Emacs。

为什么选择Emacs

之前由于时不时需要在GNU/Linux里面编辑一些配置(比如配置vps),所以很简单地学了一下Vi的使用方法,但也仅限于会上下左右、会进Insert mode、会按:wq保存退出的水平。但是之前也听说过Emacs,所以我去搜了一下Emacs和Vim的区别和各自的使用场景,大致如下:

  • Vim和Emacs的运行环境不同。原版Vim只提供命令行界面(CLI, Command line interface),而Emacs提供GUI和CLI两种。这也侧面体现出不装插件的状态下Vim更像是一个记事本类的编辑器小工具,而Emacs倾向提供一套软件开发的环境。若在命令行下使用Emacs会有小部分功能缺失:部分快捷键被终端占据、浏览器无法显示图片、Emoji支持由终端提供等。
  • Vim相对Emacs轻量,内置的功能较少:Emacs内置了文件浏览器、Git客户端、终端甚至一个简单的浏览器。所以使用Emacs写代码很大程度上是“开箱即用”的,最多只需要装一些自动补全相关的插件。而Vim只有基本的编辑功能,所以若不自行安装插件功能性就差一些。
  • Vim和Emacs的操作方式不同。Vim使用三种模式,以使用户在大多数时候避免使用组合键。但与此同时在各个模式间切换也增加了时间成本。Emacs则只有编辑模式,组合键的使用非常普遍,使用过程中经常需要按Ctrl/Command键(可以通过按键映射将大小写和Ctrl互换以减轻小指压力)。不过,现在很多人选择使用evil插件来在Emacs中实现Vim的编辑模式,反过来似乎也有。
  • Vim的扩展性不如Emacs。Vim的插件采用Vim Script编写,Emacs的插件采用Emacs Lisp编写。Lisp起源于1958年,是当前广泛使用的编程语言中最老的之一。再加上Emacs的GUI提供的自由度,你可以通过安装插件在Emacs中收发邮件、听音乐甚至剪辑视频。而在语言支持相关的插件方面两者都非常完善了。

看到Emacs有这么多功能,再加上以前对Lisp有所耳闻,最后决定学Emacs。

学习路线

  1. 看官方Tutorial(有中文翻译版)
  2. 打印Reference Card,时不时看一遍。遇到某个键忘记了就速查。
  3. 尝试逐渐将日常开发切换到Emacs上,逐渐形成肌肉记忆

一些知识点

有些知识点Tutorial没有讲到或者讲了但是我没完全理解,在此记录一下。

Buffer和Window

刚看完tutorial的时候一直没搞清楚buffer和window的关系是什么,后面发现关键是Emacs的一个设计思想:数据与UI解绑。我们通常使用Visual Studio Code这类编辑器的时候都是一个正在编辑的文件(数据)对应一个打开的窗口。但是Emacs不是这样。正在编辑还未保存的文件内容和buffer对应,然后一个frame中显示的区域和window对应。

背景知识

Visual Studio Code 与 Visual Studio、IDEA 等有着本质上的不同:前者为文本编辑器,而后者为 IDE(集成开发环境)。IDE 以语言为中心,为语言打造最贴身的开发工具,而编辑器只负责编辑,其他的功能都得由插件实现。但是编辑器相对于 IDE 来说

  1. 更加轻量、快速,尤其是存储空间上二者甚至能差好几个数量级。
  2. 跨语言开发时能最大限度地保留写代码的习惯。
  3. 底层原理对使用者更透明,有利于新手了解编译等过程。

准备工作

  1. 安装 Visual Studio Code

  2. 转到 VS Code 侧边栏中 Extension 这个 tab,搜索安装插件 适用于 VS Code 的中文(简体)语言包

  3. 安装插件 C/C++ Extension Pack.

  4. 下载编译好的 Mingw-w64 工具链(包含了最新的 GCC C++ 编译器)。

配置 MingW

  1. 7-Zip 或其他解压软件解压下载的 Mingw-w64 工具链,将 mingw64 复制到 C 盘根目录下。
  2. 按下组合键 Win+R,输入 sysdm.cpl,选择高级 - 环境变量,在系统变量下找到 Path 这一行双击。
  3. 点击新建,输入 C:\mingw64\bin 。然后一路确认。
  4. 按下组合键 Win+R,输入 cmd,在命令行中输入 gcc --version 并回车,查看是否成功显示 gcc 版本。

Side note: 为什么要这样做?

刚才你将 mingw64 的可执行文件(binary)目录添加到了环境变量 PATH 中。在cmd等终端下运行可执行文件时,如果在当前目录找不到这个名称的文件,命令行就会自动从上到下在 PATH 环境变量中的目录寻找。这样,即使编辑器不知道我们把 mingw 放在哪里,也可以正常运行编译命令。

配置编译生成

  1. 打开 VS Code,点击打开文件夹,并选择一个你想存放代码的文件夹。

  2. 新建配置文件夹 .vscode,新建 tasks.json 保存如下内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
{
"tasks": [
{
"type": "cppbuild",
"label": "C/C++: g++.exe build active file",
"command": "C:\\mingw64\\bin\\g++.exe",
"args": [
"-fdiagnostics-color=always",
"-g",
"${file}",
"-o",
"${fileDirname}\\${fileBasenameNoExtension}.exe"
],
"options": {
"cwd": "${fileDirname}"
},
"problemMatcher": [
"$gcc"
],
"group": {
"kind": "build",
"isDefault": true
},
"detail": "Task generated by Debugger."
}
],
"version": "2.0.0"
}
  1. 新建一个文件,命名为 helloworld.cpp,并保存如下代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    #include <iostream>
    #include <vector>
    #include <string>

    using namespace std;

    int main()
    {
    vector<string> msg {"Hello", "C++", "World", "from", "VS Code", "and the C++ extension!"};

    for (const string& word : msg)
    {
    cout << word << " ";
    }
    cout << endl;
    }
  2. 此时按下 Ctrl+Shift+B 或者点选 终端 > 运行生成任务,您可以看到 终端 选项卡弹出,并自动执行编译命令。

  3. 用 + 按钮新建一个终端窗口并运行 .\helloworld.exe,此时您可以看到 Hello World 信息。

配置调试

  1. 在顶部菜单栏,选择运行 > 添加配置... > C++ (GDB/LLDB).

  2. 粘贴如下内容至打开的 launch.json:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
{
"version": "0.2.0",
"configurations": [
{
"name": "C/C++: g++.exe build and debug active file",
"type": "cppdbg",
"request": "launch",
"program": "${fileDirname}\\${fileBasenameNoExtension}.exe",
"args": [],
"stopAtEntry": false,
"cwd": "${fileDirname}",
"environment": [],
"externalConsole": false,
"MIMode": "gdb",
"miDebuggerPath": "C:\\mingw64\\bin\\gdb.exe",
"setupCommands": [
{
"description": "Enable pretty-printing for gdb",
"text": "-enable-pretty-printing",
"ignoreFailures": true
}
],
"preLaunchTask": "C/C++: g++.exe build active file"
}
]
}
  1. 鼠标移动到行数指示器左侧,您可以看到红色圆点,单击后即为在该行下断点。调试时程序会运行到这一行前并停下。

    请在第 9 行下断点。

  2. 按下 F5 或者点选 运行 > 开始调试,这时候您可以看到程序在第 9 行停下,请自行探索窗口上部出现的调试工具。

进阶设置

插件

对自己学习成果的评价

2021年高考结束了,结果也已经大体尘埃落定。我终于不得不面对自己的一个个选择所带来的命运。在反思高中学习过程的时候,我发现一个重大问题。我基本上一直用这三个假设面对学习:

  1. 一个人生来就必定有一个其擅长学习的知识领域。
  2. 只要选取了正确的学习方法,艰涩的知识也会变得简单。
  3. 一个人想要检验自己的学习成果,只需扪心自问自己是否真正理解了这些知识。

在追溯这三假设的来源之前不得不说,这三条假设写出来一看真是错得离谱。第一条根本没有任何科学实验证实,因为「擅长学习」本来就是未定义的。当然在这里不是,因为已经被第三条定义了。第二条虽说看起来没什么问题,但是仔细一想就会发现:各种学习方法之间的学习效果根本没有纳入考量的范围内(就算考量投入产出也会用第三条吧)。难道单凭「简单」就算是正确的学习方法吗?第三条是最离谱的:「扪心自问」能问出什么来?是10%的理解还是50%的理解又或者是100%的理解?更不用说对于「是否理解」这个问题本身就是完全主观的。我今天觉得理解了,很可能明天忘了一部分又或者看到一道难题,就又觉得自己不够理解。如此糟糕的评价标准还支撑着另外两个假设,这直接就让我这整一套学习假设彻底地失败了。

然而不幸的是,我一年多来一直秉持着这样的态度指导自己的学习。原因很简单:学习本来就是一件很艰辛的事情。无论是3Blue1Brown做的可视化科普视频,还是费曼对物理学的精彩表述,都只不过是科学自身美感的表现。问题在于学生的目的是成为那个画家(不论其能不能画出名画),而不是名画前的观众。能欣赏一幅画自然能激发一个人学习画画的决心,但是如果他只想着欣赏别人的画作却懒得自己动笔,他永远也当不了画家。而我以前正是这样的人。每个人没有外界附加条件下,都会默认选择懒惰、舒适。结果我就走进了我给自己树立的那三条互相佐证的圈子里,在没认清形势之前,面对别人的劝说一时走不出来了。

至于这三条假设是怎么形成的,我也已经说不清了。事实上这并不是那一天忽然听说或想到的,只是长期的心理暗示的结果。从高二开始我就乐于在网上看各种优质的科普视频(是的很优质,但它终究还是科普)以及自己探究各种难以理解的物理概念。但不止这点。我之前或许也提到过,我很看重「自我认同」,并且觉得这是解决一切内卷问题的良药。那种所谓的,一个人只需要认清楚自己的人生价值并为之努力,即便是粗茶淡饭也「不改其乐」的You only live once(你只活一次/及时行乐)的思想深深影响了我。这就是我把「扪心自问自己是否理解」当成评价标准的根源:我讨厌追求那些「世俗的」分数,因为那些都是身外的评价。但是我却没意识到,「自我」也是会变化的,就像是一年前这时候的自己肯定也想不到有一天他会因为高考和大学这种「世俗的事情」而发愁吧。现在我明白,生活不是一条笔直的单行道,而是一个复杂的、永远都在自我折叠的迷宫。

那么以后如何防止这样的情况呢?其实很简单:多审视自己对自己的评价方式,仔细分析这样的评价方式是否可靠:是否有较高的稳定性?在各种情况下能不能保持一致?是不是正在循环论证,让自己自我感动?

对效率的追求

现在想起来,我在高中时期考试时的速度和平时写题的速度之间差异巨大。尤其是理科以及文科的作文。为什么会这样呢?原因无非就是我注意力不集中,精神涣散。但是高三后期考试考多了,考年级内的周测都开始逐渐放松下来。

对远景目标的敏感度

如果回到刚入高三时一个我不想写作业的下午,我可能会劝那时候的自己:你一年以后就要高考了!可是这多半是徒劳的,因为当时我是这么看待这个问题的:高考是远在一年后的事,而眼下我不要两个小时就能折腾完这个平板,这么微不足道的小事又能引起什么后果呢?

这就又是一个我的问题:对远景目标的敏感度低。

对某件事是否值得做的评估

我也打着「为了自己好好学习」的名号做过很多事情:额外买了台平板,说要拿来在家里看网课和课件;破解平板,说是让自己查资料;逆向平板教学App,说是让自己能在别的手机平板Kindle上随时随地学习。然而,这些事情基本上都没按照预想的方向发展。其实当时的自己并不是不知道这些可能的后果,但是就是有意无意忽略了这些。

Wer mit Ungeheuern kämpft, mag zusehn, dass er nicht dabei zum Ungeheuer wird. Und wenn du lange in einen Abgrund blickst, blickt der Abgrund auch in dich hinein. 与恶龙缠斗过久,自身亦成为恶龙; 凝视深渊过久,深渊将回以凝视。

——Friedrich Wilhelm Nietzsche(弗里德里希·威廉·尼采)

对于是什么时候初次见到这句话,我的印象已经很模糊了。无论如何,写故事的人们很喜欢它。原因当然有很多,但是首当其冲的自然是吸引人的眼球了。然而这桥段如此惯用,以至于慢慢变得老套和稀松平常而甚至成为一个梗。这又何不是有些讽刺的自指呢。

然而无论如何,这既然被人写在小说里面,那么它必然是人们心目中关于“真实”的投影。小说必须在某种方面遵循我们心目中的真实感,而最真实的“现实”如何发展却常常与我们的猜测相悖。那么,这句话究竟想说什么?我们如何看待这句话呢?

先进行话语分析。这句话属于很直白的相关关系:屠龙与成为恶龙成正相关关系。

下面先贴一个最直白的解释:

龙被勇士杀死,说明勇士已经拥有乃至超过恶龙的力量,一旦勇士因为该力量而堕落,那么他将成为另一条恶龙。

这句话蕴含了辩证的思想,某种程度上揭示了勇者与恶龙的故事能长期延续的一种可能。

(来源萌娘百科,采用知识共享(Creative Commons) 署名-非商业性使用-相同方式共享 3.0 协议授权。)

这里让我不满意的地方是:所谓“力量”在绝大多数语境下是“单向”的。也就是说,你拥有力量后除非发生很重大的事故,否则力量就是只增不减的。推广这个概念显得有点困难了。

我的建议是:不妨退一步想想,为什么要屠龙呢?参考大多数写法,无非就是这条龙有意无意地造成了对人的合法权利的侵犯(至于合不合法当然是人类自己制定啦),比如气候异常(不够环保)、侵害生命权财产权之类的。那么为了维护合法权利,人类只有想办法把龙给杀了这一条路可以走(也许吧)。一句话概括:解决有问题的龙就是解决问题。那么最终,那个反对龙侵犯他人合法权利的人也开始侵犯他人合法权利了。这个转折就留下了很大的操作空间:好端端的为啥去做自己本来反对的事呢?故事要写下去得给加个因果:因为拥有力量(使能侵犯他人权利)而反转?(这是必要条件而不是充分条件吧)因为屠龙的过程或者对龙进一步的认识而反转?

不对,这些明明是小说家要考虑的问题。不妨跳出成为恶龙的具体因果而思考促成这转变发生的外部因素。回到这句话:

解决有问题的龙就是解决问题。

现在的结果不正是解决有问题的龙根本无法解决问题吗?再结合屠龙者自身作前后对照,侧面反映一件事:龙也许不是问题的关键!那么这就是我的答案:龙不是问题所在,而是问题的一种外在表现形式。而当屠龙者屠龙时就是用抑制问题的外在表现来表面上解决问题。最后一步,屠龙者变成恶龙,也就是说我们得从这变换里找一个不动点。显然有且仅有一种可能:“抑制问题的外在表现来表面上解决问题”就是问题所在!

用最通俗易懂的方式概括,其实只有一句话:反对形式主义,也是一种形式主义。(解释:如果只是喊着反对口号而不去考察形式主义深层次的原因,那么这口号就是一种形式主义)

有趣的是,这两句话看上去是我上面生拉硬扯在一起的,然而在各种小说影视桥段中你都能看到形式主义的身影。

中国古代改朝换代时,起义者杀死统治者取得权利,又变为新的统治者,开始循环。

人类因为对地球的破坏而受到所谓神明的惩罚,却以为只要把神明搞定就可以继续挥霍后代将求之不得的资源。

(想到了再补充)

本文意在简要说明搭建博客的过程,前面会有一些关于基本概念和运作原理的介绍。如果你已经有了一定的背景知识,可以跳到后面阅读。

博客怎样工作?

这个博客最早搭建于2019年9月7日。当时我还没有一台能长期开机的服务器(其实现在也没有),所以无意间看到 Hexo 这个博客引擎就被吸引住了,按着说明文档自己一步步搭了下来。其实搭建过程并不需要什么编程知识,只是需要充分的时间和耐心,以及遇到问题就去搜索引擎的反应。为什么 Hexo 的运作不需要服务器呢?其实 Hexo 只干了一件事:把编辑器输出的Markdown文档(Microsoft Word虽然也是这一类文件,但是不被Hexo支持)转换成HTML 5网页(包括HTML、CSS、JavaScript)。而这些网页从此就算「独立」了:不需要与生成它的那台机器相连接,它自己就能在任何能打开它的浏览器上工作,也不需要在任何服务器上运行代码。所以,我们只需要给这些网页找一个「网盘」(前提是得支持Http连接),就能通过访问这个网盘打开网页了。「网盘」也叫静态网站托管服务、OSS等,我使用的 GitHub Pages 就是其中之一。它是完全免费的。

但是需要一台电脑安装Hexo和相关的依赖,并在文章更新时运行一次生成、上传到GitHub还是让你觉得很不爽,怎么办?有没有免费运行Hexo的服务?还真有,那就是这篇文章要说的 GitHub Actions。

在本地计算机配置 Hexo 及主题

  1. 请参见 Hexo 文档 安装 Hexo,并新建一个 Hexo 网站。
  2. 之后在网站根目录下运行 hexo server,此时访问 http://localhost:4000/,你此时应该能访问一个简单的博客网站。
  3. 安装 NexT 主题npm install hexo-theme-next
  4. 找到node_modules/hexo-theme-next/_config.yml并复制到 Hexo 目录并重命名为_config.next.yml文档
  5. 按照文档编辑_config.yml
  6. 继续按照文档编辑_config.next.yml(注意此时文档中的next/_config.yml应视为_config.next.yml

(可能有些太简略了,待补充)

现在,你已经成功配置好自己的个人博客,在命令行执行hexo server即可在本机上运行博客。下一步就是把博客托管至GitHub了。

将博客托管到 GitHub Pages

  1. 首先你需要登录自己的 GitHub 账号。如果没有 GitHub 账号,请使用邮箱注册一个。注意,注册时请选一个理想的用户名,因为这将成为你博客域名的一部分:[username].github.io

  2. 然后新建一个 repository,repository name填入[username].github.io(username即为注册时填入的用户名),其余保持默认。

  3. 参考此处配置 Git 用户信息。请使用你在注册 GitHub 时提供的邮箱和用户名。

  4. 配置 Hexo 以将博客部署至 GitHub。打开_config.yml并找到下面这块配置(注意编辑repo中的<username>)(文档

    1
    2
    3
    4
    5
    deploy:
    type: git
    repo: https://github.com/<username>/<username>.github.io
    # example, https://github.com/hexojs/hexojs.github.io
    branch: gh-pages
  5. 运行 hexo clean && hexo deploy ,输入 GitHub 用户名和密码。

  6. 进入repository页面,点击 Settings - pages,确保已启用 GitHub Pages。此时https://<username>.github.io应已可以访问。

使用 GitHub Actions 部署博客

  1. 登录GitHub,再新建一个repository。名字可以自己取,我的是blog-source

  2. 新建文件博客目录/.github/workflows/deploy.yml,内容如下:(注意替换<username><useremail>

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    name: Deploy blog to Github
    on: [workflow_dispatch]
    jobs:
    build:
    runs-on: ubuntu-latest
    steps:
    - name: Checkout
    uses: actions/checkout@v1
    - name: Checkout GitHub Pages repository
    uses: actions/checkout@v2
    with:
    repository: '<username>/<username>.github.io'
    path: '.deploy_git'
    - name: Setup Node.js environment
    uses: actions/setup-node@v2-beta
    with:
    node-version: '12'
    - name: Install pandoc (Latex support)
    run: |
    wget -O pandoc.deb https://github.com/jgm/pandoc/releases/download/2.13/pandoc-2.13-1-amd64.deb
    sudo dpkg -i pandoc.deb
    - name: Setup Hexo environment
    run: npm install

    # 从之前设置的 secret 获取部署私钥
    - name: Set up environment
    env:
    DEPLOY_KEY: ${{ secrets.DEPLOY_KEY }}
    run: |
    sudo timedatectl set-timezone "Asia/Shanghai"
    mkdir -p ~/.ssh
    echo "$DEPLOY_KEY" > ~/.ssh/id_rsa
    chmod 600 ~/.ssh/id_rsa
    ssh-keyscan github.com >> ~/.ssh/known_hosts
    git config --global user.email "<useremail>"
    git config --global user.name "<username>"
    # 生成并部署
    - name: Deploy
    env:
    MESSAGE: ${{ format('Site updated {0}@{1}', github.repository, github.sha) }}
    run: |
    npx hexo deploy --generate --message "$MESSAGE"
  3. 修改博客目录/.gitignore在最后一行添加package-lock.json

  4. 在博客目录下运行

    1
    2
    3
    4
    5
    6
    git init
    git add --all
    git commit -m "first commit"
    git branch -M main
    git remote add origin https://github.com/<username>/blog-source.git
    git push -u origin main
  5. 生成SSH密钥:ssh-keygen -f hexo-deploy-key一路回车即可
  6. 记事本打开 hexo-deploy-key.pub ,将里面的内容设置为仓库<username>.github.io的部署密钥(Settings > Deploy keys)
  7. 在仓库blog-source的 Settings > Secrets 中新增一个 secret,命名为 DEPLOY_KEY,把私钥 hexo-deploy-key 的内容复制进去。
  8. 最后点击blog-source的Actions > Deploy blog to Github > Run workflow

参考

最近刷新了对小说的认知。

之前不喜欢,甚至鄙视小说,是觉得它连篇累牍,信息密度小。篇幅长,可主旨就几句话,看起来总不如议论文之类的舒服。可事实上小说的信息量并不一定比论述文小,这种错误的认知是源于对小说底层逻辑的不理解。

世界上有两种问题:一种是越研究越觉得它简单、连贯的,另一种是越研究,越显出其复杂的。而这两种问题有时候还能围绕着同一件事物:我们目前对气体分子运动的研究已经很详细了,也已总结出描述这些现象的很准确的定律。这就是越研究越简单的问题。但是我们现在仍然无法准确地预计天气,因为气体分子数量实在太多了。即使初始条件稍微有那么一丝偏差,最后的结果都会截然不同。这就是越研究越复杂的问题。

小说实际上就是对后者的研究。例如,对于「祥林嫂死了」这个事实我们会问:她为什么死了?她怎么死的?对这样的问题的一个回答是:因为封建社会对她的迫害,以及人们的冷漠无情。但是还有另一种回答思路:是因为她无依无靠、走投无路。那么为什么她处于这种境地呢?是因为她改嫁了,李四老爷忌惮她。那么为什么她改嫁了?……继续问下去,我们会得到这部小说的倒序的情节。那么,前一个回答比后一个回答好吗?恐怕不是。

小说正是这样:它是对于这个世界复杂性的承认。它的底层逻辑是:对一件事的来龙去脉的还原比匆忙地给这件事定性、下结论有更大的价值。因为我们身处的这个世界本就是复杂的、由无数的因果交织构成的。

所以,下次想要在小说的字里行间中不耐烦地搜寻「主旨」时,请先等一等吧。把一件事捏成想要的形状,然后将它放在论点的后面充当论据,并不是小说的目的。恰好相反,小说认为对于一件具体的事情的追问,对于事实的探寻,本身就是「主旨」所在。


关于小说,最近还看到不少有趣的说法。陈列如下:

Q:小说都是人编造出来的故事,那么既然如此,我为何不看真实的历史、纪录片之类的?为什么要看一个主观的、被精心编造出来的东西?

A:有关于小说的一个很有趣的地方在于:小说总是从某种角度追求贴近作者对于「真实」的那种认知,但是最「真实」的现实却丝毫不理会我们是怎么理解它的!一个新奇的剧情被用得多了就会变得老套,而现实却时刻让我们感到「魔幻」。所以,从某种意义上来说,小说不追求跟现实100%一致,而是反映我们对于真实的认知。我们大可不必要求绝对的客观。毕竟,无论以什么样的形式呈现现实,都只呈现了现实的一部分。

0%