LWLAymh的备忘录

为啥这篇文章总是传不上去???

为啥这篇文章总是传不上去???

事情是这样的,几天前,我们班被出了这么一道物理思考题(为表述方便略有简化).

有一辆以$v_0$行驶的质量超级大的火车,上面站了一个质量为$m$的人随火车一起运动.突然，这个人相对于火车以$\Delta v$的速度向前平跳(也就是说此时他相对于地面的速度为$v_0 + \Delta v$),求这个人做这个起跳需要多少能量.

注意这里火车质量很大,所以火车在此人跳跃过程中始终以$v_0$速度前进.

我看到这个题觉得很简单啊,肯定是$\frac{ m }{ 2 } ( ( v_0 + \Delta v )^2 - v_0^2 )$.然后发现答案竟然是$\frac{ m }{ 2 } ( \Delta v )^2$.

下面是我们物理课代表给出的解释:

虽然人的动能变化确实是$\frac{ m }{ 2 } ( ( v_0 + \Delta v )^2 - v_0^2 )$,但是在他起跳的过程中,火车对他是有一个力的.而且,因为火车在运动,所以虽然起跳的时候人相对于火车没有运动,但这个力的作用点相对于地面竟然是运动着的!

因此,不妨设这个力为$F$,注意这里的$F$不一定是常数,而是一个关于时间$t$的函数,我们自然有:$W = \int_{ t_0 }^{ t_1 } Fx \text{ d } t$,注意到作用点的速度恒为$v_0$,因此$W = v_0 \int_{ t_0 }^{ t_1 } F \text{ d } t = v_0 \Delta p = v_0 \Delta vm$,把这个加上后恰好得出答案.

这时我意识到这个事情其实就等价于任何惯性参考系参考下能量都是守恒的.所以我们直接以火车为参考系,立即得出答案.

但是为啥呢?而且我总觉得上面那个力的分析非常诡异,因为我总感觉起跳是瞬间的,这个力理论上不应该做功啊.

通过在网上海量搜索后,我大概找到了这么两种理解方式啊.

第一种是,我们冷静一下.如果没有外力干扰,那么火车其实并不能匀速前进.设火车质量为$M$,当人的速度为$v_0 + \Delta v$的时候,根据动量守恒,火车的速度应该为$v_0 - \frac{ m }{ M } \Delta v$.

注意这个时候不能以火车为参考系了,因为火车不再是惯性参考系了,所以我们加入一个以$v_0$匀速前进的青蛙作为新的参考系.不难发现在青蛙参考系和在地面参考系下,火车和人的系统的动能增量是相等的,都是$\frac{ 1 }{ 2 } ( m ( \Delta v )^2 + M ( \frac{ m }{ M } \Delta v )^2 )$.

然后,因为火车质量非常非常非常大,我们注意到$\lim_{ M \rightarrow + \infty } \frac{ m }{ M } \Delta v = 0$,完活.

但是这个过程别说还是进行了近似估计了,就是和现实也不符啊.你火车肯定要有动力来源使得其能进行匀速直线运动.但是这个理解方式的优越性在于,它试图将火车和人视作一个系统来观察,这个角度下我们完全不要去管二者分别的动能了,而是直接分析系统动能.

所以我反思了一下为什么我觉得一开始的那个做法很奇怪,我注意到对人做功的力同时一定对火车作负功,那么也就是一定还有一个对火车作正功的外力,这个力同时也是整个系统的外力.

对这个施加在火车上的外力进行完全一样的分析,就可以得到相同的答案.

或者更一般地,我们来证明惯性参考系下的所需要的能量恒定:

我们已知:

要证:

而注意到:

这就证明了该结论!

不过这个做法虽然相当理性但是一点都不直观啊,为什么两个平方竟然可以在这里线性加减,我其实还是没找到更加易于理解的方式啊,如果有大佬知道可以联系我一下qwq

哦哦我突然瞎想出了一个相当简洁的方式啊,就是我们不难注意到只要满足动量守恒以及做功的方程$W = Fx$,我们很自然可以推导出动能差的表达式,而这两个基础的表达式都是线性的,因此动能差也一定与选取哪个惯性参考系无关!

换句话说,这个动能差的表达式中的平方是我们积分积出来的,但是积分是可以加减的!

在大半夜和Querainy 和Minuses 深入交流之后,我发现上面的过程还是太感性理解了,我们来添加一些细节.

首先,Minuses 提供了在宏观下动量定理和牛二等价的证明(他原本的形式用的全是向量,但是我比较懒,所以换成一维情况了):

然后,他又提供了只要有牛顿第二定律和$W = Fx$的定义,我们就可以推导惯性参考系下动能定理的证明:

Minuses 无敌,可让天下一先.

Querainy提出我之前的说法是错误的,因为在不同参考系下牛顿第二定律的确不会有影响,但是$W = Fx$是受到了影响的.例如在上面的例子中,如果以火车为参考系,那么火车与人之间的力对人是没有做功的.但是以地面为参考系,那么这个力因为作用点在变所以是做功了的.

然而这个做功的改变在上面的积分形式中就可以发现,由于速度的改变导致平方项不能完美消除,因此这个做功的改变会抵消切换参考系(伽利略变换)带来的动能形式的改变.

这个自我修正bug看上去相当诡异,但是一想到动能定理本身就是从$W = Fx$和牛顿第二定律推导出来的,因此有自洽性也非常合理.

追根溯源看上面整个问题,我们会发现,如果我们换参考系然后看动能,动能的变化量的确是不一样的.

但是问题在于,我们在意的不是动能的变化量,而是我引起这个变化需要外加多少能量.如果我引起这个变化所需要外加的能量不变,那么就仍然满足能量守恒定律.

如果我们换参考系,动能的变化量改变,但是同时原本不做功的力也会随之进行做功.事实上由于力的作用点最多只在一个惯性参考系下才是静止的,因此换参考系几乎一定会引起力的做功.

所以我们其实还可以再举一个类似的例子:

考虑一个劲度系数为$k$的弹簧连在地上,上面放了一个重物$M$,我们来观察一下这个东西.

不妨取重物放上弹簧后的平衡位置为重力势能和弹性势能的零点,设弹簧原长位置相对于此位置距离为$x_0$,此时当然有$kx_0 = Mg$那考虑系统的弹性势能:

重力势能:

那么总势能当然是:

时隔不知道多长时间,现在我们来证明柯尼希定理:质点系在参考系$A$中的总动能等于质点系在质心系中的动能与质心在参考系$A$中的动能之和.

不妨设质心系下质点系的总动能为$E_{ kS }$,参考系$A$下的总动能为$E_{ kA }$,质心相对于$A$参考系的速度为$\vec{ v }_C$,我们当然有:

那这就给出了一个更强的结论,而且这里的质心参考系甚至不需要是惯性系.

今晚学弟问了我这么一个问题:

对于一个圆锥摆,设其绳上拉力为$T$,我们有:

那么问题来了:当小球自然下垂的时候,$T = mg$,但是$\omega = 0$,左边不等于右边???

怎么处理这个问题呢?

下面是我个人的想法啊,不一定正确.

冷静一下,$\omega = \frac{ v }{ r }$,我们的确能确认自然下垂的时候$v = 0$,但由于$r$也是$0$,我们没道理判定$\omega = 0$.

那么我们把角速度换成线速度就有:

这样极限情况下两边就相等了(均为$0$).

或者说我们还可以这么干:

考虑$T = \frac{ mg }{ \cos \theta }$,所以$\omega^2 = \frac{ g }{ L \cos \theta }$,注意到其实$\omega$是随着小球下落而单调递减的,但是不可能减到$0$.

另一个想法是:考虑先放一个实体圆锥(可提供支持力),让球在圆锥上转圈,然后逐渐加速到支持力$N = 0$,此时小球会飘起来.我们观察一下这个式子是啥:

考虑引入离心力,只需要让离心力,重力,支持力和拉力四力平衡即可,设绳子与竖直方向的夹角为$\theta$,作正交分解后立刻有:

替换掉其中的$N$,得到:

考虑$T$和$\omega^2$的函数关系,小球从在圆锥摆上的状态到飘起来的状态应该是连续的两段直线,注意到当$\theta \rightarrow 0$的时候,它俩的关系是$T = mg$的平行于$\omega^2$轴的直线,这段直线会一直延伸到$\omega$的最低点,也就是$\omega = \sqrt{ \frac{ g }{ L } }$的点然后再转上去.

如果这个文章就这么结束还是有点无聊,不如让我们来看个类似的问题:

先来看第一问:

设水平向左为正方向,设小球相对于滑块的水平速度为$v_1$,滑块速度为$v_2$.

水平方向动量守恒,当然有$m ( v_1 - v_2 ) = Mv_2$.

此时小球的总速度应该为$v = \sqrt{ ( v_1 - v_2 )^2 + ( \frac{ v_1 \sin \theta }{ \cos \theta } )^2 } = v_2 \sqrt{ ( \frac{ M }{ m } )^2 + \frac{ ( M + m )^2 \sin^2 \theta }{ m^2 \cos^2 \theta } }$.

小球和滑块的总机械能守恒,当然有:$\frac{ 1 }{ 2 } mv^2 + \frac{ 1 }{ 2 } Mv_2^2 = mgR \cos \theta$.

两式联立,解得:$v_2 = \sqrt{ \frac{ 2 m^2 gR \cos \theta }{ ( Mm + M^2 ) + ( M + m )^2 \tan^2 \theta } } = \sqrt{ \frac{ 2 m^2 gR \cos^3 \theta }{ ( m + M ) ( M + m \sin^2 \theta ) } }$.

看上去只是麻烦而已,也没那么难嘛.

再来看第二问:

考虑$a_n = \frac{ ( \frac{ v_1 }{ \cos \theta } )^2 }{ R } = \frac{ v_2^2 ( M + m )^2 }{ m^2 R \cos^2 \theta } = \frac{ 2 g ( M + m ) \cos \theta }{ M + m \sin^2 \theta }$,

而滑块的水平加速度大小应该是$a ‘ = - \frac{ N \sin \theta }{ M }$,那么惯性力$F ‘ = - a ‘ m = \frac{ mN \sin \theta }{ M }$.

而$a_n m = N - mg \cos \theta + F ‘ \sin \theta$,$\frac{ M + m \sin^2 \theta }{ M } N = ma_n + mg \cos \theta = \frac{ 2 gm ( M + m ) \cos \theta }{ M + m \sin^2 \theta } + mg \cos \theta = mg \cos \theta ( \frac{ 3 M + 2 m + m \sin^2 \theta }{ M + m \sin^2 \theta } )$,整理得到$N = Mm \cos \theta ( \frac{ 3 M + 3 m - m \cos^2 \theta }{ ( M + m \sin^2 \theta )^2 } )$.方向沿半径方向朝向圆心.

这里就要用惯性力了.

众所周知,高中物理有一道很经典的分解速度的题:

物理老师在上课讲这个题的时候,将速度分解为两个正交的速度,这两个速度的矢量和就是原速度.

乍一看好像非常合理,然而随即大家可能就会见到这个题:

其中中间的物体下落的速度为$v$,这个时候沿绳子分解速度的时候,两个分速度应该均是$v \cos \theta$,而这个时候两个速度的矢量和并不是原速度啊!

老师讲到这里的时候,往往会说这是因为:”速度的分解和力的分解并不一样.”但你可能会疑问:同样是矢量的分解,为什么会不一样呢?

先提前给出我的思考:在这个滑轮组模型中,我们做的操作并不是将原速度分解为了这两个速度,这两个速度也并非由原速度一下分解出来的,而分别只是原速度分解出的速度的一部分.

先看这个最经典的模型:

不妨设高度差为$h$,此时绳子长度为$L$,物体距离墙的距离为$x$.

有勾股定理:

$L^2 = h^2 + x^2$,注意到此时$h$是一个常量.

两边对$t$求导,自然有:

此时的另一个分速度自然是$v_h = v_x \sin \theta$.在物理课上,物理老师会这么解释这种分解:

$v_L$这个速度提供了绳子缩短的速度,而$v_h$提供了绳子转动的速度.

那么这个$v_h$听上去应该是此时绳子与物体接触点的转动的线速度对吧.也就是说角速度应该是$\omega = \frac{ v_h }{ L } = \frac{ h }{ L^2 } v_x$,令绳子与转轴夹角为$\alpha , \sin \alpha = \frac{ x }{ L }$而我们有:

这就证明了$v_h$的确是线速度,这也与我们直观感受相当匹配.

解释完上面这个分解的正确性,我们又要开始考虑了:那么为什么力和速度的分解不一样呢?

有一个很形象的比喻,那就是如果两个人同时以速度$v$的速度拉一个物体,这个物体的速度是$v$;但如果两个人同时以力$F$拉一个物体,这个物体的受力是$2 F$.

这是为什么呢?动量定理实际上将力在时间上的积累与动量等价起来了对吧,由于速度并非是动量,因此自然像力那样叠加.这么思考也许是正确的:两个受力均为$F$的物体的合力是$2 F$,两个速度均为$v$的物体合速度为$v$,两个动量均为$p$的速度相同的物体合动量为$2 p$.

或者换而言之,力的作用之间是有牛顿第三定律作保证的,这就可以让力在物体间存在一种类似传递的效果.但是速度并没有这种效果,速度并非是外界对物体做出的改变,而是物体的性质本身.

从这个角度,我们回到滑轮的那个题,我们就可以明白为什么要这么分解了:原因很简单,这两个沿绳的速度并不是一次分解分解出来的,而是让原本的速度先沿其中一个绳分解为两个速度,一个是沿绳的速度$v \cos \theta$,另一个是提供绳转动的线速度$v \sin \theta$.

而速度是不能叠加的,因此右边也做这个操作,这就使得沿绳的分速度均为$v \cos \theta$.

回看开头的那个滑轮题,这题其实还有个很好玩的地方:那就是C的动能最大点可不是C的受力平衡点:原因很简单,C的受力平衡点由于滑轮作用仍然存在角速度上的加速度.

大家高中都学过开普勒三定律对吧!下面我们来证明它们是对的.

由于难度不太一样,我们微调一下顺序.

开普勒第二定律

根据角动量守恒,当然有$\vec{ r } \times \vec{ p } = C$为定值.又根据机械能守恒,其在某一个点的机械能应该为$- \frac{ GmM }{ r } + \frac{ p^2 }{ 2 m }$.

先考虑证明开普勒第二定律,取一段极小时间$\text{ d } t$,考虑掠过的面积应该是$\text{ d } S = \frac{ 1 }{ 2 } \vec{ r } \times ( \vec{ r } + \text{ d } \vec{ r } ) = \frac{ 1 }{ 2 } \vec{ r } \times \text{ d } \vec{ r }$,于是掠面速度$V = \frac{ \text{ d } S }{ \text{ d } t } = \frac{ 1 }{ 2 m } \vec{ r } \times \vec{ p }$是一个常数.

开普勒第三定律

那么$T = \frac{ S }{ V } = \frac{ 2 m \times ab \pi }{ \vec{ r } \times \vec{ p } } = mab \frac{ 2 \pi }{ C }$.

那么$\frac{ T^2 }{ a^3 } = \frac{ 4 \pi^2 m^2 b^2 }{ aC^2 }$.

根据机械能守恒,当然应该有在近日点和远日点机械能相等,那自然有:

带入得到$\frac{ T^2 }{ a^3 } = \frac{ 4 \pi^2 }{ GM }$是一个定值.

开普勒第一定律

我们知道圆锥曲线的极坐标方程是:

其中$e$是离心率,$p$是准焦距(焦点到准线的距离).

后面不会了,开摆!

没想到这个系列博客都出到第三节了.

之所以起这么个名字,是因为下面要开搞的数列很像真理元素的这个视频.但其实下面的操作和这个视频并没有什么关系.

而且其实理论上,这篇博客的名字应该叫《被qyc创飞了(1)》

前天,qyc给我发了一个博客,里面提供了一种非常厉害的估计数列的方法.我一看就觉得超级厉害啊,因为这个题我之前也做过然后被爆杀了,而竟然可以拿科技秒掉.

大概讲一下qyc的神仙操作:

$a_1 = 1 , a_{ n + 1 } - a_n = - \frac{ 1 }{ 3 } a_n^2$

考虑构造一个函数$f ( n )$使得$f ( n ) \approx a_n$,那我们就可以将$a_{ n + 1 } - a_n \approx f_n$.

这个第一眼看上去就很有道理,而事实上也确实很有道理,原因是根据拉格朗日中值定理,$\exists x_0 \in [ n , n + 1 ] , f ‘ ( x_0 ) = f ( n + 1 ) - f ( n )$,而对于增长率变化不大的函数,直接认为$f ‘ ( x_0 ) = f ‘ ( n )$是有理可循的!

@Minuses在知乎上找到了这个东西的系统理论.但是我没有看.

然后,原式子就变成了一个微分方程了,带入$f ( 1 ) = 1$解得$f ( n ) = \frac{ 3 }{ n + 2 }$.这个精度已经足够选出来原本的放缩题的答案了.

但是我不满意!具体数学上教过我们可以用数列估计误差项,那现在我们来考虑一下它的误差项吧!

令$a_n = \frac{ 3 }{ n + 2 } - b_n$,带入化简,得到$\{ b_n \}$的递推式:

算到这里,我们可以很轻易使用数学归纳法算出$b_n \leq \frac{ 1 }{ 4 n }$,这个精度已经挺不错的了,但是也让人觉得很不满意,因为这个误差项怎么和估计项是同阶的啊.

然后我开始估计了一下这个$b_n$的阶,因为我其实没学过什么高超的高数技巧,所以我使用了OI的一些技巧来估计,不妨假设$b_n^2 < < b_n$:

$b_{ n + 1 } = O ( 1 ) b_n + O ( \frac{ 1 }{ n^3 } )$.

那么$b_n$应该是$O ( \frac{ 1 }{ n^2 } )$级别的对吧!然后我就开始算,算了一晚上也没放出来一个式子,相当自闭.

晚上回家咨询了一下汪神wzm,得知了这个$b_n$是$O ( \frac{ \ln n }{ n^2 } )$级别的,这下白算一晚上了.

如何理解这个级别?考虑别乱动$b_n$的系数,我们有:

这警戒我们以后乱估计的时候千万别把$O ( n^{ \epsilon } )$和$O ( 1 )$搞混了,警钟长鸣.

这个时候大概估计一下会发现$b_n \leq \frac{ 3 \ln n }{ n ( n + 1 ) }$.

但是如果你尝试带入数学归纳,会发现完全做不动.怎么办呢?

在这个问题被搞出来后两个周,我妈的一位同事给出了纯文化课的牛逼做法,下面来介绍一下这个做法并且终结此题:

首先换元,上面等价于下面这个数列放缩:

观察形式,注意到$a_n ( a_n - 1 )$这个东西很像一个类似裂项的东西,因此两边取倒数,自然有:

考虑$0 < a_n \leq \frac{ 1 }{ 3 }$,于是我们有下面这个不等式:

两边求和有:

仔细观察下面这个式子:

我们上面的操作实质上是使用这个式子将$0 < a_n \leq \frac{ 1 }{ 3 }$这个放缩给缩紧了,所以我们再用一次这个式子再紧一遍.

两边求和自然有:

这个界甚至比我们给出的界还要紧.而且似乎继续迭代可以得到更紧的解!相当牛逼!

概统导论

习惯的更改

这一部分主要是和组合相关,文化课中的组合内容有一些很奇怪的形式,比如竞赛中为了避免巨量的字母符号所带来的丑陋形式,会将$C_{ n }^k$写作$\binom{ n }{ k }$,而文化课中不允许此类更改,再者文化课中将$C_{ n }^k a^{ n - k } b^k$称作二项式的第$k + 1$项(从第$1$项开始编号),此等同样是一个需要改正的习惯.

从线性角度审视

首先我们有$E ( aX + b ) = aE ( X ) + b , D ( aX + b ) = a^2 D ( X )$.

我们都知道期望满足线性可加,也就是$E ( X_1 + X_2 ) = E ( X_1 ) + E ( X_2 )$,这很好理解,因为期望从一开始定义就是所有情况下的答案的加和,因此根据我们的加法交换律和结合律就可以导出上面的式子.

我们还知道期望的乘法在相互独立的条件下是可以直接乘的,也就是若$X_1$和$X_2$相互独立,$E ( X_1 X_2 ) = E ( X_1 ) E ( X_2 )$,同样是拆期望那个式子,使用乘法分配律得到.

而方差在相互独立的条件下同样是线性可加的,也就是只要$X_1$和$X_2$相互独立,$D ( X_1 + X_2 ) = D ( X_1 ) + D ( X_2 )$.从形式上证明是好证明的,我们考虑:

或者你也可以卷积然后求导啊!

如何从感性上理解这一点呢?很遗憾,笔者暂时没有想出从感性上理解的方式.从感觉上来讲,笔者比较相信这和独立变量以及正交性有关,查询相关资料得到了协方差的概念,也就是当两个变量独立的时候协方差为$0$,不然$D ( X_1 + X_2 )$要再加上两倍的协方差.笔者的能力也就到此了.

对于数据统计部分,我们会发现它在做的其实都是一个套路:将数据放在均值的两侧,也就是减去均值,这样新的值的均值为$0$,并且缩放权值,使得方差恰好为$1$.这个做法在正态分布那里就已经展示了它的强大.这是下面概统的极重要的思想,似乎被称作”标准化”.如果我们痴迷于这个思想,就会发现概统的一切复杂的公式的目的只有两个:让误差均值为$0$的前提下,使得方差最小.

分布列

两点分布

直接写的话也就是$P ( X ) = \begin{cases}p & X = 1 \ 1 - p & X = 0 \ 0 & other\end{cases}$,事实上这么写可能不太严谨,因为两点分布的$X = 1$和$X = 0$两个事件互为对立,但笔者仍然选择这种形式来写,因为看着舒服.

考虑概率生成函数,自然是$G ( x ) = ( 1 - p ) + px$.由此式子轻松推得$E ( x ) = G ‘ ( 1 ) = p , D ( x ) = E ( x^2 ) - E^2 ( x ) = G ‘ ‘ ( 1 ) + G ‘ ( 1 ) - ( G ‘ ( 1 ) )^2 = p - p^2 = p ( 1 - p )$.

这里非要炫技用一下概率生成函数是因为笔者快忘了这玩意怎么用了,这个东西在下面几乎不会再用到了.

二项式分布

所谓$n$重伯努利试验,也就是$n$次两点分布的累计,满足$P ( X = k ) = C_{ n }^k ( 1 - p )^{ n - k } p^k$,我们关注两个事情,也就是二项式分布的$E ( X ) = np , D ( X ) = np ( 1 - p )$,也就是将两点分布的均值与方差给拆开单独累加了.

超几何分布

所谓不放回取球,考虑目前有$N$个数字,有$M$个是$1$,剩下$N - M$个是$0$,取出$n$次,取出了$m$个$1$的概率.简单组合一下得到此概率为$\frac{ C_{ M }^m C_{ N - M }^{ n - m } }{ C_{ N }^n } \\$,注意这里必须保证$n \leq N$.

由范德蒙德卷积得知,$\sum_{ m } C_{ M }^m C_{ N - M }^{ n - m } = C_{ N }^n$,因此该分布列所有情况之和为$1$.

考虑其均值,从感性上讲必定是$\frac{ nM }{ N }$.

从理性上讲,首先可以吸收恒等式+范德蒙德卷积,其次可以概率生成函数.

结合来讲,考虑每一个事件:它必然形如$01101$之类的,表示每一次取出时拿到的球.不难发现对于事件的全集,我们交换前两个球,仍然唯一对应到了事件的全集.也就是说取出的顺序并不重要,第一次取得到$1$的概率,和第二次取得到$1$的概率完全相等,这必然意味着两次的期望相等.

方差是$n \frac{ N ( N - M ) ( N - n ) }{ N^2 ( N - 1 ) }$,不太想管这个东西了.

正态分布

前面的分布大都是离散的,而正态分布是连续函数,因此我们写$f ( x ) = \frac{ e^{ - \frac{ ( x - \mu )^2 }{ 2 \sigma^2 } } }{ \sigma \sqrt{ 2 \pi } } \\$,是不是看着非常震撼!其中的方差是$\sigma^2$,期望是$\mu$.本着闲着没事干的原则,我们来彻底冷静一下剖析整个正态分布函数:

众所周知,标准正态分布满足$\sigma = 1 , \mu = 0$,此时的函数也就是$f ( x ) = \frac{ e^{ - \frac{ x^2 }{ 2 } } }{ \sqrt{ 2 \pi } }$.一个好奇是,你凭啥说所有情况下的概率之和为$1$,事实上这其实是因为$g ( x ) = e^{ - x^2 }$的积分是$\sqrt{ \pi }$,不会求这个积分.

观察$g ( x ) = e^{ - x^2 }$这个函数,你会发现它其实是想要模拟一个钟形曲线,也就是中间部分要更高,两边要更低.如果只是这样,我们完全可以用函数$e^{ - | x | }$模拟,但这样的曲线并不圆滑,中间有个小突起,这是因为绝对值本身的分段函数性质,因此直接把上面那个东西换成平方得到一个更圆滑的曲线,如果想要这个曲线横向放缩,则对横坐标使用变换,这就是$\sigma$的由来,将$x \rightarrow \sigma x$,也就是在$x$那里除去一个$\sigma$.而对这个曲线进行横向移动,也就是将$x \rightarrow x - \mu$.

这也就引出所谓的$3 \sigma$原则了,同样是积分.

成对数据的统计

样本相关系数

对于若干数据$( x_i , y_i )$,我们先进行标准化,也就是减去均值后再除以方差,这样做使得$x , y$分别的均值为$0$,方差为$1$.下面默认已经标准化过了.

不妨构造$n$维向量$\vec{ x } = ( x_1 , x_2 , \cdots , x_n ) , \vec{ y } = ( y_1 , y_2 , \cdots , y_n )$,考虑它们的点乘$\vec{ x } \cdot \vec{ y }$,不难发现由于方差为$1$,因此$| \vec{ x } | = | \vec{ y } | = \sqrt{ n }$,因此它们的点乘为$n \cos \theta$,设$r = \frac{ \vec{ x } \cdot \vec{ y } }{ n } = \cos \theta$.

如果$\exists k$,$\forall i , y_i = kx_i$,此时必有$| r | = 1$,因此我们断言(为啥呢?其实是不太理解的啊)当$| r |$越靠近$1$的时候,$x , y$之间的线性关系越强.

最小二乘法

我们在上面的角度审视中提出了一个观点:在满足均值为$0$的前提下,使得方差最小.由此我们审视所谓的一元线性回归方程:$Y = bx + a + e , E ( e ) = 0 , D ( e ) = \sigma^2$.

现在我们要做的就是,已知若干组数据$( x_i , y_i )$,去构造一组$a , b$满足上面的条件.不妨令$e_i = y_i - ( bx_i + a )$,若$\sum e_i = 0$,必有$a = \bar{ y } - b \bar{ x }$,带入解得当$\sigma$最小的时候,$b = \frac{ \sum_{ i } ( x_i - \bar{ x } ) ( y_i - \bar{ y } ) }{ \sum_{ i } ( x_i - \bar{ x } )^2 } \\$.

提出质疑:为啥这里不需要对数据进行标准化呢?

因为标准化没有用,我们的目的是找到那个$b$使得$\sigma$最小,标准化说到底只是为了保证$\sigma = 1$的工具,没有必要在这里标准化.

独立性检验

使用卡方分布,懒得去学细节了.

独立性检验其实是依赖于这么一件事实:那就是如果两个事件独立,我们得知$P ( AB ) = P ( A ) P ( B )$,那么我们反推,如果我们在现实中的估计中,发现$P ( AB )$和$P ( A ) P ( B )$差的太大,那么我们就认定其没有独立性.

接下来不妨设在测试过程中估算出:$P ( 00 ) = \frac{ a }{ n } , P ( 01 ) = \frac{ b }{ n } , P ( 10 ) = \frac{ c }{ n } , P ( 11 ) = \frac{ d }{ n }$.那么$P ( A = 0 ) P ( B = 0 ) = \frac{ ( a + b ) ( a + c ) }{ n^2 }$.我们计算它与$P ( 00 )$的差,平方后除以$P ( A = 0 ) P ( B = 0 )$然后做四遍求和化简,得到$\chi^2 = \frac{ n ( ad - bc )^2 }{ ( a + b ) ( a + c ) ( c + d ) ( b + d ) }$.

这有什么用呢?通过牛逼数学家的计算,我们可以认为如果独立性成立,那么$P ( \chi^2 \geq x_\alpha ) = \alpha$.或者给出我们经验上的准则:

选取一个较小的$\alpha$,并得知其对应的$x_\alpha$,如果$\chi^2 \geq x_\alpha$,推断独立性不成立,犯错的概率是$\alpha$.反之断言其独立性成立,犯错的概率不可知,肯定$\alpha$越大犯错的概率越小.

函数导论

常用对数表

1. $\ln 2 = 0 . 693$.

2. $\ln 3 = 1 . 099$.

3. $\ln 5 = 1 . 609$.

4. $\ln 0 . 1 = - 2 . 303$.

5. $\ln 0 . 5 = - 0 . 693$.

常用指数表

1. $e = 2 . 718$.

2. $e^2 = 7 . 389$.

3. $e^3 = 20 . 086$.

4. $e^5 = 148 . 413$.

5. $e^{ 0 . 1 } = 1 . 105$.

6. $e^{ 0 . 5 } = 1 . 649$.

7. $e^\pi = 23 . 147$.

基本函数的图像及性质

$f(x)=xe^x$

图像

极值与极限

$f ‘ ( x ) = ( x + 1 ) e^x$,$x = - 1$的时候,取最小值$- \frac{ 1 }{ e }$.

另外$\lim_{ x \rightarrow - \infty } f ( x ) = 0 \\$.

$f(x)=x\ln x$

图像

极值与极限

$f ‘ ( x ) = 1 + \ln x , x = \frac{ 1 }{ e }$的时候,有最小值$- \frac{ 1 }{ e }$.

另外$\lim_{ x \rightarrow 0^{ + } } f ( x ) = 0 \\$.

$f(x)=\frac{e^x}{x}$

图像

极值与极限

$f ‘ ( x ) = \frac{ e^x ( x - 1 ) }{ x^2 } , x = 1$的时候,有极小值$e$.

另外$\lim_{ x \rightarrow - \infty } f ( x ) = 0 \\$.

$f(x)=\frac{\ln x}{x}$

图像

极值与极限

$f ‘ ( x ) = \frac{ 1 - \ln x }{ x^2 } , x = e$的时候,有极大值$\frac{ 1 }{ e }$.

另外$\lim_{ x \rightarrow + \infty } f ( x ) = 0 \\$.

$f(x)=x-\ln x$

图像

极值与极限

$f ‘ ( x ) = 1 - \frac{ 1 }{ x } , x = 1$的时候,有最小值$1$.

$f(x)=\frac{x}{e^x}$

图像

极值与极限

$f ‘ ( x ) = \frac{ 1 - x }{ e^x } , x = 1$的时候,有最大值$\frac{ 1 }{ e }$.

另外$\lim_{ x \rightarrow + \infty } f ( x ) = 0 \\$.

预处理函数

分离对数

Example

令$f ( x ) = ( 2 + x + ax^2 ) \ln ( x + 1 ) - 2 x$,已知$x = 0$是极大值点,求$a$.

考虑分离对数后操作多项式,我们显然可找到$0 < t < 1 , 2 + t + at^2 > 0 , 2 - t + at^2 > 0$,下面只考虑$x \in [ - t , t ]$.此时$f ( x ) = ( 2 + x + ax^2 ) ( \ln ( x + 1 ) - \frac{ 2 x }{ 2 + x + ax^2 } )$.

考虑令$g ( x ) = \ln ( x + 1 ) - \frac{ 2 x }{ 2 + x + ax^2 }$,由于$f ( 0 ) = 0$,只需证明$g ( x ) \leq 0 , x \in [ - t , t ]$即可.

而:

则$a^2 0^2 + 4 a 0 + 6 a + 1 = 0$,$a = - \frac{ 1 }{ 6 }$.验证一下.

消去指数

Example

令$f ( x ) = e^x - \ln ( x + 1 ) + ax^3 - x^2 - 1$,若$\forall x \in ( - 1 , 1 ) , f ( x ) \geq 0$,求$a$.

$f ( 0 ) = 0$,于是上面的条件等价于$0$是$( - 1 , 1 )$的最小值点.

考虑$f ‘ ( x ) = e^x - \frac{ 1 }{ x + 1 } + 3 ax^2 - 2 x$,则$f ‘ ( 0 ) = 0$恒成立.

讨论$g ( x ) = 1 + e^{ - x } ( 3 ax^2 - 2 x - \frac{ 1 }{ x + 1 } )$的正负,看$g ‘ ( x ) = \frac{ x ( - 3 ax^3 + 2 x^2 + ( 9 a + 2 ) x + 6 a - 1 ) }{ ( x + 1 )^2 e^x }$.

接下来的讨论是简单的.

消元法

变化条件

Example

已知$x + 2 y = 1$,求$x^2 + y^2$的最小值.

直接令$x = 1 - 2 y$,带入即可.

变化所求

Example

已知$x^2 + y^3 = 2$,求$x + y$的最小值.

这个的话不妨设其最小值为$C$,有$x + y \geq C$,移项得到$y \geq C - x$,两边三次方然后带入.

换元法

普通参数方程

Example

已知$x^2 + y^2 - xy = 1$,求$x + y$的最小值.

这个的话大概是这样,我们找到一个$t$,使得$x = f ( t ) , y = g ( t )$,然后换元.

比如这个题,你就可以凑成$( x - \frac{ y }{ 2 } )^2 + ( \frac{ \sqrt{ 3 } }{ 2 } y )^2 = 1$,然后做三角换元.

齐次化构造

Example1(对数平均不等式)

求证$\sqrt{ ab } < \frac{ a - b }{ \ln a - \ln b } < \frac{ a + b }{ 2 }$.

两边证明方式类似,这里只证明右半边,下面的证明的每一步均为充要的,因而可以倒退.

换元,令$t = \frac{ a }{ b }$,然后下面大力求导.

Example2

已知函数$f ( x ) = 3 \ln x - ax$,若$x_1 < x_2$是$f ( x )$的两个零点,求证$f ‘ ( \frac{ x_1 + 3 x_2 }{ 4 } ) < 0$.

我们来分析已知,我们目前知道的是:

我们想要知道的是:$\frac{ 12 }{ x_1 + 3 x_2 } < a$.

这就是整个题全部的部分,和前面的函数其实一点关系都没太有.那么这个东西怎么搞呢?我们先把$a$给换掉,事实上我们根据前面的方程有$a = \frac{ 3 \ln \frac{ x_2 }{ x_1 } }{ x_2 - x_1 }$.

于是我们只需要证明:$\frac{ x_1 + 3 x_2 }{ 4 } > \frac{ x_2 - x_1 }{ \ln \frac{ x_2 }{ x_1 } }$,这是一个很显然的齐次化形式.

Example3

已知函数$f ( x ) = \ln x - ax$,其有两个零点$x_1 \ne x_2$,求证$x_1 x_2 > e^2$.

同样分析已知,我们得到的是:

通过简单线代知识我们知道,如果我们想把这两个条件同时用上,我们最好先相加再相减,这样这一步推下来就是充要的:

这里先把所求变形一下,我们把它改成$\ln x_1 + \ln x_2 > 2$.

发现了什么?这个东西等价于$a ( x_2 + x_1 ) > 2$,至此,我们用上了第二个式子,并且将其蕴含到了答案中.

接下来用第一个式子代换$a$即可.

Example4

已知$f ( x ) = x^2 + axe^x - ae^{ 2 x }$有三个不同的零点$x_1 < x_2 < x_3$,求$a$的范围,并求证$( 1 - \frac{ x_1 }{ e^{ x_1 } } )^2 ( 1 - \frac{ x_2 }{ e^{ x_2 } } ) ( 1 - \frac{ x_3 }{ e^{ x_3 } } ) = 1$.

考虑两边同时除以$e^{ 2 x }$,这样得到$g ( x ) = ( \frac{ x }{ e^x } )^2 + a \frac{ x }{ e^x } - a$,令$t = \frac{ x }{ e^x }$得到$g ( t ) = t^2 + at - a = 0$.

考察$g ( t ) = 0$的两根$t_1 < t_2$,根据韦达定理,首先需要满足$\Delta = a^2 + 4 a > 0 \Rightarrow a > 0$,然后$t_1 + t_2 = - a , t_1 t_2 = - a$.

接下来考察函数$\frac{ x }{ e^x }$,这个函数图像我们很熟悉,如果想要最后有三个零点,又因为$t_1 , t_2$中必有一负,因此$t_2 \in ( 0 , \frac{ 1 }{ e } )$.由此立得$0 < a < \frac{ 1 }{ e ( e - 1 ) }$.

接下来考虑后面那个东西,其实就是简单韦达定理,随便做做.

同构化构造

Example1

若$x > 0$时,$ax ( e^{ ax } + 1 ) \geq 2 ( x^2 + 1 ) \ln x$恒成立,求$a$取值范围.

一般这种题先判$a$的正负,注意到$x > 1$的时候右边恒大于$0$,因此$a > 0$.

观察这个式子,发现形式似乎很相似,更进一步地,我们把常数$2$放进$\ln$,自然有:$ax ( e^{ ax } + 1 ) \geq ( x^2 + 1 ) \ln x^2$.

考虑令$t_1 = ax , t_2 = \ln x^2$,则:

接下来分析函数$f ( x ) = x ( e^x + 1 )$的单调性,就可以得到$a \geq \frac{ 2 }{ e }$.

不等式相关

基本不等式相关

方程角度的审视

我们曾经下过这么一个论断:即对于有一个方程限制的双变量,求另一个式子的最值,我们是可以有一套机械化方法探路的.具体而言,这个方法基于大部分情况下,我们只需要两个二元方程就可以得到确定的(唯一或者唯二或者常数个)原本的两个变量的值.

于是我们设一个常数来表示其中一个方程,另一个方程自然是题目给出的限制条件,我们只需要把所求转化为对于这个常数的限制就好了.

如果我们再去仔细揣摩这个过程,我们会发现一些更有趣的事情:即只要我们能做到”降次”这件事,我们似乎一定存在方程的解.这可能类似于所谓的齐次化构造$\frac{ m }{ n } = k$.

那这意味着什么呢?在绝大多数情况下我们拿到的方程都是非齐次的方程,这给了我们机会去降次.

我们给出一个例题:

Example

已知$n , m > 0 , 2 m + n = nm$,求$n + m + \sqrt{ n^2 + m^2 }$的最小值.

这个题有一个方式是观察到$n , m , \sqrt{ n^2 + m^2 }$是直角三角形的三条边然后使用三角换元.但我们接下来会给出一个更加厉害的做法:

我们想要知道它的最小值,就是想要证明下面这个不等式并且证明等号成立:

如果$n + m \geq k$,那么不等式显然成立,下面只需要证明$n + m < k$的情况:

变形方程得到$\frac{ 2 }{ n } + \frac{ 1 }{ m } = 1$,使用这个式子来降次:

要严谨一点的话我们需要证明$4 k - 8 \geq 0$,$k \geq 2$.这非常简单,因为$k \geq n + m > 3$.

这就足够了么?不需要证明存在一个$w = \frac{ n }{ m }$使得带入到原方程中有解么?这个其实是显然易证的.

那么:

这个等号可以取到,也就是说,只要满足:

那么这个$k$就是一个下界,特别地,如果满足:

那么这个$k$就是一个下确界,也就是我们想要求的最小值.

事情还没有解决(即使这个时候你已经能猜到$k = 10$是一个解了),接下来我们必须求出一个$k$.

我们看上去走投无路了对么?其实不然,你发现这个式子两边的次是不等的,我们可以使用它降次!换言之,把这个$\sqrt{ k - 2 }$带入到上面去!

我想你这个时候又会发现我们走投无路了,但稍微思考一下就会发现,这个方程一定没有常数项(或者说$k = 0$是这个方程的一个解).

这样得到了一个二次方程,我们自然可以解出$k = 10$.

泰勒展开

抽象函数的泰勒展开

常用泰勒展开公式

1. $\frac{ 1 }{ 1 - x } = \sum_{ k \geq 0 } x^k = 1 + x + x^2 + \cdots \\$.

2. $e^x = \sum_{ k \geq 0 } \frac{ x^k }{ k ! } = 1 + x + \frac{ 1 }{ 2 ! } x^2 + \cdots \\$.

3. $\ln ( 1 + x ) = \sum_{ k \geq 1 } ( - 1 )^{ k - 1 } \frac{ x^k }{ k } = x - \frac{ 1 }{ 2 } x^2 + \frac{ 1 }{ 3 } x^3 + \cdots \\$.

极值点偏移

Example1

已知函数$f ( x ) = \ln x - ax$,其有两个零点$x_1 \ne x_2$,求证$x_1 x_2 > e^2$.

极值点偏移的形式,应该是形如$g ( x ) = a$有两个解$x_1 , x_2$,然后使得$x_1 + x_2$满足一定条件.因此我们先变形条件:

也就是目前我们构造出了函数$g ( x ) = \frac{ \ln x }{ x }$,观察$g ( x )$图像立得$x_1 + x_2 > 2 e$.

我们发现,$x_1 x_2 \leq \frac{ ( x_1 + x_2 )^2 }{ 4 }$,这个形式看上去非常正确!但是问题在于,我们好像不太能去变形不等式了,怎么办呢?

考虑对着我们要证明的东西去搞,极值点偏移可以解决相加性问题,因此我们变形所求为$\ln x_1 + \ln x_2 < 2$,然后令$t_1 = \ln x_1 , t_2 = \ln x_2$,带入立有:

而$g ( x ) = \frac{ x }{ e^x }$恰好也是满足$x_1 + x_2 > 2$的这么一个函数!于是我们就解决了问题.

Example2

$f ( x ) = x ( 1 - \ln x )$,$b \ln a - a \ln b = a - b$,求证$2 < \frac{ 1 }{ a } + \frac{ 1 }{ b } < e$.

首先变形条件得到$b ( 1 + \ln a ) = a ( 1 + \ln b )$,得到$f ( \frac{ 1 }{ a } ) = f ( \frac{ 1 }{ b } )$,左半部分就是经典极值点偏移.

那么右半部分怎么做呢?我们来考虑:

$f ‘ ( x ) = - \ln x$,其在$( 0 , 1 ) \uparrow , ( 1 , + \infty ) \downarrow$,考察极值点偏移,我们想要证明$\frac{ 1 }{ b } < e - \frac{ 1 }{ a }$,我们就想办法把$\frac{ 1 }{ b }$和$e - \frac{ 1 }{ a }$扔到同一个区间里,而它们确实同在$( 1 , + \infty )$这个区间内.

比较有启发性的是,你发现$\frac{ 1 }{ b } , e - \frac{ 1 }{ a }$和$\frac{ 1 }{ a } , e - \frac{ 1 }{ b }$这两对必有一对在同一个区间内部.

现在我们就可以套路化了:

对着上面那个函数证明即可.

Example3

$f ( x ) = e^{ x - 1 } - ax$在$( 0 , 2 )$有两个零点$x_1 , x_2$,求证$x_1 x_2 > \frac{ 1 }{ a }$.

首先要证明$a$的范围啊,我们不加证明地给出:$a \in ( 1 , \frac{ e }{ 2 } )$,并且$( - \infty , 1 + \ln a ) \downarrow , ( 1 + \ln a , + \infty ) \uparrow$.

这个其实差不多啊,简单来说就是首先列方程:

我们知道,一般双变量的问题加法会比较好做(原理是加法便于看单调区间),因此现在我们有两条路可走:要么变化所求,两边取$\ln$,要么变化已知.

我们发现如果变化所求,我们还得对已知两边取$\ln$,这也太麻烦了,不如直接变化已知.具体地,我们把已知的式子相乘就可以得到$x_1 x_2$和$x_1 + x_2$之间的关系,带下来就可以了.然后观察单调区间做极值点偏移.最后的式子应该形如$0 < f ( 2 + \ln a - x_2 )$,也就是$0 < ae^{ 1 - x_2 } - a ( 2 + \ln a - x_2 )$.

但是这样有一个问题,我们把$f$带进去,你会发现最后我们的式子同时带有$a , x_2$,这个就难做了,咋办呢?考虑拿$ax_2 = e^{ x_2 - 1 }$操作一下把$a$消掉就好了.

切割线放缩

基本的切割线不等式

1. $e^x \geq x + 1$.

2. $\frac{ x - 1 }{ x } \leq \ln x \leq x - 1$.

乍一看非常平凡,事实上有一些不平凡的推论:

1. $\ln ( n + 1 ) < \sum_{ k = 1 }^n \frac{ 1 }{ k }$.

考虑$\ln ( \frac{ n + 1 }{ n } ) < \frac{ 1 }{ n }$,左右两边分别求和得到上面的式子.

1. $\ln n > \sum_{ k = 2 }^n \frac{ 1 }{ k } , n > 1$.

这个怎么证明呢?考虑左右取负,也就是需要证明$\ln \frac{ 1 }{ n } < - \sum_{ k = 2 }^n \frac{ 1 }{ k }$.

考虑$\ln ( \frac{ n - 1 }{ n } ) \leq - \frac{ 1 }{ n }$,两边求和得到上式.

1. $\sum_{ k = 1 }^n ( \frac{ k }{ n } )^n < \frac{ e }{ e - 1 }$.

考虑$n \ln ( \frac{ k }{ n } ) \leq k - n$,也就有$( \frac{ k }{ n } )^n \leq e^{ k - n }$,两边求和得到上式.

一般的切割线放缩

Example1

设$f ( x ) = x \ln x$,若$f ( x ) = b$有两个实数根$x_1 , x_2 ( x_1 < x_2 )$,求证:$be + 1 < x_2 - x_1 < \frac{ e^{ - 3 } + 2 + 3 b }{ 2 }$.

注意到$f ( x )$下凸,考虑求出两条切线,那么这两条切线与$y = b$的交点之差要大于等于$x_2 - x_1$,两条割线交点之差要小于等于$x_2 - x_1$.

先求好求的割线,一般而言,我们考虑边界情况,也就是$b \rightarrow - \frac{ 1 }{ e }$的情况,为了让这种情况有解,我们的割线必过$( \frac{ 1 }{ e } , - \frac{ 1 }{ e } )$.

考虑直接选取$( 0 , 0 )$和$( 1 , 0 )$作为另外两个点,这两条割线就是$x = - y$和$x = ( e - 1 ) y + 1$.做差立得上面的式子.

那么后半边怎么证明呢?我们考虑一个想法是:这题既然出出来了,它必然不可能是虚的.因此我们要找的切点不可能过于离谱.

另外一个事实是,我们考虑如果我们找到了一条切线,那么由于不等式的右边是定值,我们肯定想要让令一条切线稍微平均一下,使得$( x_2 - x_1 )_{ \max }$尽可能地小对吧!

我们不妨设我们要找的两个切点,一个横坐标是$u$,另一个是$v$,其中$v < \frac{ 1 }{ e } < u$,那么两条切线分别是:

那么,现在我们要做的就是找到一组$( u , v )$,使得:

感觉很难搞啊,我们不妨让$u = 1$,自然有:

然后我们凑系数,上面的式子,我们大胆猜测:

考虑让$f ‘ ( v ) = - 2$,则$v = e^{ - 3 }$,带入发现正好适配.

凹凸性反转

Example1

求证:$\forall x \in ( 0 , + \infty ) , \ln x + 1 > \frac{ 1 }{ e^{ x + 1 } } - \frac{ 2 }{ e^2 x }$.

这个式子看上去就很震撼,那么我们该怎么处理呢?

我们知道常数项在导数中是好处理的,而且我们通过强大的注意力,发现右边那个式子如果乘以$x$,他就是一个凸函数了,而左边也是有凹凸性的.

因此我们变形为$x \ln x + x > \frac{ x }{ e^{ x + 1 } } - \frac{ 2 }{ e^2 }$,然后证明左边的最小值$\geq$右边的最大值.

比较大小

接下来以一个题为例,介绍一下几种估算/严谨的比较大小方式.

Example1

已知$a = 0 . 1 e^{ 0 . 1 } , b = \frac{ 1 }{ 9 } , c = - \ln 0 . 9$,求比较$a , b , c$的大小关系.

二阶导数

我们上面声明过了二次导数可以判断极值类型,我们用这个方式来计算$a$和$c$的大小关系.

构造函数$f ( x ) = xe^x + \ln ( 1 - x )$,则$f ( 0 . 1 ) > 0 \Rightarrow a > c$.

考察$f ( 0 ) = 0$,$f ‘ ( 0 ) = 0$,$f ‘ ‘ ( 0 ) = 4 > 0$,则$f ( 0 ) = 0$是一个极小值点,并在接下来有着增大的趋势.因此我们可以估算$f ( 0 . 1 ) > 0$.

估算定积分

考察$a$和$b$的大小关系,不妨设$f ( x ) = ( 1 - x ) e^{ 1 - x } - \frac{ 1 }{ 10 x }$,则$f ( 0 . 9 ) < 0 \Rightarrow b > a$.

注意到$f ( 1 ) = - \frac{ 1 }{ 10 }$,$f ‘ ( 1 ) = - \frac{ 9 }{ 10 }$,考虑估算一下积分,那么$f ( 0 . 9 ) \approx f ( 1 ) - f ‘ ( 1 ) 0 . 1 = - \frac{ 1 }{ 100 } < 0$.

你可能会觉得这个$- \frac{ 1 }{ 100 }$,是不是不太能那么肯定地估算啊.但是实际上,我们考察$f ‘ ( x ) = ( x - 2 ) e^{ 1 - x } + \frac{ 1 }{ 10 x^2 }$,这个东西在$[ 0 . 9 , 1 ]$上直觉上平均值是大于$- \frac{ 9 }{ 10 }$的,这样就有道理多了(真的么).

泰勒展开

上面提过了,这里略过.

正经做法

接下来开抄标答.

令$f_a ( x ) = xe^x , f_b ( x ) = \frac{ x }{ 1 - x } , f_c ( x ) = - \ln ( 1 - x )$.

这样当$x = 0 . 1$的时候所有的数字都被正确表示了.

比较$a , b$:

考虑它们都有乘除项,考虑使用对数把乘除改为加减,立有:

注意到$x = 0$的时候$y = 0$,又注意到其在$( 0 , 0 . 1 )$上单减,这样立有$a < b$.

比较$a , c$:

注意到$x = 0$的时候$y = 0$,又注意到其在$( 0 , 0 . 1 )$上单增,这样立有$a > c$.

经验教训:在构造函数的时候,你一定要找一些简单一点的函数来构造,最好不要带有系数.

数列导论

递归式的求解

特征根法

一个常系数的$k$阶线性递推关系形如:

当$P = 0$时,称作齐次线性递推.

特征方程

我们称方程$r^k = \sum_{ i = 1 }^k c_i r^{ k - i }$是该递推关系的特征方程,方程的解叫做该递推关系的特征根.

二阶线性齐次递推

若其特征方程有两个不同的根$r_1$和$r_2$,那么存在两个常数$\alpha_1$和$\alpha_2$,满足$a_n = \alpha_1 r_1^n + \alpha_2 r_2^n$.

若其特征方程有两个相同的根$r$,那么存在两个常数$\alpha_1$和$\alpha_2$,满足$a_n = \alpha_1 r^n + \alpha_2 nr^n$.

先考虑前者的证明,首先考虑对于$n = 0$或者$n = 1$的情况,我们考虑求出一组$\alpha_1$和$\alpha_2$来满足:

若$r_1 \ne r_2$,可以解得:

接下来考虑数学归纳:

接下来考虑后者,首先我们有$\Delta = c_1^2 + 4 c_2 = 0$,考虑初始条件:

接下来我们考虑数学归纳:

我们接下来只需证明$c_1 r + 2 c_2 = 0$即可.根据方程,不难发现$r = \cfrac{ c_1 }{ 2 }$,根据$\Delta = 0$,自然得证.

更一般的情况

在上面做$k = 2$的时候,我们已经发现了这个问题的棘手.甚至动用了求根公式.那有没有什么办法能让这个方法拓展到更高维呢?我们引入线性代数.

重定义向

由于《线性代数》一书的作者与笔者使用字母习惯略有差异,为了防止出错,下面一律使用原书的使用习惯,可能会与前面的定义不尽相同.

给定$a_0 , . . . , a_n$,其中$a_0 \ne 0$,对于所有的$k \in \mathbb{ N }$,若有下列式子成立:

则称为一个$n$阶线性差分方程(或递归关系).为了简化,通常取$a_0 = 1$.若$\{ z_k \}$是零序列,则称其是一个齐次线性方程.

引入矩阵

我们注意到,对于齐次差分方程而言,如果不给定$y_0 , \cdots y_{ n - 1 }$,只是构造一组满足条件的$y$的话,自然的想法是令$y_k = r^k$.其中$r$是辅助方程$a_0 r^{ n } + a_1 r^{ n - 1 } + \cdots + a_n = 0$的一个根.

注意到如果我们将上面的内容看作是$T : \{ y_k \} \mapsto \{ z_k \}$这样一个映射,这显然是一个线性变换.这意味着齐次方程$a_0 y_{ k + n } + a_1 y_{ k + n - 1 } + \cdots + a_n y_k = 0$的解集就是$T$的核,设为$H$,不难发现只要给定$y_0 , \cdots y_{ n - 1 }$,这个解就唯一确定,将它们看作自由变量,这意味着$\dim H = n$.

还没完,注意到我们解方程可以解出$n$个根,如果这$n$个根互不相同,这意味着它们必然线性无关.这样的话我们就可以轻松求得所有的解集,就算给定了$y_0 , \cdots y_{ n - 1 }$,我们也可以用解集的基通过线性组合拟合出来答案.

至于如果这$n$个根有重根的话怎么办,我们发现这可能拟合失败.根据上面的经验,我们发现我们需要找到另外几组线性无关的$\mathbb{ R }^k$的向量来拟合.

最后,如果对于非齐次线性递推的答案,可能就需要猜根了.总之需要猜出总共$n$个线性无关的根,然后拟合初值.我们如此做:对于一个出现了$m$次的根$r$,我们注意到$r^k , kr^k , \cdots , k^{ m - 1 } r^k$都是满足条件的解,且他们线性无关.这个结论是怎么得到的呢?

首先,我们注意到如果初始条件成立,我们只要错位相减就可以做数学归纳,也就是说我们需要证明初始条件成立,下面以$kr^k$作为例子,即证明:

是满足条件的.

用一下简单的生成函数技巧,如果有两个$r$作为根,必然意味着原方程形如$( y - r )^2 P$,其中$P$是一个关于$y$的多项式.

我们把它写开:$( y^2 - 2 ry + r^2 ) P = 0$,然后我们用$kr^k$去代替$r^k$,不难发现代替后右边还是个多项式,而左边变成了$0$,这意味着这个根一定可行.

对于更高次的问题,只需要用二项式定理解决一下就行.

不过!我们可以用导数解决这个问题:我们对原方程两边求导.

这样我们就可以数学归纳解决.

另外,我们注意一个问题:$( ( y - r )^2 P ) ‘ = ( y - r ) ( ( y - r ) P ) ‘ + ( y - r ) ‘ ( y - r ) P = ( y - r ) [ ( y - r ) ‘ P + ( ( y - r ) P ) ‘ ]$,$r$一定是这个方程的一个根,高次是同理的.

再进一步

我们注意到齐次差分方程一定能写成$\vec{ x }_k = A \vec{ x }_{ k - 1 }$的形式.如果我们取$A$的特征向量的线性组合作为$\vec{ x }_0$,不难发现一定是满足条件的.

更进一步,如果我们定义元素和为$1$的向量为概率向量,由概率向量组成的矩阵为概率矩阵,那么确定了初始向量的齐次差分方程最后一定会收敛到一个值.证明的话直接求通项然后去求极限即可.

再再进一步

我们都知道矩阵加速:也就是$\vec{ x }_{ k + 1 } = A \vec{ x }$,$\vec{ x }_{ n } = A^n \vec{ x }_0$.而我们又知道CH定理:$p ( A ) = 0$,我们用多项式取膜,有$A^n = p ( A ) F ( A ) + G ( A ) = G ( A )$,这就是解.

数列中的求和问题

和式的基本运算

分配律:$\ \sum_{ i \in S } ca_i = c \sum_{ i \in S } a_i \\$.

结合律:$\ \sum_{ i \in S } ( a_i + b_i ) = \sum_{ i \in S } a_i + \sum_{ i \in S } b_i$.

交换律:$\sum_{ i \in S } a_i = \sum_{ p ( i ) \in S } a_{ p ( i ) }$,其中$p$是$S$集合的重新排列.

交换求和顺序:

1. $\sum_{ i } \sum_{ j } a_{ i , j } [ P ( i , j ) ] = \sum_{ j } \sum_{ i } a_{ i , j } [ P ( i , j ) ]$.

2. $\sum_{ i = 1 }^n \sum_{ j = i }^n a_{ i , j } = \sum_{ j = 1 }^n \sum_{ i = 1 }^j a_{ i , j }$.

一般分配律:$\sum_{ i } \sum_{ j } a_{ i } b_j = ( \sum_{ i } a_i ) ( \sum_j b_j )$.

交换顺序法

Example1(等差数列求和)

等差数列求和：

Example2(切比雪夫单调不等式)

令$S = \sum_{ 1 \leq i < j \leq n } ( a_j - a_i ) ( b_j - b_i ) = \sum_{ 1 \leq j < i \leq n } ( a_j - a_i ) ( b_j - b_i )$.

考虑恒等式$[ 1 \leq j < i \leq n ] + [ 1 \leq i < j \leq n ] = [ 1 \leq j , i \leq n ] - [ 1 \leq i = j \leq n ]$.

那么我们有:

又有$( \sum_{ i = 1 }^n a_i ) ( \sum_{ j = 1 }^n b_j ) = n \sum_{ i = 1 }^n a_i b_i - \sum_{ 1 \leq i < j \leq n } ( a_j - a_i ) ( b_j - b_i )$,显然有以下式子:

上式被称为切比雪夫单调不等式.

Example3(拉格朗日恒等式)

即$\sum_{ 1 \leq j < k \leq n } ( a_j b_k - a_k b_j )^2 = ( \sum_{ i = 1 }^n a_i^2 ) ( \sum_{ i = 1 }^n b_i^2 ) - ( \sum_{ i = 1 }^n a_i b_i )^2 \\$.

令$S_n = \sum_{ 1 \leq j < k \leq n } ( a_j b_k - a_k b_j )^2 \\$,有:

扰动法

Example1(等比数列求和)

而$S_{ n - 1 } + ax^n = S_n = a + xS_{ n - 1 }$,有$S_n + ax^{ n + 1 } = a + xS_n , S_n = a \frac{ x^{ n + 1 } - 1 }{ x - 1 }$，其中$x \ne 1$.

Example2(平方和公式)

$S_n = \sum_{ i = 0 }^n i^2$.

如果直接对该公式使用扰动法:

我们无法得到$S_n$的封闭形式,但我们发现我们得到了$\sum_{ i = 1 }^n i$的封闭形式.

那以此类推，我们设$W_n = \sum_{ i = 0 } i^3$

展开和收缩

Example1(平方和公式)

整理得到$S_n$.

Example2

求$\sum_{ i = 1 }^n i^3 \\$.

Problme3

求$\sum_{ i = 1 }^n iq^i ( q \ne 1 )$.

Solution3

ProblemEX2

求$\sum_{ i = 1 }^n ( ai + b ) q^{ i - 1 } ( q \ne 1 )$.

SolutionEX2

令$A = \frac{ a }{ q - 1 } , B = \frac{ b - A }{ q - 1 }$,答案为$( An + B ) q^n - B$.

有限微积分

移位算子

定义移位算子$E$，使得$Ef ( x ) = f ( x + 1 )$.

差分算子

定义差分算子$\Delta f ( x ) = f ( x + 1 ) - f ( x )$，类似于无限微积分中的D算子.

另外,不难发现有$\Delta = E - 1$.

逆差分算子

定义逆差分算子$\Sigma$,可以得到有限微积分的基本定理:

$g ( x ) = \Delta f ( x ) \Leftrightarrow \sum g ( x ) \delta x = f ( x ) + C \\$

这里的$\Sigma$又被称为不定和式,是差分等于$g$的一个函数类.

值得一提的是,这里的$C$与无限微积分中的$C$有一定区别,这里的$C$可以是满足$p ( x ) = p ( x + 1 )$的任意一个函数而不非得是常数函数.

定和式

如果$g ( x ) = \Delta f ( x )$,那么有$\sum \nolimits_{ a }^b g ( x ) \delta x = f ( x ) |^{ b }_a = f ( b ) - f ( a ) \\$.

值得一提的是,如果$a \leq b$,显然有$\sum \nolimits_{ a }^b g ( x ) \delta x = \sum_{ x = a }^{ b - 1 } g ( x ) \\$.

但如果$a > b$,那么$\sum \nolimits_{ a }^b g ( x ) \delta x = - \sum \nolimits_b^a g ( x ) \delta x \\$.

事实上,我们一定有:$\sum \nolimits_a^b g ( x ) \delta x + \sum \nolimits_b^c g ( x ) \delta x = \sum \nolimits_a^c g ( x ) \delta x \\$.

一些基本的公式

类比无限微积分中的$D ( x^m ) = mx^{ m - 1 }$，有:

\Delta(x^{\underline{m}})=mx^{\underline{m-1}}，\sum mx^{\underline{m-1}}\delta x=x^{\underline{m}}+C，m\ne 0\\

\\

类比无限微积分中的$D ( \ln x ) = \frac{ 1 }{ x }$，有:

令H(x)=\sum_{i=1}^x\frac{1}{i}\\\Delta(H(x))=x^{\underline{-1}}，\sum x^{\underline{-1}}\delta x =H(x)+C\\

\\

类比无限微积分中的$D ( e^x ) = e^x$,有:

$\Delta ( 2^x ) = 2^x ， \sum 2^x \delta x = 2^x + C \\$

$\Delta ( c^x ) = ( c - 1 ) c^x ， \sum c^x \delta x = \frac{ c^x }{ c - 1 } + C , c \ne 1 \\$

$\Delta ( c^{ \underline{ x } } ) = \frac{ c^{ \underline{ x + 2 } } }{ c - x } , \sum \frac{ c^{ \underline{ x + 2 } } }{ c - x } \delta x = c^{ \underline{ x } } + C , c - x \ne 0 \\$.

根据组合数公式,有:

$\Delta ( \binom{ x }{ k } ) = \binom{ x }{ k - 1 } \\$.

Example1

仍然考虑平方和公式：

我们有:$k^2 = k^{ \underline{ 2 } } + k^{ \underline{ 1 } } \\$.

那么:

整理即可得到封闭形式.

值得一提的是:

与前面的方法不同，这里没有使用三次的二项式公式，而是使用了二次的斯特林公式负责将一般幂转化为下降幂.

分部求和法则(Abel求和法)

两边取不定和，即可得到分部求和法则:

$\sum u \Delta v = uv - \sum Ev \Delta u \\$.

分部求和用一般和式表达如下,下式又被称为Abel求和法:

$\sum_{ i = l }^{ r - 1 } ( a_{ i + 1 } - a_i ) b_i = a_r b_r - a_l b_l - \sum_{ i = l }^{ r - 1 } a_{ i + 1 } ( b_{ i + 1 } - b_i ) \\$.

Example1

求$\sum_{ k = 0 }^n k 2^k \\$.

根据分部求和法则，我们有:

$\sum x 2^x \delta x = x 2^x - \sum 2^{ x + 1 } \delta x = x 2^x - 2^{ x + 1 } + C \\$.

改为定和式形式，显然有:

Example2

求$\sum_{ k = 0 }^{ n - 1 } kH_k \\$.

令$u ( x ) = H_x , v ( x ) = \frac{ 1 }{ 2 } x^{ \underline{ 2 } } \\$.

带入分部求和法则，显然有:

$\sum xH_x \delta x = \frac{ x^\underline{ 2 } }{ 2 } H_x - \frac{ x^\underline{ 2 } }{ 4 } + C \\$.

带入即可求出原式$= \frac{ n^\underline{ 2 } }{ 2 } ( H_n - \frac{ 1 }{ 2 } ) \\$.

Example3

求$\sum_{ i = 1 }^n \frac{ 2 i + 1 }{ i ( i + 1 ) } \\$.

令$u = ( 2 n + 1 ) , v = - \frac{ 1 }{ i }$,则$\Delta u = 2 , \Delta v = \frac{ 1 }{ i ( i + 1 ) }$.

根据分部求和法则,有:

Example4

求$\sum_{ i = 0 }^{ n - 1 } \frac{ H_k }{ ( k + 1 ) ( k + 2 ) } \\$.

令$u = H_n , v = - \frac{ 1 }{ n + 1 } , \Delta u = \frac{ 1 }{ n + 1 } , \Delta v = \frac{ 1 }{ ( n + 1 ) ( n + 2 ) } \\$.

根据分部求和法则,有:

基础数论在数列中的应用

Example

令$A = \{ 2 n - 1 | n \in \mathbb{ N }_{ + } \} , B = \{ 3 n - 1 | n \in \mathbb{ N }_{ + } \}$.求$A \cap B$,以及$A \cup B$的最小的一百项之和.

对于前者,我们知道:

所以$A \cap B = \{ 6 n - 1 | n \in \mathbb{ N }_{ + } \}$.

而同理,$x \in A \cup B \Leftrightarrow x \equiv - 1 / - 2 / - 3 / - 5 \pmod{ 6 }$.于是后者是简单的.

构造双射在数列中的应用

设$A = \{ x | x = 2 n - 1 , n \in \mathbb{ N }_+ \} , B = \{ x | x = 2^n , n \in \mathbb{ N }_+ \}$,现在将$A \cup B$中的元素排序并提取成一个数列$a$,求使得$S_n > 12 a_n$最小的正整数$n$.

写出数列,它长这样:

不妨设$n$在第$r$行$c$列,显然$( r , c )$和$n$构成双射.

那么我们现在无非有两个思路:要么找到一个方式使得对于给定的$n$能快速表达$( r , c )$,要么反之.显然反之比较简单.

考虑设前$k$行共有$W_k$个数,不难发现$W_{ k + 1 } = W_k + 2^{ k - 1 } + 1 , W_k = 2^{ k - 1 } + k$.

显然,对于$( r , c )$来说,它对应的$n$就是$W_{ r - 1 } + c$.

令$SR_{ r }$为前$r$行数字之和,不难发现$SR_r = 2^{ r + 1 } - 2 + ( 2^{ r - 1 } )^2$.

接下来考虑找到这个最小的$n$,显然$r \ne 1$,接下来只考虑$r \geq 2$的情况.

那么我们可以轻松写出$S_n$和$a_n$的表达式,下面直接给出:

讨论一下$[ c = 2^{ r - 2 } + 1 ]$这个判定式取$0$还是取$1$,这样就做完了.

不等式放缩在数列中的应用

几何导论

三角相关

三角恒等变换

两角和差公式

倍角公式

半角公式

和差化积

值得一提的是,如果你对和差化积特别熟悉,你不难发现下面这个式子:

如果细看会发现,这其实就是和差化积与二倍角公式并用得到的推论,但实际上用处远比和差化积要多.

积化和差

万能公式

令$w = \tan \frac{ A }{ 2 }$,则:

当然,这个所谓的万能公式其实一点用都没有,因为我们有更强大的公式:

补充公式

周期函数与初等数论

我们知道,处理三角中的周期性问题时,需要设一些取值为整数的$k$来解决问题,这引发我们思考:是否可以将初等数论中的模法来解决这一类问题呢?

Example1

已知函数$f ( x ) = \sin ( \omega x + \varphi ) , w > 0$,$f ( - \frac{ \pi }{ 6 } ) = 0 , f ( \frac{ \pi }{ 2 } ) = - 1$,求$w$和$\varphi$的表达式.

正确做法应该是强设$k_1 , k_2$,但我们来使用模法.

必须要注意的一点是,我们这里的$\omega$和$\varphi$都不是整数,这意味着我们必须时刻保证同余式子左侧是整数,也就是在操作的时候不可以使用任何逆元!换句话说,你两边同时做乘法的时候,只可以同时乘以整数,不可以同时乘以分数.

不妨令$\frac{ \pi }{ 2 }$为单位$1$,我们必有以下式子:

下面推导$\omega$,首先将上面两个式子直接相减,立有:

对于$\varphi$,考虑类似的做法,将第一个式子乘以$3$后与第二个式子相加,立有:

这样我们得到的必须满足的条件就有以下几条:

向量相关

旋转模型

自己瞎起的名字.

Example1

已知$AB = 2 , AC = 1 , \angle A = \theta$,$BC$绕$B$点顺时针旋转$\frac{ \pi }{ 3 }$得到$BD$,求以$\theta$表示$S_{ \triangle CBD }$.

先来说文化课做法,我们直接表示$S$,令$\alpha = \angle ABC$:

对于这个式子,我们发现如果我们能得到$| BD | \sin ( \alpha )$和$| BD | \cos ( \alpha )$就可以解决了对吧.

这两个怎么求得呢?我们发现$BD$是$\alpha$的一条临边.观察正弦定理和余弦定理可知,正弦定理可以帮助我们求出$| BD | \sin \alpha$,余弦定理可以帮助我们求出$| BD | \cos \alpha$.

然而,如果我们再冷静一下,会得到一个更厉害一点的做法:

我们直接建系,立刻可以求出$\overrightarrow{ AB }$和$\overrightarrow{ BC }$的坐标表示,将$\overrightarrow{ BC }$用旋转矩阵转过去,拿叉积算一下两个向量所生成的三角形面积即可.

如果要把这个做法对应到文化课可以拿到分的做法的话,首先叉积可以去掉,改为直接暴力算.至于旋转的话可能需要一些操作例如三角换元之类的.

爪子模型

比起套模型,我们来总结一下向量中的两个做题法则:

1. 如果存在两条不共线向量,已知它们的夹角以及边长,这个题至少可以通过设单位向量暴力运算解决.

2. 如果通篇题目不涉及边长,或者是涉及边长,但所求是角,将某个边长当作$1$是一定没有问题的,这样可以少掉一个未知量,为将来的做题提供更明确的道路.

直接来看题:

Example1

$\triangle ABC$中,$b^2 = ac$,点$D$在$AC$上且满足$BD = b$,有$\overrightarrow{ AD } = 2 \overrightarrow{ DC }$,求$\cos \angle ABC$.

这题通篇没有提到任何的边长,我们可以直接钦定$c = 1$,于是有$b^2 = a$.

考虑我们要求$\cos \angle ABC$,而我们有一条很奇怪的边$BD$,似乎不满足任何性质,我们立刻想到要把它用$\angle ABC$的两条边向量表示,除此之外没有任何别的表示方式.

后面就没有什么了,这题的难点在于后面的解方程过程,但只要你敢让$c = 1$,后面的解方程极其简单.

奔驰定理及三角形四心

奔驰定理

对于$\triangle ABC$内一点$P$,立有$S_{ \triangle PBC } \overrightarrow{ PA } + S_{ \triangle PAC } \overrightarrow{ PB } + S_{ \triangle PAB } \overrightarrow{ PC } = \vec{ 0 }$.

看到的证明都略麻烦,下面给出一个容易理解的证明.

我们物理上学过拉密定理,其实也就是运用三角形法则以及正弦定理.利用拉密定理,令$a = PA , b = PB , c = PC$,我们要证奔驰定理,也就是要证明:

考虑$| \frac{ \overrightarrow{ PA } }{ a } | = | \frac{ \overrightarrow{ PB } }{ b } | = | \frac{ \overrightarrow{ PC } }{ c } | = 1$,后者根据拉密定理显然成立.

外心

有正弦定理,$| \overrightarrow{ OA } | = | \overrightarrow{ OB } | = | \overrightarrow{ OC } | = \frac{ a }{ 2 \sin A }$.

考虑三个三角形的面积可以表示为$\frac{ r^2 }{ 2 } \sin \theta$,又考虑到圆中的$\theta$是圆心角是圆周角的两倍,立有$\sin ( 2 A ) \overrightarrow{ OA } + \sin ( 2 B ) \overrightarrow{ OB } + \sin ( 2 C ) \overrightarrow{ OC } = \vec{ 0 }$.

下面给出一个例题:

Example1

在$\triangle ABC$中,$AB = 2 , BC = \sqrt{ 10 } , AC = 3$,若$O$是其外心,且$\overrightarrow{ AO } = p \overrightarrow{ AB } + q \overrightarrow{ AC }$.

先给出我一开始的想法:

在没学奔驰定理之前,我们看到这个外心,第一反应肯定是使用$| OA | = | OB | = | OC |$,也就是这三个长度都是好求的.因此,我们考虑对上面的式子两边平方,得到一个关于$p , q$的方程.但是这样没有解决问题.

考虑我们只用了$| OA |$,用上$| OB |$,这样的话我们两边同时加上$\overrightarrow{ BA }$,就可以得到$p , q$的另一个方程,可以解出两组解,直接舍也可以舍,不然的话根据$| OC |$也可以舍一个解.

但是这样太蠢了啊,我们考虑直接凑奔驰定理:

考察奔驰定理,立有$\frac{ p + q - 1 }{ \sin ( 2 A ) } = \frac{ p }{ \sin ( 2 B ) } = \frac{ q }{ \sin ( 2 C ) }$,简单题.

Example2

已知相异两点$O , H$分别为$\triangle ABC$的外心和垂心,若$\overrightarrow{ OH } = m ( \overrightarrow{ OA } + \overrightarrow{ OB } + \overrightarrow{ OC } )$,求$m$.

这题要用到的性质是,我们一定要知道$( \overrightarrow{ OB } + \overrightarrow{ OC } ) \cdot \overrightarrow{ BC } = 0$,这也是外心的一个很重要的性质.

由此,我们让左边凑出$\overrightarrow{ AH }$,然后两边同时乘以$\overrightarrow{ BC }$就可以解决.注意到最后解方程的时候要么$m = 1$,要么三角形等边,但是我们声明过$O , H$相异两点.

重心

首先重心将中线三等分,这个我竟然一直没细想过怎么证明啊,只是觉得倍长中线肯定能证明.

事实上用不到那么麻烦,你直接连接两个中点,立有中位线,然后以重心为两个三角形的顶点,立有一组对顶角且对边平行的$1 : 2$的相似.

又考察三条中线将整个三角形分成了六部分,这六部分的面积是相等的.

为啥呢?因为你可以先把三角形分成三部分(也就是每个顶点连到重心),然后将这三部分内部的两个小三角形证明面积相等(因为此时重心是它的顶点,沿着中线连下去就还是这个三角形的中线),再利用上面的三等分结论就显然了啊.

结合奔驰定理,立有若$O$是重心,则必有$\overrightarrow{ OA } + \overrightarrow{ OB } + \overrightarrow{ OC } = \vec{ 0 }$.

然后听说有个物理理想实验的理解方式,大概是说这与力矩结合一下就可以得到这是他物理重心的结论,不会.

垂心

若$O$是重心,立有$\overrightarrow{ OA } \cdot \overrightarrow{ BC } = 0$,将$\overrightarrow{ BC } = \overrightarrow{ BO } + \overrightarrow{ OC }$,立有$\overrightarrow{ OA } \cdot \overrightarrow{ OB } = \overrightarrow{ OA } \cdot \overrightarrow{ OC } = \overrightarrow{ OB } \cdot \overrightarrow{ OC }$.同时顺带证明了三条高交于一点.

根据奔驰定理还有$\overrightarrow{ OA } \tan A + \overrightarrow{ OB } \tan B + \overrightarrow{ OC } \tan C = \vec{ 0 }$.

内心

根据奔驰定理,立有$a \overrightarrow{ OA } + b \overrightarrow{ OB } + c \overrightarrow{ OC } = \vec{ 0 }$.

立体几何相关

基本概念

直线

使用直线的方向向量$\vec{ s } = ( n , m , p )$和直线上一点$M_0 = ( x_0 , y_0 , z_0 )$.那么方程显然为:

如果换元,我们还有参数方程:

平面

使用平面上的一点$P_0 ( x_0 , y_0 , z_0 )$和该平面的法向量$\vec{ n }$来表示一个平面,不妨设$\vec{ n } = ( A , B , C )$,则该平面的方程显然为:

如果我们令$D = - ( Ax_0 + By_0 + Cz_)$,那么平面方程为:

夹角

两直线夹角.

直接求方向向量的夹角,然后取正值.

对于方向向量分别是$\vec{ s_1 } = ( n_1 , m_1 , p_1 ) , \vec{ s_2 } = ( n_2 , m_2 , p_2 )$,也就有$\varphi = \arccos ( \frac{ | \vec{ s }_1 \cdot \vec{ s }_2 | }{ | \vec{ s }_1 | | \vec{ s }_2 | } ) \\$.

直线与平面的夹角

同样使用向量,不妨设方向向量$\vec{ s } = ( n , m , p )$,法向量$\vec{ f } = ( a , b , c )$,那么$\varphi = \arcsin ( \frac{ | \vec{ s } \cdot \vec{ f } | }{ | \vec{ s } | | \vec{ f } | } )$.

另外,由上面这个式子,不难得到一些特殊情况下的判定标准:

1. 若直线与平面平行,则$am + bn + cp = 0$.

2. 若直线与平面垂直,则$\frac{ a }{ m } = \frac{ b }{ n } = \frac{ c }{ p }$.注意这里分母可能除以$0$,我们实际上应该是三个形如$a = mt$的参数方程,这里简化了.

交点

联立方程硬解.

基本定理

参考:https://zhuanlan.zhihu.com/p/401766934

三余弦定理(最小角定理)

这个定理说明直线与平面的夹角,是所有包含直线的平面与这个平面形成的夹角中最小的那一个.并且偏移量决定了差距.

三正弦定理(最大角定理)

这个定理说明二面角是另一个平面上的直线与平面的夹角中最大的那个,并且偏移量决定了差距.

圆锥曲线

约定

对于所有对称情况结论只讨论一种(其它情况可通过坐标变换得到),但是例题以及做题方法除外.

大部分涉及斜率的存在性问题,统一不予考虑.如果遇到实际例题,只需特别处理那几个特殊情况即可($mx + ny = 1$需要判断过原点的直线,$y = kx + b$需要判断平行于$y$轴的直线),显然大部分情况下是平凡的.

椭圆

定义

第一定义

平面内与两定点$F_1 , F_2$距离之和为常数($> | F_1 F_2 |$)的点轨迹.即:$\{ P \mid | F_1 P | + | F_2 P | = 2 a , F_1 ( - c , 0 ) , F_2 ( c , 0 ) \}$.

第二定义

平面内一动点到定点与准线($x = \pm \frac{ a^2 }{ c }$)的距离比是常数$e = \frac{ c }{ a }$的点轨迹,即$\{ P \mid \frac{ | PF_1 | }{ d_1 } = \frac{ | PF_2 | }{ d_2 } = \frac{ c }{ a } = e , F_1 ( - c , 0 ) , F_2 ( c , 0 ) \}$.

第三定义

平面内一动点到两定点$A_1 ( - a , 0 ) , A_2 ( a , 0 )$的斜率乘积等于定值$e^2 - 1$的轨迹称为椭圆.

椭圆方程

标准方程

由定义不难得到椭圆的标准方程:$\frac{ x^2 }{ a^2 } + \frac{ y^2 }{ b^2 } = 1 ( b^2 = a^2 - c^2 , a > b > 0 )$.

一般方程

$nx^2 + my^2 = 1 ( n , m \geq 0 )$,这样设的好处在于如果不知道焦点的位置,仍然可以设方程并进行代数运算,最后判断一下$n$和$m$的大小关系即可.

椭圆重要元素

焦半径

若$P ( x_0 , y_0 )$,则$| PF_1 | = a + ex_0$,$| PF_2 | = a - ex_0$.

焦点弦

过$F_1$的弦$| AB | = 2 a + e ( x_1 + x_2 )$.

过$F_2$的弦$| AB | = 2 a - e ( x_1 + x_2 )$.

注意到焦点弦最短时$x_1 = x_2$.

焦点三角形

即$\bigtriangleup PF_1 F_2$,令$\theta = \angle F_1 PF_2$,有以下性质:

1. $C = 2 a + 2 c$.

2. $S = b^2 \tan \frac{ \theta }{ 2 } = c | y_P |$.

3. $\cos \theta \geq 1 - 2 e^2$(当$P$在短轴上取等).

4. $| PF_1 | | PF_2 | = \frac{ 2 b^2 }{ 1 + \cos \theta }$.

Example

Example1

已知椭圆$\frac{ x^2 }{ a^2 } + \frac{ y^2 }{ b^2 } = 1$,$P$是椭圆上一点,$\angle F_1 PF_2$的角平分线交$x$轴于$Q ( \frac{ c }{ 4 } , 0 )$,求离心率取值范围.

注意到$S_{ \bigtriangleup QPF_1 } = \frac{ 5 }{ 3 } S_{ \bigtriangleup QPF_2 }$,又有$Q$到$PF_1$和$PF_2$的距离相等,用等积法,显然$PF_1 = \frac{ 5 }{ 4 } a , PF_2 = \frac{ 3 }{ 4 } a$.

然后用三角形不等式做差就行.$2 c > \frac{ 1 }{ 2 } a , \frac{ 1 }{ 4 } < e$

双曲线

定义

第一定义

平面内与两定点$F_1 , F_2$距离之差为常数($> | F_1 F_2 |$)的点轨迹.即:$\{ P \mid | | F_1 P | - | F_2 P | | = 2 a , F_1 ( - c , 0 ) , F_2 ( c , 0 ) \}$.

第二定义

平面内一动点到定点与准线($x = \pm \frac{ a^2 }{ c }$)的距离比是常数$e = \frac{ c }{ a }$的点轨迹,即$\{ P \mid \frac{ | PF_1 | }{ d_1 } = \frac{ | PF_2 | }{ d_2 } = \frac{ c }{ a } = e , F_1 ( - c , 0 ) , F_2 ( c , 0 ) \}$.

第三定义

平面内一动点到两定点$A_1 ( - a , 0 ) , A_2 ( a , 0 )$的斜率乘积等于定值$e^2 - 1$的轨迹称为双曲线.

双曲线重要元素

焦半径

若$P ( x_0 , y_0 ) , ( x_0 > 0 )$,则$| PF_1 | = a + ex_0$,$| PF_2 | = - a + ex_0$.

渐近线

$y = \pm \frac{ b }{ a } x$.

如果换个方向的双曲线,事实上就是把双曲线标准方程的等号右边写成$0$得到的两个直线方程.

焦点三角形

即$\bigtriangleup PF_1 F_2$,令$\theta = \angle F_1 PF_2$,有以下性质:

1. $S = \frac{ b^2 }{ \tan \frac{ \theta }{ 2 } }$.

抛物线

定义

第一定义

平面内一动点到定点与准线的距离相等的点轨迹.

抛物线重要元素

焦点弦

我曾经以为整理完二项式恒等式后再也不会有同样恐怖的结论群了

直线$AB$为过$y^2 = 2 px ( p > 0 )$焦点的弦,$A ( x_1 , y_1 ) , B ( x_2 , y_2 )$,倾斜角为$\theta$,准线与$x$轴交点为$E ( - \frac{ p }{ 2 } , 0 )$,作$AA_1$,$BB_1$垂直于准线于$A_1 , B_1$,则:

1. $| AF | = x_1 + \frac{ p }{ 2 }$,$| BF | = x_2 + \frac{ p }{ 2 }$,$| AB | = x_1 + x_2 + p , \frac{ 1 }{ | FA | } + \frac{ 1 }{ | FB | } = \frac{ 2 }{ p }$.

2. $| AF | = \frac{ p }{ 1 - \cos \theta } , | BF | = \frac{ p }{ 1 + \cos \theta } , | AB | = \frac{ 2 p }{ \sin^2 \theta }$.

3. $x_1 x_2 = \frac{ p^2 }{ 4 }$,$y_1 y_2 = - p^2$.

4. $S_{ \bigtriangleup AOB } = \frac{ p^2 }{ 2 \sin \theta }$.

5. $k_{ AE } + k_{ BE } = 0$.

6. $A , O , B_1$三点共线,$B , O , A_1$三点共线.

7. 以$AB$为直径的圆与抛物线的准线相切.

8. 以$A_1 B_1$为直径的圆与$AB$相切.

9. 以$AF$或$BF$为直径的圆与$y$轴相切.

通用解法

联立方程

点参

不设直线斜率,直接通过设点坐标并且导出直线斜率.

这种做法通常要么不能做,要么能做并且非常简单,需要强大的构造能力.

弦长公式

已知直线$l$上有两点$N ( x_1 , y_1 ) , M ( x_2 , y_2 )$,这条直线的斜率为$k$,那么$| NM | = \sqrt{ 1 + k^2 } | x_1 - x_2 | = \sqrt{ 1 + \frac{ 1 }{ k^2 } } | y_1 - y_2 |$.

点差法

设圆锥曲线上两点$A ( x_1 , y_1 ) , B ( x_2 , y_2 )$,其中点$M ( x_0 , y_0 )$,有$2 x_0 = x_1 + x_2 , 2 y_0 = y_1 + y_2$.

把这两个点带入圆锥曲线方程并做差,可以通过平方差公式消去几项.然后可以表示出直线斜率,大概做做.

垂径定理

已知直线$l$与曲线交于两点$N ( x_1 , y_1 ) , M ( x_2 , y_2 )$,这条直线的斜率为$k$,$MN$的中点为$P ( x_0 , y_0 )$,那么:

1. 在椭圆$\frac{ x^2 }{ a^2 } + \frac{ y^2 }{ b^2 } = 1 ( a > b > 0 )$中,$k \frac{ y_0 }{ x_0 } = - \frac{ b^2 }{ a^2 } = e^2 - 1$.

2. 在双曲线$\frac{ x^2 }{ a^2 } - \frac{ y^2 }{ b^2 } = 1$中,$k \frac{ y_0 }{ x_0 } = \frac{ b^2 }{ a^2 } = e^2 - 1$.

3. 在抛物线$y^2 = 2 px ( p > 0 )$中,$k = \frac{ p }{ y_0 } = \frac{ x_0 }{ p }$.

小联立

如果题目中有两条直线,它们之间的斜率满足一定关系,那么可以通过把这两个直线的斜率都设出来,然后再添加一个方程来实现.

这个方法的优点在于,有的时候分离出的方程会让原始式子简单很多.

缺点在于,有的时候会让原始式子复杂很多.

大联立

直接设主要直线的方程,然后其它直线均通过主要直线方程导出.

最常用的方法.

齐次化

本质是平移坐标系.

简单来说,如果图中有两条有公共点的直线$PA$,$PB$,我们可以将公共点$P$平移至原点,这样$PA$和$PB$的方程都方便表达.然后设$AB$的方程为$mx + ny = 1$(注意这个式子不能表示过原点的直线,需要特判).

由于进行了平移,新得到的圆锥曲线方程可能存在一次项和零次项,我们将一次项乘以$mx + ny$,零次项乘以$( mx + ny )^2$,这样就得到了一个齐次式子.将两边同时除以$x^2$后就得到了一个和$k = \frac{ y }{ x }$有关的方程.

换句话说,某种意义下,齐次化应该算是点参和大联立的结合体:大部分情况下,能用点参的条件是斜率可以用点坐标轻松表示,而如果点的坐标比较奇怪就没办法表示,而齐次化可以完美解决这个问题.

非对称性韦达定理

大概就是求出一个用一个方程的根表达的式子,然后需要继续化简.

通常的做法是寻找方程的$x_1 x_2$和$x_1 + x_2$之间的关系来做.

当然还有一种情况是问形如$\frac{ Ax_1 + Bx_2 }{ Cx_1 + Dx_2 }$是定值的问题,这个时候一定有$\frac{ A }{ C } = \frac{ B }{ D }$.

还没完,非对称性韦达定理的应用巨多,例如令$w = \frac{ x_1 }{ x_2 }$,自然有$w + \frac{ 1 }{ w } + 2 = \frac{ ( x_1 + x_2 )^2 }{ x_1 x_2 }$.

还比如有$y_2 = ny_1 + m$,我们可以用配凑技巧改写作$( y_2 + w ) = k ( y_1 + w )$,也就有$\frac{ y_2 + w }{ y_1 + w } = k$,类似上面的做法也可以求.

硬解定理

设直线$y = kx + \varphi$与曲线$\frac{ x^2 }{ m } + \frac{ y^2 }{ n } = 1$相交于$A ( x_1 , y_1 )$和$B ( x_2 , y_2 )$.

那么联立方程是:$( n + mk^2 ) x^2 + 2 k \varphi mx + m ( \varphi^2 - n ) = 0$.

判别式:$\Delta = 4 mn ( n + mk^2 - \varphi^2 )$.

韦达定理:

配凑法

参考:https://zhuanlan.zhihu.com/p/521025768.

先猜结论,再对着结论构造一个对称式子,从而声明这个式子就是答案.

问题在于咋构造,通常前面的部分还是按部就班来.最后来一步”注意到”来机械降神.

感觉没什么太大用,因为小题直接猜结论,大题按部就班不会太慢.

应用

Example1(大联立/点参)

已知抛物线$y^2 = 4 x$,若$A , B$位于抛物线上$x$轴上方不同的两点,直线$OA , OB$的斜率分别为$k_1 , k_2$,且满足$k_1 k_2 - 4 = 4 k_1 + 4 k_2$,求证:$AB$过定点,并求出$k_{ AB }$的取值范围.

注意到$k_1$和$k_2$之间的关系很复杂,这个时候就别惦记你那小联立了,老老实实拿大联立做吧.

设$AB : y = kx + b$,则$A ( x_1 , kx_1 + b ) , B ( x_2 , kx_2 + b )$,显然$k_1 = k + \frac{ b }{ x_1 } , k_2 = k + \frac{ b }{ x_2 }$.

直接带入方程,有:

而直接大联立得到的式子是:

带入,得到$k - b = 4$,因此过定点$( - 1 , - 4 )$,与$kb < 1$联立得到$k < 2 + \sqrt{ 5 }$.

还没完,这种题一定要检查一遍条件.注意到$AB$为$x$轴上方两点的性质没用到,这意味着$y_1 y_2 > 0 \land y_1 + y_2 > 0$,带入方程得到:

化简得到$\begin{cases}b > 0 \ k > 0\end{cases}$,解得$k > 4$,于是$k \in ( 4 , 2 + \sqrt{ 5 } )$.

这啥暴力计算啊…没啥好方法嘛?

首先显然的一点是:由于是在做抛物线,直线方程设成反式肯定会好算很多.(整理到这里才意识到可以设反式,但是懒得改前面的内容了)

看上去式子太复杂确实不太可能用小联立做.问题在于,$OA$和$OB$的斜率看上去都很好表示,为何不能用点参做呢?

我们尝试直接用点参:

我们毫不费力就导出了用反式之后做的式子,这仿佛在预示我们点参是有用的,让我们继续:

显然过定点$( - 1 , - 4 )$,并且通过$y_1$和$y_2$的关系也很好求斜率的范围.

另外值得一提的是,通常情况下,不要用那个$\frac{ x - x_1 }{ x_1 - x_2 } = \frac{ y - y_1 }{ y_1 - y_2 }$的方程直接表示直线,你做抛物线的很重要的一个目标是通过消参来让式子变得更简洁,而不是去硬着头皮算,上面这个直线方程咋消参啊.

Example2(齐次化)

已知椭圆$\frac{ x^2 }{ 4 } + y^2 = 1$,$P , Q$在椭圆上,$A ( 2 , 0 )$,$k_{ AP } k_{ AQ } = \frac{ 1 }{ 20 }$,求证:$PQ$过定点.

注意到$A ( 2 , 0 )$,设$P ( x_1 , y_1 ) , Q ( x_2 , y_2 )$,$PQ : m ( x - 2 ) + yn = 1$,那么我们要求的也就是$x - 2$和$y$之间的关系.

第一步先要把椭圆方程配出来,显然$\frac{ x^2 }{ 4 } + y^2 = 1 \Rightarrow \frac{ ( x - 2 )^2 }{ 4 } + ( x - 2 ) + y^2 = 0$.

显然?这咋配的啊.

其实简单来说也就是令$x ‘ = x - 2 , y ‘ = y$,我们有$x = x ‘ + 2 , y = y ‘$,带入就可以得到关于$x ‘ , y ‘$的方程,然后再带回$x$和$y$就行.

我们开始推导:

令$k = \frac{ y }{ x - 2 }$,也就得到了$4 n + 1 + 4 mk + 4 k^2 = 0$.用一遍韦达定理,有:$k_1 k_2 = \frac{ 4 n + 1 }{ 4 } = \frac{ 1 }{ 20 } , n = - \frac{ 1 }{ 5 }$.

也就有:$PQ : - \frac{ 1 }{ 5 } ( x - 2 ) + my = 1$,显然过定点$( - 3 , 0 )$.

Example3(小联立)

已知椭圆$\frac{ x^2 }{ 9 } + y^2 = 1$,$P , Q$是该椭圆上两动点,$M , N$分别为$P , Q$在$x$轴上的射影,而且$k_{ OP } k_{ OQ } = - 1$,记$S = S_{ \bigtriangleup OPM } + S_{ \bigtriangleup OQN }$,求$S$的最大值.

出现了两条直线!提问:使用大联立还是小联立.

考虑这么一个事实:大联立的用处应该体现在直线$PQ$很重要的时候,而这个题除了$P , Q$两点以外,和$PQ$半毛钱关系都没有.而且如果使用小联立,那么两个斜率之间的关系也很好表示,因此我们选择小联立.

设$P ( x_1 , y_1 ) , Q ( x_2 , y_2 )$,$k = \frac{ y_1 }{ x_1 } , - \frac{ 1 }{ k } = \frac{ y_2 }{ x_2 }$:

而联立方程,有:

代入计算即可求解.

当然这个题斜率形式很好看,拿点参肯定也是可以做的,但是没啥必要,因为斜率关系很好看.

等一下,大联立真的没啥希望嘛?

确实没啥希望,因为直线$PQ$有两个未知量,我们还需要拿$k_{ OP } k_{ OQ } = - 1$限制它们的关系,不如直接小联立.

Example4(非对称性韦达定理)

已知椭圆$\frac{ x^2 }{ 2 } + y^2 = 1$,$F ( 1 , 0 )$,直线$l$过$F$且交椭圆于$A , B$两点.求问:$x$轴上是否存在异于$F$的一点$Q$,使得$\frac{ k_{ QA } }{ k_{ QB } }$是定值.

直接设$AB : x = ky + 1$,$Q ( q , 0 )$.我们有:

坏了,这咋做.

我们用一下韦达定理得到:

注意到$\frac{ ( y_1 + y_2 ) }{ 2 } = k ( y_1 y_2 )$,代入,有:

若是定值,那么就有:$\frac{ 3 - 2 q }{ 1 } = \frac{ 1 }{ 3 - 2 q }$,解得$q_1 = 1 ( F )$,$q_2 = 2 ( Q )$.

所以$Q ( 2 , 0 )$.

Example5(配凑法)

已知椭圆$\frac{ x^2 }{ 4 } + \frac{ y^2 }{ 3 } = 1$,过$F ( - 1 , 0 )$的直线交椭圆于$M , N$两点,过$M$作直线$x = - 4$的垂线,垂足为$E$,求证:$EN$过定点.

根据对称原理,显然这个定点一定在$x$轴上.

我们先写大联立的式子:设$MN : x = - 1 + ky$,带入有$( 3 m^2 + 4 ) y^2 - 6 my - 9 = 0$.再设$M ( x_1 , y_1 ) , N ( x_2 , y_2 )$,自然有:

接下来呢,我们想一下我们要求什么:我们要求出$EN$的表达式:形如$y - m = k ( x - n )$,然后声明$( n , m )$是定点.

这又意味着啥呢,这意味着在这条直线上,除了那个定点以外,一定有$k = \frac{ y - m }{ x - n }$.而我们现在有两个点$E ( - 4 , y_1 )$和$N ( x_2 , y_2 )$,又猜出$m = 0$,也就是我们要找到一个$n$满足$\frac{ y_1 }{ - 4 - n } = \frac{ y_2 }{ x_2 - n }$.

我们倒着推:

这是啥,这是非对称性韦达定理.

这一步已经可以暴力化简了.但那样还不如直接做呢.所以我们直接选择从非对称性韦达定理的角度推过来.

观察韦达定理的关系式,我们有:

做到这一步发现要做完了,不难发现$n = \frac{ 5 }{ 2 }$.

等一下,最后咋就这么巧就凑出来了呢?

因为你都确定了$m = 0$了,肯定是可以凑出来的,除非它真的不过定点.

极点极线

定义

几何定义

感觉这个定义大概率没啥用

过不在二次曲线上的一点$P$作直线$l$交二次曲线于$M , N$两点(离$P$近的是$M$),则在$l$上有且只有一点$Q$,使得$| MQ | | NP | = | MP | | NQ |$(即$P , Q , M , N$构成一调和点列).当$l$绕着$P$旋转时,$Q$的轨迹是一条直线$p$(或一部分),这条直线$p$叫做点$P$关于二次曲线的极线,而$P$叫做$p$关于该曲线的极点.

以椭圆为例子,接下来我们声明:$p : \frac{ x_0 x }{ a^2 } + \frac{ y_0 y }{ b^2 } = 1$.

证明:我有一个绝妙的证法,可惜这里地方太小,写不下.

代数定义

对于不在二次曲线$C : Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0$上的一点$P ( x_0 , y_0 )$,我们称它的极线为$p : Axx_0 + B \frac{ x_0 y + y_0 x }{ 2 } + Cyy_0 + D \frac{ x + x_0 }{ 2 } + E \frac{ y + y_0 }{ 2 } + F = 0$.

而对于在二次曲线上的点,我们也可以这么定义,不难发现此时极线就是过极点的切线.

证明:我有一个绝妙的证法,可惜这里地方太小,写不下.

基本性质

性质1(配极原理)

对于同一条二次曲线$C$,如果点$P$的极线经过点$Q$,那么点$Q$的极线经过点$P$.

证明:我有一个绝妙的证法,可惜这里地方太小,写不下.

性质2(配极原理推论)

两点连线的极点是这两点的极线的交点;两直线交点的极线是这两直线的极点的连线.

证明:由性质1,显然.

性质3(极点与极线的位置关系)

ps:对于双曲线而言:我们所说的在内部指的是平面中被双曲线分为的三部分平面中对称的那两部分.抛物线类似.

1. 设四边形$ABCD$(对边不平行)内接于二次曲线$C$,则对角线交点$P$的极线是两组对边交点的连线.反之同理,若$P$在二次曲线内部,那以这个点为对角线交点的内接四边形对边交点的连线就是它的极线.这告诉我们:若一个点在二次曲线内,那它的极线一定在二次曲线外.反之亦然成立.

2. 若一个点在二次曲线上,那它的极线就是过这个点的二次曲线的切线.

3. 若一个点在二次曲线外,那它的极线就是过这个点向二次曲线作两条切线,这两条切线与二次曲线的交点的连线.

证明:我有一个绝妙的证法,可惜这里地方太小,写不下.

使用方法

通过极点极线猜结论,然后想办法证明结论.

Example1

已知$\frac{ \cos \theta }{ a } + \frac{ \sin \theta }{ b } = 1$,求证:$\frac{ 1 }{ a^2 } + \frac{ 1 }{ b^2 } \geq 1$.

设直线$l : \frac{ x }{ a } + \frac{ y }{ b } = 1$,$M ( \cos \theta , \sin \theta )$,则$M$在$l$上.

又注意到$M$显然是在单位圆上,而$l$是单位圆关于$P ( \frac{ 1 }{ a } , \frac{ 1 }{ b } )$的极点.又注意到$l$与单位圆至少有一个交点,因此$P$要么在圆上要么在圆外,得证.

Example2

已知椭圆$\frac{ x^2 }{ 4 } + \frac{ y^2 }{ 3 } = 1$,$A_1 ( - 2 , 0 ) , A_2 ( 2 , 0 ) , D ( \frac{ 1 }{ 2 } , 0 )$,过$D$的直线交椭圆于$P , Q$两点(不与$A_1 , A_2$重合).$A_1 P \cap A_2 Q = M$,$A_1 Q \cap A_2 P = N$,设$k_1 = k_{ A_1 P } , k_2 = k_{ A_1 Q }$.求证:$k_1 k_2$是定值,求出这个定值并求出$\bigtriangleup DMN$面积的最小值.

一眼极点极线,通过极点极线知识不难得知$MN : x = 8$.

我们先来看已知$MN : x = 8$之后怎么做:

设$P ( x_1 , y_1 ) , Q ( x_2 , y_2 )$,再设$PQ : x = ky + \frac{ 1 }{ 2 }$,则:$k_1 k_2 = \frac{ y_1 }{ x_1 + 2 } \frac{ y_2 }{ x_2 + 2 }$,不难算出$k_1 k_2 = - \frac{ 9 }{ 20 }$.

此时$S_{ \bigtriangleup DMN } = | MN | | 8 - \frac{ 1 }{ 2 } | \frac{ 1 }{ 2 }$.不难发现只需求出$| MN |_{ \min }$即可.而$MN \bot x$轴,所以$| MN | = | y_M - y_N |$.

接下来咋做?第一问求得$k_1$和$k_2$的关系不能白求啊!

我们有$A_1 P : x = - 2 + \frac{ 1 }{ k_1 } y , A_1 Q : x = - 2 + \frac{ 1 }{ k_2 } y$,带入$x = 8$,求得$y_M = 10 k_1 , y_N = 10 k_2$.

于是$| MN | = 10 | k_1 - k_2 |$.注意到$k_1 > 0 \land - k_2 > 0 \land k_1 ( - k_2 ) = \frac{ 9 }{ 20 }$,显然可以用基本不等式计算,最后得到$S_{ \min } = \frac{ 45 \sqrt{ 5 } }{ 2 }$.

好,问题就差一步极点极线的证明了.

这个时候,我们先说出$A_1 Q : x = - 2 + \frac{ y_2 }{ x_2 + 2 } y , A_2 P : x = 2 + \frac{ y_1 }{ x_1 - 2 } y$,然后我们声明这两条直线的交点的横坐标一定是$8$,然后代入验证即可.

好吧我也觉得很无赖,没办法.

隐函数求导

大概是这样的:

拿椭圆举例子,我们假设椭圆方程是$\frac{ x^2 }{ a^2 } + \frac{ y^2 }{ b^2 } = 1$.

我们将$y$看作$x$的函数,对两边求导,自然得到:

这是个方程,你可以解得$y ‘ = - \frac{ b^2 x }{ a^2 y }$.而这就是椭圆过$( x , y )$这一点切线的斜率.用点斜式就可以得到方程.

目前没发现这方法在除了推导切线方程以外有啥用.

线性变换

大概率没啥用的方法,不过思想还是挺重要的.

(好吧我特意写这么一栏只是因为我线代学魔怔了)

简单来说就是把一般的图形变成特殊的图形,然后乱做.

线性变换的问题在于角的变化有点随意.不过边长以及斜率的变化都可以控制.

不过感觉只有椭圆是迫真有用的东西

旋转矩阵

向量$\vec{ b } = ( x , y )$逆时针旋转$\theta$后得到的答案是$A \vec{ b }$,其中

\cos\theta,-\sin\theta\\

\sin\theta,\cos\theta

\end{bmatrix}

你要不喜欢矩阵表示也不是不行,那向量$( x , y )$旋转$\theta$得到$( x ‘ , y ‘ )$,其中

y’=xsin\theta+ycos\theta

椭圆转化成圆

我们注意到圆的方程是$( x ‘ )^2 + ( y ‘ )^2 = 1$,而椭圆的方程形如$\frac{ x^2 }{ a^2 } + \frac{ y^2 }{ b^2 } = 1$.

我们注意到上面的式子等价于:$( \frac{ x }{ a } )^2 + ( \frac{ y }{ b } )^2 = 1$.我们将原坐标系中的所有坐标$( x , y )$全部变成$( \frac{ x }{ a } , \frac{ y }{ b } )$之后,就得到了一个新的坐标系.在新的坐标系中,我们只需要对着圆做就行.

换成线性代数语言,令$\vec{ f } = ( x , y )$满足椭圆方程,令$\vec{ g } = ( x ‘ , y ‘ )$满足圆的方程,自然有:

双曲线转化为反比例函数

注意到反比例函数的方程是$x ‘ y ‘ = 1$,而双曲线的方程是$\frac{ x^2 }{ a^2 } - \frac{ y^2 }{ b^2 } = 1$.

这个要硬配可能有些抽象.我们拿矩阵导一导.

首先先转化为$x^2 - y^2 = 2$的形式,需要左乘矩阵$\begin{bmatrix}\frac{ \sqrt{ 2 } }{ a } , 0 \ 0 , \frac{ \sqrt{ 2 } }{ b }\end{bmatrix}$.

然后这个形式和我们所需要的反比例函数的形式只差一步旋转$\frac{ \pi }{ 4 }$了.旋转矩阵为

\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\\

\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}

\end{bmatrix}

把两个东西乘起来得到矩阵

\frac{1}{a},-\frac{1}{b}\\

\frac{1}{a},\frac{1}{b}

\end{bmatrix}

验证一下,我们有$x ‘ = \frac{ x }{ a } - \frac{ y }{ b } , y ‘ = \frac{ x }{ a } + \frac{ y }{ b }$.带入反比例函数的方程:

对着矩阵求逆一下得到:逆矩阵为

\frac{a}{2},\frac{a}{2}\\

-\frac{b}{2},\frac{b}{2}

\end{bmatrix}

验证一下,我们有$x = \frac{ a }{ 2 } ( x ‘ + y ‘ ) , y = \frac{ b }{ 2 } ({ y ‘ - x ‘ } )$,带入双曲线方程得到:

要觉得矩阵部分比较魔怔也可以直接看上面的普通描述.

抛物线转化为二次函数

这个比较简单,交换$x , y$即可,小问题.

极坐标

平面内取一点$O$为极点,引一条射线$Ox$叫做极轴,再选定单位长度和单位角度以及角度正方向,就建立了一个极坐标系.

对于平面上任意一点$M$,令$\rho = | OM |$,$\theta$为以$Ox$为始边,沿角度正方向(一般是逆时针方向)转到$OM$的夹角.那么我们称$( \rho , \theta )$为$M$的极坐标,其中$\rho$叫做极径,$\theta$叫做极角.

$\rho$有可能取负,我们通常认为$( - \rho , \theta ) = ( \rho , \theta + \pi )$.

通常情况下默认$0 \leq \theta < 2 \pi , \rho \geq 0$.如果遇到和直角坐标系结合的问题,通常默认原点为极点,$x$轴正半轴为极轴且二者单位长度相等.下文如无特殊说明均按此建立极坐标.

注意到若$M$在直角坐标系中坐标为$( x , y )$,在极坐标中坐标为$( \rho , \theta )$,若$M \ne O$自然有:

看到这里,聪明的你可能已经发现了不对劲:那这玩意怎么做坐标系变换呢?这玩意难道能乱乘矩阵嘛?这俩项单位都不一样欸.

别急,你注意到这个东西看上去不太能整什么抽象的坐标系,做的时候直接考虑转化为平面直角坐标系再做.

圆的极坐标方程

显然是$\rho^2 = r^2$.

另外,如果中心在$C ( \rho_0 , \theta_0 )$,半径为$r$的方程咋求呢?

我们考虑本质是坐标系变换,想都别想先转平面直角坐标系,自然有:

另外由于$\cos \theta = \cos ( - \theta )$,这个公式应该不难背.

直线的极坐标方程

过定点$( \rho_1 , \theta_1 )$,且倾斜角为$\alpha$:$\rho \sin ( \alpha - \theta ) = \rho_1 \sin ( \alpha - \theta_1 )$.

这个咋推的呢,先换回平面直角坐标系,假设过定点$( x_1 , y_1 )$,倾斜角为$\alpha$,我们自然有$( x - x_1 ) \sin \alpha = ( y - y_1 ) \cos \alpha$.

于是有:

其实本质还是极坐标轴变换,因为过极点的直线是显然的.

我们再来考虑一个:求过定点$( \rho_1 , \theta_1 )$和$( \rho_2 , \theta_2 )$的直线方程.

同理的:

太丑了吧,甚至不对称?

(网上的资料这一步可以继续往下化简,用一些三角函数知识).

这个故事教给我们:极坐标系下是很难表示一些直线的.

那表示曲线呢?

圆锥曲线的极坐标方程

优美的来了!

我们注意到圆锥曲线的一种定义是:到准线距离$d$和到定点距离$r$之比为常数的曲线.令$e = \frac{ r }{ d }$.

假定定点为原点,极轴垂直于准线,$h$为定点到准线的距离,又设曲线上一点为$M ( \rho , \theta )$,自然有:$r = \rho , d = h + \rho \cos \theta$.

于是有:

值得一提的是这玩意不能将圆理解为$e = 0$的圆锥曲线.

参数方程

在平面直角坐标系中,曲线上任意一点的坐标$x , y$都是某个变量$t$的函数$\begin{cases}x = f ( t ) \ y = g ( t )\end{cases}$.

圆的参数方程

$M ( r \cos \theta , r \sin \theta )$,其中$\theta$是$\angle OMx$.

直线的参数方程

$M ( x_0 + t \cos \theta , y_0 + t \sin \theta )$,其中$\theta$是倾斜角,$t$是参数,$M_0 ( x_0 , y_0 )$.

注意到$| M_0 M | = | t |$.事实上,设$\vec{ e } = ( \cos \theta , \sin \theta )$,也就是直线的单位方向向量,则$\overrightarrow{ M_0 M } = t \vec{ e }$.

椭圆的参数方程

$M ( a \cos \theta , b \sin \theta )$,其中$\theta$称为$M$的离心角.

值得注意的是,这里的$\theta$并非$\angle MOx$,而是将椭圆线性变换回圆后对应点的对应圆心角.

Example1

在椭圆$\frac{ x^2 }{ 9 } + \frac{ y^2 }{ 4 } = 1$上求一点$M$,使$M$到直线$x + 2 y - 10 = 0$的距离最小.

直接令$M = ( 3 \cos \theta , 2 \sin \theta )$,则$d = \frac{ | 3 \cos \theta + 4 \sin \theta - 10 | }{ \sqrt{ 5 } } = | \sqrt{ 5 } \sin ( \theta + \varphi ) - 2 \sqrt{ 5 } |$,其中$\varphi = \arcsin \frac{ 3 }{ 5 }$.

于是$d_{ \min } = \sqrt{ 5 }$,此时$\sin ( \theta + \varphi ) = 1 = \sin{ \frac{ \pi }{ 2 } }$,那么就有$\theta = \frac{ \pi }{ 2 } - \varphi$,$\sin \theta = \cos \varphi = \frac{ 4 }{ 5 } , \cos \theta = \sin \varphi = \frac{ 3 }{ 5 }$.

则$M = ( \frac{ 9 }{ 5 } , \frac{ 8 }{ 5 } )$.

Example2

已知椭圆$\frac{ x^2 }{ 100 } + \frac{ y^2 }{ 64 } = 1$,有一内接矩阵$ABCD$($AB / / x , BC / / y$),求矩阵最大面积.

直接令$A = ( 10 \cos \theta , 8 \sin \theta )$,则$S = 20 \cos \theta \times 16 \sin \theta = 160 \sin ( 2 \theta )$,$S_{ \max } = 160$.

双曲线的参数方程

$M ( \frac{ a }{ \cos \theta } , b \tan \theta ) = M ( a \sec \theta , b \tan \theta )$,其中$\theta$称为$M$的离心角,通常规定$\theta \in [ 0 , 2 \pi ] \land \theta \ne \frac{ \pi }{ 2 } \land \theta \ne \frac{ 3 \pi }{ 2 }$.

其实本质也就是三角恒等式$\sec^2 \theta = 1 + \tan^2 \theta$.

Example1

圆$O : x^2 + ( y - 2 )^2 = 1$上有一点$P$,双曲线$x^2 - y^2 = 1$上有一点$Q$,求$| PQ |_{ \min }$.

设$Q ( \sec \theta , \tan \theta )$,则:

$| OQ |_{ \min } = \sqrt{ 3 } , | PQ |_{ \min } = \sqrt{ 3 } - 1$.

Example2

求证:等轴双曲线平行于实轴的弦在两顶点所张的角均为直角.

设$P ( a \sec \theta , a \tan \theta ) , Q ( - a \sec \theta , a \tan \theta )$,则$k_P = \frac{ a \tan \theta }{ a \sec \theta - a } , k_Q = \frac{ a \tan \theta }{ - a \sec \theta - a }$.注意到$k_P \cdot k_Q = - 1$.

Example3

已知双曲线$\frac{ x^2 }{ a^2 } - \frac{ y^2 }{ b^2 } = 1$,$A , B$是双曲线同支上相异两点,线段$AB$的垂直平分线与$x$轴相交于点$P ( x_0 , 0 )$,求证:$| x_0 | > \frac{ c^2 }{ a } = \frac{ a^2 + b^2 }{ a }$.

设$A ( a \sec \alpha , b \tan \alpha ) , B ( a \sec \beta , b \tan \beta )$,则中点$M ( \frac{ a }{ 2 } ( \sec \alpha + \sec \beta ) , \frac{ b }{ 2 } ( \tan \alpha + \tan \beta ) )$.

于是中垂线方程为$y - \frac{ b }{ 2 } ( \tan \alpha + \tan \beta ) ) = - \frac{ a ( \sec \alpha - \sec \beta ) }{ b ( \tan \alpha - \tan \beta ) } [ x - \frac{ a }{ 2 } ( \sec \alpha + \sec \beta ) ]$.

代入$P ( x_0 , 0 )$,求得$x_0 = \frac{ c^2 }{ 2 a } ( \sec \alpha + \sec \beta )$.

也就是要比较$| \sec \alpha + \sec \beta |$和$2$的大小关系,注意到$A , B$同支,所以$| \sec \alpha + \sec \beta | > 2$.

抛物线的参数方程

$M ( \frac{ 2 p }{ \tan^2 \theta } , \frac{ 2 p }{ \tan \theta } )$,其中$\theta$称为$M$的离心角,意义是该点和原点所确定直线的斜率,注意这个参数方程不能表示抛物线顶点.

事实上,我们可以有一个别的参数方程表达:$M ( 2 pk^2 , 2 pk )$,这个参数方程可以表示顶点.

Example1

若抛物线$\begin{cases}x = 2 pt^2 \ y = 2 pt\end{cases}$上有不同两点$M_1 , M_2$,所对应的参数分别是$t_1 , t_2$,求直线$M_1 M_2$所在直线的斜率.

$k_{ M_1 M_2 } = \frac{ 2 pt_1 - 2 pt_2 }{ 2 pt_1^2 - 2 pt_2^2 } = \frac{ 1 }{ t_1 + t_2 }$.

Example2

$A , B$是抛物线$y^2 = 2 px$上异于顶点的两动点,且$OA \bot OB$,$AB$上有一点$M$满足$OM \bot AB$,求$M$的轨迹方程.

设$M ( x , y ) , A ( 2 pt_1^2 , 2 pt_1 ) , B ( 2 pt_2^2 , 2 pt_2 )$,注意到:

因为$\overrightarrow{ OA } \bot \overrightarrow{ OB }$,所以$( 2 pt_1 t_2 )^2 + ( 2 p )^2 t_1 t_2 = 0$,$t_1 t_2 = - 1$.

因为$\overrightarrow{ AB } \bot \overrightarrow{ OM }$,又有$k_{ AB } = \frac{ 1 }{ t_1 + t_2 }$,所以$k_{ OM } = - ( t_1 + t_2 )$,$\frac{ y }{ x } = - ( t_1 + t_2 )$.

接下来咋做捏?注意到我们好像忘记了$ABM$三点共线的性质,拿向量做这个东西.

$\overrightarrow{ AM } = ( x - 2 pt_1^2 , y - 2 pt_1 ) , \overrightarrow{ MB } = ( 2 pt_2^2 - x , 2 pt_2 - y )$.

那么有$( x - 2 pt_1^2 ) ( 2 pt_2 - y ) = ( 2 pt_2^2 - x ) ( y - 2 pt_1 )$.

化简得到$x^2 + y^2 - 2 px = 0 ( x \ne 0 )$.

等一下,这咋想到的啊.

首先注意到我们有两个点$A , B$,自然要设出它们的参数方程.然后呢?然后我们发现最后$M$一定和$t_1 , t_2$有关.但是我们要求的是$M$的方程,其中不能带有$t_1 , t_2$,因此考虑把$M$的坐标设出来,再用这个坐标表示$t_1 , t_2$,表示不出来表示$t_1 t_2 , t_1 + t_2$也可以,然后消掉即可.

当然这题还有一个做法,注意到$M$一定在以$| OA |$为直径的圆上,$B$同理,这两个圆的方程分别为:

也就是说,$t_1 , t_2$是同一个方程的两个根,根据韦达定理自然有$t_1 t_2 = \frac{ - ( x^2 + y^2 ) }{ 2 px } = - 1$,于是直接有$x^2 + y^2 - 2 px = 0$.

还没完,注意到$O$一定是一个根,要去掉,所以答案就是$x^2 + y^2 - 2 px = 0 ( x \ne 0 )$.

Example3

已知$A , B , C$是抛物线$y^2 = 2 px ( p > 0 )$上的三个点,且$BC$与$x$轴垂直,直线$AB$和$AC$分别与抛物线的轴交于$D , E$两点,求证:抛物线的顶点平分$DE$.

设$A ( 2 pt_1^2 , 2 pt_1 ) , B ( 2 pt_2^2 , 2 pt_2 ) , C ( 2 pt_2^2 , - 2 pt_2 )$,注意到$AB : y - 2 pt_1 = \frac{ 1 }{ t_1 + t_2 } ( x - 2 pt_1^2 )$,$AC : t - 2 pt_1 = \frac{ 1 }{ t_1 - t_2 } ( x - 2 pt_1^2 )$.

可求得$D ( - 2 pt_1 t_2 , 0 ) , E ( 2 pt_1 t_2 , 0 )$,于是得证.

蒙日圆

参考:https://zhuanlan.zhihu.com/p/591258689

定义

过圆锥曲线外一点作两条互相垂直的切线,那么这一点的轨迹是一个圆,这个圆被称为蒙日圆,又叫外准圆.

方程

椭圆的蒙日圆方程

设椭圆为$\frac{ x^2 }{ a^2 } + \frac{ y^2 }{ b^2 } = 1$,其蒙日圆方程为$x^2 + y^2 = a^2 + b^2$.

证明:直接设椭圆上一点就可以导出.

双曲线的蒙日圆方程

设双曲线为$\frac{ x^2 }{ a^2 } - \frac{ y^2 }{ b^2 } = 1$,其蒙日圆方程为$x^2 + y^2 = a^2 - b^2$.

证明:其实注意到椭圆的证明中设$b$是复数也是成立的,自然得证双曲线.

我知道你在想啥,你在想有没有可能一个点向双曲线能做出超过两条切线.事实上根据渐近线的原理这是不可能滴.

抛物线的蒙日圆方程

设抛物线$y^2 = 2 px$,其蒙日圆方程为$x = - \frac{ p }{ 2 }$.

有一说一,直线是半径无穷大的圆.

• 抽象代数
  • 群
    • 定义
    • 基本概念和事实
      • Example1
      • Example2
    • 子群
      • Example1
      • Example2
      • Example3
      • Example4
      • Example5
      • Example6
      • Example7
      • Example8
    • 同态和同构
    • 群的实例
      • 全变换群,对称群与交错群
      • 一般线性群
      • 克莱因四元群
      • 循环群
    • 相反群
      • Example1
    • 陪集
    • 群作用
      • Cayley定理
      • Burnside引理
        • 共轭类计数
      • $p$-群
      • Sylow定理
        • Example1
    • 正规子群
      • 正规子群的判定定理
        • Example1
        • Example2
        • Example3
      • 正规子群与同态
      • 同态基本定理
      • 第一同构定理
      • 第二同构定理
      • 交换化
        • Example1
        • Example2(岩泽健吉(Iwasawa)判准)
        • Example3
    • 群的直和与直积
      • 直和
      • 半直积
        • Example1
        • Example2(二面体群)
  • 环
    • 子环
    • 理想
      • Example1
      • Example2
      • Example3(中国剩余定理)
    • 同态和同构
      • 同态基本定理
      • 第一同构定理
      • 第二同构定理
    • 整环
      • 特征
      • 整除性
      • 唯一分解整环(UFD)
      • 主理想整环(PID)
      • 欧几里得整环(ED)
  • 多项式环
    • 一元多项式环
    • 多元多项式环
    • 不可约多项式
      • 本原多项式
      • 一个判定不可约的算法
      • 不可约多项式上的扩域
    • 对称多项式
      • 牛顿公式
    • 结式
    • 判别式
  • 域
    • 域同态
    • 分式域
    • 有限域
    • 有限域上的多项式分解
    • Galois扩张
• 线性代数
  • 矩阵引入
    • 矩阵运算
    • 分块矩阵
  • 线性方程组
    • 系数矩阵和增广矩阵
    • 矩阵的初等行变换
    • 阶梯形矩阵
      • 简化阶梯形矩阵的唯一性
    • 解线性方程组
      • 存在与唯一性定理
    • 矩阵方程
    • 齐次线性方程组
  • 线性空间
    • 相关运算
      • 直积
      • 直和
      • 叉乘
    • 线性无关与线性相关
    • 子空间
      • 向量的线性组合
      • 线性映射
      • 基和维数
    • 可逆矩阵
      • 初等矩阵
      • 求解逆矩阵
        • Example1(LU分解)
    • 核与像与秩
      • Sylvester秩不等式
      • Frobenius秩不等式
    • 对偶空间
    • 直和分解与分块矩阵
    • 基的变换
      • 矩阵的共轭(相似)
      • 矩阵的相抵
    • 商空间
      • 同态基本定理
      • 第一同构定理
      • 第二同构定理
      • 旗
      • 不变子空间
  • 行列式
    • 置换(排列)
    • 交错形式
    • 定义
    • 余子式与代数余子式
    • 行列式定向
    • 克拉默(Cramer)法则
    • 一些特殊行列式
      • 置换矩阵
      • 上三角矩阵
      • 分块上三角矩阵
      • 范德蒙德(Vandermonde)行列式
      • 一类分块矩阵
    • 特征多项式
    • Cayley-Hamilton定理
    • 矩阵的迹
      • Example
    • Binet-Cauchy定理
    • 特征值与特征向量
    • 极小多项式
    • 同步对角化
    • 上三角化
    • 广义特征子空间
    • 特殊矩阵的特征值
      • Example
  • 双线性形式
    • 线性映射
    • 非退化形式
    • 伴随映射
    • 分类问题
    • 二次型
      • 实二次型
      • 惯性(Sylvester)定理
    • 辛空间
      • 达布定理
    • 回看对偶空间
      • 双重对偶
      • 核,余核与对偶映射
      • 像自对偶
  • 实内积空间
    • 勾股定理
    • 柯西不等式
    • 三角不等式
    • 距离相关
    • 正交向量族
    • Gram-Schmidt 正交化
      • Example1(RU分解)
      • Example2(Legendre多项式)
    • 正交算子
    • 正交补空间
    • 投影矩阵
    • 自伴算子
      • (实)Sylvester 判准
      • (实)正定矩阵的二次根
        • Example1
        • Example2
      • 极分解
      • 最小二乘法
    • 奇异值分解
    • Moore-Penrose 广义逆
    • 极大化极小原理(Courant-Fischer定理)
    • Perron-Frobenius定理
      • Collatz-Wielandt公式
      • Perron定理
    • 实正交变换的标准型
      • 欧拉角
      • 四元数
  • 复内积空间
    • 共轭空间
    • (复)半双线性形式
    • 伴随映射
    • Hermite形式
      • 正规线性映射
      • 二次型
    • 复内积空间
      • 酉变换
      • 正规算子的酉对角化(谱定理)
      • 相关实内积空间定理推广
      • 复矩阵范数实例
  • 模
    • 自由模
      • Example1(非自由模)
    • 线性映射和模结构
    • 主理想环上的有限生成模
      • 自由模与其子模
      • Smith标准型
      • 结构定理
      • 有限生成交换群的分类
    • 有理标准型
      • Example1
    • Jordan标准型
      • 加性Jordan-Chevalley分解
      • 乘性Jordan-Chevalley分解
  • 张量积
    • 张量积与直和
    • Kronecker积
    • 张量积与对偶空间
    • 张量代数
      • 另一种构造
      • 又看对偶空间
        • Example1
        • Example2
      • 简单应用
    • 域的变换

汉诺塔问题

三个柱子,$n$个面积互不相等的有孔圆盘一开始按照面积从上往下以此增大的顺序套在其中一个柱子上.

现在每次可以将某根柱子顶端的圆盘移动到另一根柱子顶端,要求这根柱子原本没有圆盘或者柱子顶端圆盘面积大于该圆盘.

求最小移动次数,使得所有圆盘移动到另一根柱子上.

不妨令$T_n$表示答案,显然$T_0 = 0 , T_1 = 1$.

而我们一定可以找到一种方案,使得前$n - 1$个圆盘先移动到其中一根柱子上,然后将最下面的圆盘移动到目标柱子,最后再把$n - 1$个圆盘移动到目标柱子.由于这是一个可行解而不一定是最优解,我们有:$T_n \leq 2 T_{ n - 1 } + 1$.

而如果我们要移动最大的圆盘,一定要保证前n-1个圆盘已经移走到一根柱子上.因此一定有:$2 T_{ n - 1 } + 1 \leq T_n$.于是有$T_n = 2 T_{ n - 1 } + 1$.

Example1(《具体数学》1.2)

汉诺塔问题,所有圆盘一开始均在最左边的塔A上,要将他们全都移动到最右边的塔C上,不允许在二塔之间直接移动,求最小操作次数.

Solution 1

考虑设$T_n$为n个圆盘时的最小操作次数.假设已知$T_{ n - 1 }$,我们考虑如何移动.

首先因为不能直接在AC之间移动,因此一定是先要把最大的圆盘移动到中间塔上,这一步要求先把所有圆盘移动到C上,然后需要再把这些圆盘移动回A上,因此,显然有:$T_{ n } = 3 T_{ n - 1 } + 2 , T_0 = 0$.

考虑如何求该式子的封闭形式,令$W_n = T_n + 1$,显然有$W_n = 3 W_{ n - 1 } , W_0 = 1$,显然$W_n = 3^n$,有$T_n = 3^n - 1$.

注意到$T_n$刚好是三根柱子上所有合法排列的数量,并且这个过程中不可能出现某两个时刻的情况是相同的,因此1.3也可以证明.

Example2(《具体数学》1.4)

汉诺塔问题,问是否存在一种符合规则的初始摆放方式,使得将其全部移动到其中一根柱子所用次数小于等于$2^n - 1$.

Solution 2

不存在.

证明方式类似原初问题的证明,考虑最大的那个圆盘是否到达终点.如果到达则可以去掉它,用数学归纳证明不存在;如果还未到达,同样用数学归纳得到不等式.

Example3(《具体数学》1.10)

汉诺塔问题,但是移动圆盘时只能从A移动到B,从B移动到C,从C移动到A.一开始所有圆盘都在A,求将它们全部移动到B的最小操作次数,以及将他们从B移动回A的最小操作次数.

Solution 3

令$Q_n$为将n个圆盘从A移动到B的最小操作次数,令$R_n$为将n个圆盘从B移动回A的最小操作次数.

先考虑边界情况,$Q_0 = 0 , R_0 = 0$.

我们考虑,由于柱子间在移动过程中是无区别的,因此$Q_n$的实质是将n个圆盘移动到它的下一个柱子的最小操作次数,$R_n$的实质是将n个圆盘移动到它的上一个柱子的最小操作次数.

在将最大的圆盘移动到下一根柱子前,一定要先把上面的圆盘全部移动到上一根柱子上,最后再移动回来.

显然有$Q_n = 2 R_{ n - 1 } + 1 , 1 \leq n$.

在将最大的圆盘移动到上一根柱子前,一定要先把他移动到下一根柱子上,这个步骤要求我们把其他的圆盘移动到上一根柱子上.在这之后,我们又要把所有圆盘放到上一根柱子上来让最大圆盘到目标柱子,最后再移动回来.

有$R_n = R_{ n - 1 } + 1 + Q_{ n - 1 } + 1 + R_{ n - 1 } = Q_n + Q_{ n - 1 } + 1 , 1 \leq n$.

Example4(《具体数学》1.11)

汉诺塔问题,但是每种大小的圆盘有两个,且其中一个可以摆放在另一个的上面.

a.如果相同圆盘无区别,求最小操作次数.

b.如果相同圆盘有区别,且最后需要还原原本二者的上下顺序,求最小操作次数.

Solution 4

a.仍然令$T_n$为n对圆盘的最小操作次数,显然$T_n = 2 T_{ n - 1 } + 2 , T_0 = 0$,可解得$T_n = 2^{ n + 1 } - 2$.

b.令$Q_n$为n对圆盘的最小操作次数,观察a问题,我们可以发现a问题转移之后,只有最下面的两个圆盘会交换顺序.而如果我们在b问题中只关注最下层两个圆盘的顺序,我们发现$Q_n = T_{ n - 1 } + 1 + T_{ n - 1 } + 1 + T_{ n - 1 } + 1 + T_{ n - 1 } = 4 T_{ n - 1 } + 3 = 2^{ n + 2 } - 5$.

我们进行了四次a操作,那么次下面两个圆盘自然就顺序与原本相同了,因此这里的$Q_n$就是答案.

Example5(《具体数学》1.12)

类似Problem11,但第$i$大的圆盘有$k_i$个.

Solution 5

无区别,只是$T_n = 2 T_{ n - 1 } + k_n , T_0 = 0$.

如果求封闭形式的话,显然有$T_n = \sum_{ i = 1 }^n 2^{ n - i } k_i$.

递归式的封闭形式

在上述问题中，我们已经有了以下式子：

$T_n = 2 T_{ n - 1 } + 1 , n > 0 , T_0 = 0$.

如果$n$很大，那么一步一步去计算是很复杂的，现在我们想知道一种更为快速的求出$T_n$的方法.

换句话说，我们想要把$T_n$表示为只与n有关的式子，我们称其为该递归式的封闭形式.

寻找循环节

Example(《具体数学》1.8)

解递归式:$Q_n = \begin{cases}\alpha & n = 0 \ \beta & n = 1 \ \frac{ ( 1 + Q_{ n - 1 } ) }{ Q_{ n - 2 } } & n > 1\end{cases}$,保证$\forall n , Q_n > 0$.

Solution

注意到$Q_2 = \frac{ \beta + 1 }{ \alpha } , Q_3 = \frac{ \beta + \alpha + 1 }{ \beta \alpha } , Q_4 = \frac{ 1 + \alpha }{ \beta } , Q_5 = \alpha , Q_6 = \beta$.

显然该递归式存在长度为$5$的循环节.

数学归纳法

观察T序列的前几项，可以发现似乎有$T_n = 2^n - 1$.

现在我们来证明它：

1.该公式对于$n = 0$成立，显然可验证.

2.若该公式对$n = k$时成立，那该公式必然对$n = k + 1$成立.

因为有$T_{ k + 1 } = 2 T_k + 1 = 2 \times 2^k + 2 - 1 = 2^{ k + 1 } - 1$.

以上过程被称为数学归纳法.

Example(《具体数学》1.9)

求证:$\prod_{ i = 1 }^n x_i \leq ( \frac{ \sum_{ i = 1 }^n x_i }{ n } )^n , \forall i \in N_+ , 1 \leq i \leq n , 0 \leq x_i$.

Solution

使用反向归纳法.

1.$n = 2$时,即基本不等式,显然成立.

2.若该式子对$n = k$时成立,则该式子对n=2k时也成立.

不妨令$A_1 = \sqrt[k]{ \prod_{ i = 1 }^k x_i } , B_1 = \sqrt[k]{ \prod_{ i = k + 1 }^{ 2 k } x_i } , A_2 = ( \frac{ \sum_{ i = 1 }^k x_i }{ k } ) , B_2 = ( \frac{ \sum_{ i = k + 1 }^{ 2 k } x_i }{ k } )$,显然有$A_1 \leq A_2 , B_1 \leq B_2$.

同时有$( \frac{ A_2 + B_2 }{ 2 } ) \geq \sqrt{ A_2 B_2 } \geq \sqrt{ A_1 B_1 }$.

3.若该式子对$n = k$时成立,则该式子对$n = k - 1$的时候也成立.

令$x_k = \frac{ \sum_{ i = 1 }^{ k - 1 } x_i }{ k - 1 }$,有$x_k \prod_{ i = 1 }^{ k - 1 } x_i \leq ( x_k )^k$.

则显然$n = k - 1$时也成立.

由1和2,我们知道了对于n是二的整数次幂的情况,该公式成立,由3,我们又可以知道该公式对于任意一个存在比他大的二的整数次幂的数成立,因此该公式成立.

换元

考虑令$U_n = T_n + 1$,显然有:$T_n + 1 = 2 T_{ n - 1 } + 2$.即$U_n = 2 U_{ n - 1 }$,显然$U_n = 2^n$,则$T_n = 2^n - 1$.

这个做法可以做掉所有形如$a_{ n + 1 } = pa_n + q$的递归式.我们有:

换元做掉这个式子.

转化和式

考虑递归式$a_n T_n = b_n T_{ n - 1 } + c_n$.如果我们能找到一个不为0的求和因子$s_n$并满足$s_n b_n = s_{ n - 1 } a_{ n - 1 }$.那么我们两面同时乘以$s_n$,显然有：$s_n a_n T_n = s_{ n - 1 } a_{ n - 1 } T_{ n - 1 } + c_n s_n$.

令$S_n = s_n a_n T_n$.显然有$S_n = s_0 a_0 T_0 + \sum_{ i = 1 }^n s_i c_i$,则$T_n = \frac{ S_n }{ s_n a_n }$.

而我们也会发现$s_n = \frac{ \prod_{ i = 1 }^{ n - 1 } a_i }{ \prod_{ i = 1 }^n b_i }$.

Example1(快速排序时间复杂度)

结论:排序$n$个数时,其期望复杂度满足:

不妨考虑两边同时乘以$n$,有 $nC_n = n^2 + n + 2 \sum_{ i = 0 }^{ n - 1 } C_i , n > 1$ .

显然也有$( n - 1 ) C_{ n - 1 } = ( n - 1 )^2 + n - 1 + 2 \sum_{ i = 0 }^{ n - 2 } C_i , n > 2$.

二式相消,有$nC_n - ( n - 1 ) C_{ n - 1 } = 2 n + 2 C_{ n - 1 } , n > 2$.

而同时有$C_2 = 3$.即:$nC_n = ( n + 1 ) C_{ n - 1 } + 2 n , n > 2$,可以使用转化和式的方法,两边乘以$\frac{ 1 }{ n ( n + 1 ) }$解决.

Example2

已知$a_1 = 1$,$a_n = \sqrt{ S_n } + \sqrt{ S_{ n - 1 } }$,求$a_n$.

注意到$a_n = S_n - S_{ n - 1 }$,则有$\sqrt{ S_n } - \sqrt{ S_{ n - 1 } } = 1$,于是$\sqrt{ S_n } = n$,$S_n = n^2$,$a_n = 2 n - 1$.

成套方法

如果我们有

\alpha & n=1\\

2f(\frac n 2)+\beta & n=2k,k\in \mathbb{N_+}\\

2f(\frac {n-1}2)+\gamma &n=2k+1,k\in \mathbb{N_+}

\end{cases}

其中$n = 2^m + l$且$2^m \leq n < 2^{ m + 1 }$.

该如何求出$f ( n )$的封闭形式呢?

由于所有的未知数都是以加法运算连接,显然有$f ( n ) = A ( n ) \alpha + B ( n ) \beta + C ( n ) \gamma$,而有$A 、 B 、 C$互不影响且$\alpha \beta \gamma$与$ABC$无关.

那无论$\beta$和$\gamma$的取值如何,$A ( n )$都不会受到影响,我们考虑$\beta = \gamma = 0$的特殊情况,此时显然有$A ( n ) = 2^m$.

接下来,我们考虑取$\alpha \beta \gamma$的特殊值,去得到ABC之间的关系.

例如，当$f ( n ) = 1$时，由递推式可知$\alpha = 1 , \beta = \gamma = - 1$,那么有$A ( n ) - B ( n ) - C ( n ) = f ( n ) = 1$.

同理，$f ( n ) = n$时，可知$\alpha = 1 , \beta = 0 , \gamma = 1$,此时有$A ( n ) + C ( n ) = f ( n ) = n$.

显然可以通过解方程求得$B ( n )$和$C ( n )$.

这个方法显然是通用方法,式子仅仅是例子,事实上,只要我们能证明$ABC$互不影响且$\alpha \beta \gamma$与$ABC$无关,我们就可以使用这个方法.

这个东西的原理是什么呢?显然是因为其中存在一个线性无关性对吧.

线性递推

一个常系数的$k$阶线性递推关系形如:

当$P = 0$时,称作齐次线性递推.

特征方程

我们称方程$r^k = \sum_{ i = 1 }^k c_i r^{ k - i }$是该递推关系的特征方程,方程的解叫做该递推关系的特征根.

二阶线性齐次递推

若其特征方程有两个不同的根$r_1$和$r_2$,那么存在两个常数$\alpha_1$和$\alpha_2$,满足$a_n = \alpha_1 r_1^n + \alpha_2 r_2^n$.

若其特征方程有两个相同的根$r$,那么存在两个常数$\alpha_1$和$\alpha_2$,满足$a_n = \alpha_1 r^n + \alpha_2 nr^n$.

先考虑前者的证明,首先考虑对于$n = 0$或者$n = 1$的情况,我们考虑求出一组$\alpha_1$和$\alpha_2$来满足:

若$r_1 \ne r_2$,可以解得:

接下来考虑数学归纳:

接下来考虑后者,首先我们有$\Delta = c_1^2 + 4 c_2 = 0$,考虑初始条件:

接下来我们考虑数学归纳:

我们接下来只需证明$c_1 r + 2 c_2 = 0$即可.根据方程,不难发现$r = \cfrac{ c_1 }{ 2 }$,根据$\Delta = 0$,自然得证.

更一般的情况

直接在复数域上定义$f_k ( x ) = \{ n^k x^n \}_{ n = 0 }^\infty$,此时我们规定$0^0 = 1$.特别地,当$x = 0$的时候,定义$f_k ( x )$的第$k$项是$1$,其余项是$0$.在此基础上定义线性映射$T : ( a_n )_{ n = 0 }^\infty \mapsto ( a_{ n + 1 } )_{ n = 0 }^\infty$,立刻见到:$( T - x )^{ k + 1 } f_k ( x ) = 0 , ( T - x )^k f_k ( x ) \ne 0$.原因只需简单数学归纳.而此还可以引出$f_0 ( x ) , f_1 ( x ) , \cdots$线性无关.

在此基础上观察线性递推$a_{ n + d } = c_{ d - 1 } a_{ n + d - 1 } + \cdots + c_0 a_n$,不妨取$G ( x ) = x^d - c_{ d - 1 } x^{ d - 1 } - \cdots - c_0$,立刻应当见到如果$a$是$G$的根并且重数为$e ( a )$,那么$f_{ 0 } ( x ) , \cdots , f_{ e ( a ) - 1 } ( a )$都在$\ker f ( T )$中.这恰好是该线性递推空间的维数个.我们需要说明它们线性无关,不妨反证,假设出现了形如$\sum_j w_i f_i ( y ) = \sum_j w_j f_j ( x )$的情况,此时对右边直接操作若干次$( T - x )$就可以把右边全部消成$0$,在对着左边消几次就可以使得左边只留下最高次项,这个时候发现最高次项是消不掉的,原因是将每一个位置看作关于$n$的多项式右边的$( T - x )$是不会改变左边这边的每一个位置多项式的$\deg$,这当然意味着不可能消干净.

再再进一步

我们都知道矩阵加速:也就是$\vec{ x }_{ k + 1 } = A \vec{ x }$,$\vec{ x }_{ n } = A^n \vec{ x }_0$.而我们又知道CH定理:$p ( A ) = 0$,我们用多项式取膜,有$A^n = p ( A ) F ( A ) + G ( A ) = G ( A )$,这就是解.

约瑟夫问题

考虑n个人围成一圈,从第一个人开始,每隔一个人就杀掉一个人.如10个人围成一圈时,杀人的顺序是$2 , 4 , 6 , 8 , 10 , 3 , 7 , 1 , 9$.问最后幸存下来的人编号.

首先一定有J(1)=1.考虑第一遍杀掉n号或者n-1号之后,对整个圆圈进行重新编号.

那么当人数是偶数时,我们有$J ( 2 n ) = 2 J ( n ) - 1$;当人数是奇数时,我们杀掉一号,然后有$J ( 2 n + 1 ) = 2 J ( n ) + 1$.

整理得到:

仍然可以使用数学归纳，如果令$n = 2^m + l 且 2^m \leq n < 2^{ m + 1 }$.

有$J ( n ) = 2 l + 1$.

要是注意力没有那么集中怎么办呢?考虑到这个东西显然和取膜有着不可分割的关系,我们不妨从$0$开始编号:

这下相信$J ( n )$是多少就很显然了,将$n$写成二进制的形式,这个就相当于把首位$1$抹去然后在末尾加个$0$.

Example(《具体数学》1.15)

求约瑟夫问题中最后一名被杀死的人的编号.

Solution

显然有:

从$0$开始编号,自然有:

显然$J ( n )$也可以用二进制表达其形式.

和式

和式的基本运算

分配律:

一般分配律:

结合律:

交换律:

交换求和顺序:

和式的封闭形式

交换顺序法

Example1(等差数列求和)

我们有:

Example2(切比雪夫单调不等式)

令$S = \sum_{ 1 \leq i < j \leq n } ( a_j - a_i ) ( b_j - b_i ) = \sum_{ 1 \leq j < i \leq n } ( a_j - a_i ) ( b_j - b_i )$.

考虑恒等式$[ 1 \leq j < i \leq n ] + [ 1 \leq i < j \leq n ] = [ 1 \leq j , i \leq n ] - [ 1 \leq i = j \leq n ]$.

那么我们有:

显然有以下式子:

(\sum_{i=1}^na_i)(\sum_{j=1}^nb_j)\geq n\sum_{i=1}^na_ib_i，\forall i<j，a_i\leq a_j且b_i\geq b_j\\

上式被称为切比雪夫单调不等式.

值得一提的是,切比雪夫单调不等式其实是排序不等式的一个特化版本.

Example3(拉格朗日恒等式)

证明:

有:

扰动法

Example1(等比数列求和)

而$S_{ n - 1 } + ax^n = S_n = a + xS_{ n - 1 }$,有$S_n + ax^{ n + 1 } = a + xS_n , S_n = a \frac{ x^{ n + 1 } - 1 }{ x - 1 }$，其中$x \ne 1$.

Example2(平方和公式)

如果直接对该公式使用扰动法:

我们无法得到$S_n$的封闭形式,但我们发现我们得到了$\sum_{ i = 1 }^n i$的封闭形式.

那以此类推,我们设$W_n = \sum_{ i = 0 } i^3$.

Example3(《具体数学》2.20)

令$H_n = \sum_{ k = 1 }^n \frac{ 1 }{ k }$,求$\sum_{ i = 0 }^n H_i$.

Solution3

不妨考虑$\sum_{ i = 0 }^n iH_{ i }$的值.

Example4(《具体数学》2.21)

求$S_n = \sum_{ i = 0 }^n ( - 1 )^{ n - i } , T_n = \sum_{ i = 0 }^n ( - 1 )^{ n - i } i , U_n = \sum_{ i = 0 }^n ( - 1 )^{ n - i } i^2$.

Solution 4

转化为递归式

考虑和式$S_n = \sum_{ i = 0 }^n f ( i ) = S_{ n - 1 } + f ( n ) \\$，显然是递归式形式.

因此递归式所可以使用的方法同样可以在和式中使用.

Example1(《具体数学》2.13)

求$\sum_{ i = 0 }^n ( - 1 )^i i^2 \\$.

Solution1

令$S ( n ) = \sum_{ i = 0 }^n ( - 1 )^i i^2 = S ( n - 1 ) + ( - 1 )^n n^2$,考虑使用成套方法.

不妨令$S ( n ) = S ( n - 1 ) + ( - 1 )^n ( \alpha + \beta n + \gamma n^2 ) = \alpha A ( n ) + \beta B ( n ) + \gamma C ( n )$.

令$S ( n ) = ( - 1 )^n n , 可 以 解 得 \alpha = - 1 , \beta = 2 , \gamma = 0$,有$( - 1 )^n n = - A ( n ) + 2 B ( n )$.

令$S ( n ) = ( - 1 )^n n^2 , 可 以 解 得 \alpha = 1 , \beta = - 2 , \gamma = 2$,有$( - 1 )^n n^2 = A ( n ) - 2 B ( n ) + 2 C ( n )$.

显然可解得$2 C ( n ) = ( - 1 )^n n^2 + ( - 1 )^n n , C ( n ) = ( - 1 )^n \frac{ n ( n + 1 ) }{ 2 }$.

而原式中,$S ( n ) = C ( n ) = ( - 1 )^n \frac{ n ( n + 1 ) }{ 2 }$.

Example2(《具体数学》2.19)

有$2 T_n = nT_{ n - 1 } + 3 n ! , T_0 = 5$,求$T_n$.

Solution 2

令$s_n = \frac{ 2^{ n - 1 } }{ n ! }$,两边同时乘以$s_n$,有$\frac{ 2^n }{ n ! } T_n = \frac{ 2^{ n - 1 } }{ ( n - 1 ) ! } T_{ n - 1 } + 3 \times 2^{ n - 1 } \\$.

令$S_n = \frac{ 2^n }{ n ! } T_n$,有:

转化为积分形式

Example1(平方和公式)

考虑先求出一个近似解,然后再求误差.

考虑函数$f ( x ) = x^2$,显然$\int_0^n x^2 dx = \frac{ n^3 }{ 3 } \sim S_n \\$.

接下来,我们考虑求得二者之间的误差,设$E_n = S_n - \frac{ n^3 }{ 3 } \\$,对其使用扰动法:

这样就得到了递归式,可以求得封闭形式.

还有一种方法是:

这是一个简单的和式.而$S_n = E_n + \frac{ n^3 }{ 3 } \\$,显然也可以求得.

Example2(某浙江高考题)

已知$a_1 = 1 , a_{ n + 1 } - a_n = - \frac{ 1 }{ 3 } a_n^2$,估计$a_n$的值.

考虑构造一个函数$f ( n )$使得$f ( n ) \approx a_n$,那我们就可以将$a_{ n + 1 } - a_n \approx f_n$.

这个第一眼看上去就很有道理,而事实上也确实很有道理,原因是根据拉格朗日中值定理,$\exists x_0 \in [ n , n + 1 ] , f ‘ ( x_0 ) = f ( n + 1 ) - f ( n )$,而对于增长率变化不大的函数,直接认为$f ‘ ( x_0 ) = f ‘ ( n )$是有理可循的!

然后,原式子就变成了一个微分方程了,带入$f ( 1 ) = 1$解得$f ( n ) = \frac{ 3 }{ n + 2 }$.这个精度已经足够选出来原本的放缩题的答案了.

令$a_n = \frac{ 3 }{ n + 2 } - b_n$,带入化简,得到$\{ b_n \}$的递推式:

算到这里,我们可以很轻易使用数学归纳法算出$b_n \leq \frac{ 1 }{ 4 n }$,这个精度已经挺不错的了,但是也让人觉得很不满意,因为这个误差项怎么和估计项是同阶的啊.

然后我开始估计了一下这个$b_n$的阶,因为我其实没学过什么高超的高数技巧,所以我使用了OI的一些技巧来估计,不妨假设$b_n^2 < < b_n$:

那么这个$b_n$是$O ( \frac{ \ln n }{ n^2 } )$级别的.

如何理解这个级别?考虑别乱动$b_n$的系数,我们有:

这警戒我们以后乱估计的时候千万别把$O ( n^{ \epsilon } )$和$O ( 1 )$搞混了,警钟长鸣.

这个时候大概估计一下会发现$b_n \leq \frac{ 3 \ln n }{ n ( n + 1 ) }$.

展开和收缩

Example1(平方和公式)

我们有:

整理得到$S_n$.

Example2(《具体数学》2.14)

求$\sum_{ i = 1 }^n i 2^i \\$.

Solution 2

Example3(《具体数学》2.15)

求$\sum_{ i = 1 }^n i^3 \\$.

Solution 3

ExampleEX

求$\sum_{ i = 1 }^n iq^i ( q \ne 1 )$.

SolutionEX

ExampleEX2

求$\sum_{ i = 1 }^n ( ai + b ) q^{ i - 1 } ( q \ne 1 )$.

SolutionEX2

令$A = \frac{ a }{ q - 1 } , B = \frac{ b - A }{ q - 1 }$,答案为$( An + B ) q^n - B$.

有限微积分

移位算子

定义移位算子$E$，使得$Ef ( x ) = f ( x + 1 )$.

差分算子

定义差分算子$\Delta f ( x ) = f ( x + 1 ) - f ( x )$，类似于无限微积分中的D算子.

另外,不难发现有$\Delta = E - 1$.

逆差分算子

定义逆差分算子$\Sigma$,可以得到有限微积分的基本定理:

这里的$\Sigma$又被称为不定和式,是差分等于$g$的一个函数类.

值得一提的是,这里的$C$与无限微积分中的$C$有一定区别,这里的$C$可以是满足$p ( x ) = p ( x + 1 )$的任意一个函数而不非得是常数函数.

定和式

如果$g ( x ) = \Delta f ( x )$,那么有$\sum \nolimits_{ a }^b g ( x ) \delta x = f ( x ) |^{ b }_a = f ( b ) - f ( a ) \\$.

值得一提的是,如果$a \leq b$,显然有$\sum \nolimits_{ a }^b g ( x ) \delta x = \sum_{ x = a }^{ b - 1 } g ( x ) \\$.

但如果$a > b$,那么$\sum \nolimits_{ a }^b g ( x ) \delta x = - \sum \nolimits_b^a g ( x ) \delta x \\$.

事实上,我们一定有:$\sum \nolimits_a^b g ( x ) \delta x + \sum \nolimits_b^c g ( x ) \delta x = \sum \nolimits_a^c g ( x ) \delta x \\$.

一些基本的公式

类比无限微积分中的$D ( x^m ) = mx^{ m - 1 }$，有:

类比无限微积分中的$D ( \ln x ) = \frac{ 1 }{ x }$,有:

类比无限微积分中的$D ( e^x ) = e^x$,有:

根据组合数公式,有:

Example(平方和公式)

我们有:$k^2 = k^{ \underline{ 2 } } + k^{ \underline{ 1 } } \\$.

那么:

整理即可得到封闭形式.

值得一提的是:

与前面的方法不同，这里没有使用三次的二项式公式，而是使用了二次的斯特林公式负责将一般幂转化为下降幂.

高阶差分

考虑一阶差分是$\Delta f ( x ) = f ( x + 1 ) - f ( x )$,那么二阶差分就是$\Delta^2 f ( x ) = f ( x + 2 ) - 2 f ( x + 1 ) + f ( x )$.

类似地,我们可以通过归纳法证明$\Delta^n f ( x ) = \sum_{ k } \binom{ n }{ k } ( - 1 )^{ n - k } f ( x + k ) \\$.

事实上有一种更简单的证明方法,由于$\Delta = E - 1$,于是$\Delta^n = ( E - 1 )^n = \sum_{ k } \binom{ n }{ k } ( - 1 )^{ n - k } E^k \\$,由于$E^k f ( x ) = f ( x + k )$,即可证明原式.

另外,不难发现如果$f ( x )$是一个关于$x$的$d$次多项式,那么$\Delta f ( x )$是一个$d - 1$次多项式.同理,$\Delta^d f ( x )$会是一个常数而$\Delta^{ d + 1 } f ( x )$会是$0$,这个发现引出了牛顿级数.

Example([yLOI2020]灼)

首先不难发现对于一个位置,有意义的只有相邻的两个虫洞,设这两个位置分别为$x_1 , x_2$.

不难写出期望转移式子:$f_i = \cfrac{ 1 }{ 2 } ( f_{ i - 1 } + f_{ i + 1 } ) + 1$,并且$f_{ x_1 } = f_{ x_2 } = 0$.

接下来如何做呢?

我们先对第一个式子进行变形:

$f$的二阶差分是常数,也就是说$f$是二次多项式,不难求得其二次项系数为$- 1$又知道两个零点,显然可以得到$f$的表达式.

牛顿级数

令$f ( x ) = \sum_{ 0 \leq i \leq d } a_i x^i \\$.而由于有斯特林数可以进行幂和下降幂的转换,则我们可以将其改写为$f ( x ) = \sum_{ 0 \leq i \leq d } b_i x^{ \underline{ i } } \\$.

我们设$c_i = i ! b_i$,于是有:$f ( x ) = \sum_{ 0 \leq i \leq d } c_i \binom{ x }{ i } \\$.

也就是说,任何多项式都可以表示为二项式系数的倍数之和,我们称这样的展开式为$f ( x )$的牛顿级数.

于是不难发现有:$\Delta^n f ( x ) = \sum_{ 0 \leq i \leq d } c_i \binom{ x }{ i - n } \\$.如果我们令$x = 0$,则有:$\Delta^n f ( 0 ) = \begin{cases}c_n & n \leq d \ 0 & n > d\end{cases}$.那么牛顿级数的另一种表示即:$f ( x ) = \sum_{ 0 \leq i \leq d } \Delta^i f ( 0 ) \binom{ x }{ d } \\$.

另外,如果我们展开一下$c_n = \Delta^n f ( 0 )$,我们可以得到公式:

$\sum_{ k } \binom{ n }{ k } ( - 1 )^k ( \sum_{ 0 \leq i \leq n } c_i \binom{ k }{ i } ) = ( - 1 )^n c_n , n \in \mathbb{ N } \\$.

如果我们将多项式还原,由于$a_n = b_n$,有:

$\sum_{ k } \binom{ n }{ k } ( - 1 )^k ( \sum_{ 0 \leq i \leq n } a_i k^i ) = ( - 1 )^n n ! a_n , n \in \mathbb{ N } \\$.

另外,如果$x \in \mathbb{ N }$,那么我们有:$f ( x ) = \sum_{ 0 \leq k } \Delta^k f ( 0 ) \binom{ x }{ 0 }$,根据多项式推理法,这个公式对$\forall x \in \mathbb{ Z }$都成立.

于是我们可以类似泰勒级数写出无限牛顿级数:

Example

求$\sum_{ k } \binom{ n }{ k } \binom{ r - sk }{ n } ( - 1 )^k , n \in \mathbb{ N } \\$.

如果我们令$f ( k ) = \binom{ r - sk }{ n } = \sum_{ 0 \leq i \leq n } a_i k^i \\$,不难发现$a_n = \cfrac{ ( - 1 )^n s^n }{ n ! }$,于是显然原式$= s^n$.

分部求和法则(Abel求和法)

两边取不定和，即可得到分部求和法则:

$\sum u \Delta v = uv - \sum Ev \Delta u \\$.

分部求和用一般和式表达如下,下式又被称为Abel求和法:

对于$l = 0 , r = n , a_0 = b_0 = 0$的特殊情况,应当有:

取两组数列$\alpha , \beta$,并令$\sum_{ i = 1 }^n \beta_i = B_i$,立刻有:

Example1

求$\sum_{ k = 0 }^n k 2^k \\$.

根据分部求和法则，我们有:

$\sum x 2^x \delta x = x 2^x - \sum 2^{ x + 1 } \delta x = x 2^x - 2^{ x + 1 } + C \\$.

改为定和式形式，显然有:

$\sum_{ k = 0 }^n k 2^k = \sum \nolimits_0^{ n + 1 } x 2^x \delta x = ( n + 1 ) 2^{ n + 1 } - 2^{ n + 2 } + 2 = ( n - 1 ) 2^{ n + 1 } + 2 \\$.

Example2

求$\sum_{ k = 0 }^{ n - 1 } kH_k \\$.

令$u ( x ) = H_x , v ( x ) = \frac{ 1 }{ 2 } x^{ \underline{ 2 } } \\$.

带入分部求和法则，显然有:

$\sum xH_x \delta x = \frac{ x^\underline{ 2 } }{ 2 } H_x - \frac{ x^\underline{ 2 } }{ 4 } + C \\$.

带入即可求出原式$= \frac{ n^\underline{ 2 } }{ 2 } ( H_n - \frac{ 1 }{ 2 } ) \\$.

Example3(《具体数学》2.23)

求$\sum_{ i = 1 }^n \frac{ 2 i + 1 }{ i ( i + 1 ) } \\$.

Solution 3

令$u = ( 2 n + 1 ) , v = - \frac{ 1 }{ i }$,则$\Delta u = 2 , \Delta v = \frac{ 1 }{ i ( i + 1 ) }$.

根据分部求和法则,有:

Problem 4(《具体数学》2.24)

求$\sum_{ i = 0 }^{ n - 1 } \frac{ H_k }{ ( k + 1 ) ( k + 2 ) } \\$.

Solution 4

令$u = H_n , v = - \frac{ 1 }{ n + 1 } , \Delta u = \frac{ 1 }{ n + 1 } , \Delta v = \frac{ 1 }{ ( n + 1 ) ( n + 2 ) } \\$.

根据分部求和法则,有:

贪心

排除不优策略

Example1(CF1612E)

先把期望写开,我们发现如果选择了$t$个消息$a_1 , a_2 , . . . , a_t$,那么答案就是$\sum [ \exists j , m_i = a_j ] \cfrac{ \min ( t , k_i ) }{ t }$.显然如果$t$固定,那么每个$a_j$的贡献是独立的.于是只需要枚举$t$然后取贡献最大的.

但是,如果$t > \max \{ k_i \}$,这个时候$t - 1$的答案是$t - 1$个数之和除以$t - 1$,$t$的答案是这$t - 1$个数之和加上另一个更小的数除以$t$,而前者肯定比后者大,于是不用再进一步枚举.

于是复杂度$O ( n \max \{ k_i \} )$.

Example2(CF1592F1)

首先,二操作和三操作一定没有用,因为它们都可以用两次一操作代替.

再注意到四操作是可能有用的,因为我们拿一操作模拟四操作需要四金币的代价,而用一个四操作只需要三个金币.但是,由于拿一操作模拟四操作的时候,需要全局做一遍一操作,所以如果有两个四操作,模拟的时候两遍全局操作就可以抵消.因此,我们模拟两次四操作只需要六个金币的代价.换句话说,我们如果要用到四操作,只会使用一次或零次.

首先区间异或可以差分($b_{ i , j } = a_{ i , j } \oplus a_{ i + 1 , j } \oplus a_{ i , j + 1 } \oplus a_{ i + 1 , j + 1 }$)后转化为四个点的异或操作,而由于一操作操作了左上角的矩阵,所以它实际上是对三个在原矩阵外的点和一个在矩阵内的点操作.我们注意到如果矩阵内已经全都是$0$了,那么矩阵外不可能是$1$,也就是原矩阵也全都是$0$了.

枚举一下最后的操作是啥即可,另外注意到这一步操作必须把四个点全部变成$0$才有用,不然还需要拿一操作去补,就不如直接用一操作.

Example3(CF1592F2)

首先注意到,如果我们对$( x , y )$使用操作四,那我们不可能再对一个$( x , i )$使用操作四,不然我们就可以用四次操作一代替这两次操作四.

再通过上面的分析,注意到只有$b_{ x , y } , b_{ n , y } , b_{ x , m }$都是$1$的时候才会使用四操作,不然,如果我们使用四操作,必然会再需要一个一操作来补,这样就是至少三个金币的代价.而由于这四个点中最多只有三个$1$,所以一定不如直接用一操作来的划算.不然,如果三个都是$1$,那么用了就一定不亏,因为无论如何也需要三次一操作,而就算我们用完后$b_{ n , m }$变成$1$了,再不行也可以使用一次$1$操作来补全.

因此我们现在想要选尽可能多的三操作,满足两两操作不在同一行或同一列,这显然是一个二分图匹配问题.换句话说,如果$b_{ x , y } , b_{ n , y } , b_{ x , m }$都是$1$,我们就把$x$到$y$连一条边,然后做二分图匹配,显然是最优的.

Example4(CF1666E)

先想一下别的东西怎么求.

如果我们要求最大值最小或者最小值最大怎么办?我们可以二分后贪心,而显然它们的差就是一个答案的下界,问题在于这个下界是否可以取到.

我们冷静一下,发现在可能的方案中,第$i$条线段的右端点的位置一定是一段连续的区间.

设$f_i$表示第$i$个分界点可能的最小值,$g_i$表示第$i$个分界点可能的最大值.假设我们目前二分的最大值要小于等于$mx$,最小值要大于等于$mn$,那么我们有转移:

注意到$f$与$g$的转移是无关的,而显然对于第$i$个分界点,它可以取$[ f_i , g_i ]$中一个数,一定存在一个取法使得答案能取到下界.

为啥呢?只需让$ans_{ i }$表示第$i$条分界线是啥,那么我们$ans_i$是可以取$[ ans_{ i + 1 } - mx , ans_{ i + 1 } - mn ]$中的任何一个数字的,我们将其和上面求出的$[ f_i , g_i ]$求一下交集.如果交集为空,说明要么$ans_{ i + 1 } - mn < f_i , f_{ i + 1 } < ans_{ i + 1 } < f_i + mn$,这是不可能的.另一种情况同理不可能,这就保证了一定可以取到答案.一定能使极差$\leq mx - mn$.

Example5(2022zrtg十连测day7 Palindrome)

首先注意到同种字符的相对顺序不可能改变.于是最后的回文串是哪个字符对应哪个字符就可以确定.

这样我们的问题转化为现在有若干个点对$( l , r )$,我们想给每一个点对赋值:$a_l = i , a_r = n - i + 1$(注意如果$n$是奇数,那么中心点应该是$a_{ mid } = \frac{ n + 1 }{ 2 }$),然后使整个序列逆序对数尽可能小.

接下来讨论一下两个点对$( l_1 , r_1 )$,$( l_2 , r_2 )$之间的三种可能的关系:不交,包含,相交且不包含.会发现若$l$小则让$a_l$尽可能小就是最优的.

Example6(23省选10连测 day9 C)

强强题.

首先发现这个$\pm 1$操作很奇怪.我们不妨这么考虑:设最后的答案序列为$b$,那么答案其实就是$\sum | b_i - a_i |$.这实际上是什么呢?实际上是数轴上$a_i$和$b_i$之间的距离.既然这样,那么我们同时反转$a$和$b$,这等价于翻转数轴,答案应该是不变的.这说明什么呢?如果我挑一个$a$,将它和$x$同时反转,那么答案不变.这么做后我们可以直接清空所有$a$的最高位,只剩下$x$可能有最高位.

那$x$的最高位一定会让若干$a$往上变成它.注意到最多只会有一个$a$会向上满足$x$的最高位.证明的话同样考虑取反,如果有两个$a$满足$a_i \oplus b_i$和$a_j \oplus b_j$这一位是$1$,我们仍然考虑数轴,有$| not ( b_i ) - a_i | \leq | a_i - b_i |$,这由$a_i \oplus b_i$最高位是$1$导出.因此两个都取反一定不劣.

再考虑,我们会让哪个$a$上去满足呢?自然的想法是取代价最小的那个,因为就算它不是,这里自然地有一个待悔贪心:其它的$a$可以再变成它.

于是就做完了.

Example7(异或粽子)

Example8()

带悔贪心

Example1

给定一个数组,给出若干次操作$[ l , r , k ]$表示可以将$a [ l \cdots r ]$减一进行至多$k$次,要求操作过程中数组时刻非负,求最大能做出的操作次数.

这题的做法是,我们每次遇到一个左端点,就将所有以它为左端点的区间全部操作,并把这些区间按照右端点为关键字扔进堆里.每次遇到一个地方的值变成了负的,就从堆中找右端点最大的区间杀掉.容易发现这样是正确的.

为啥能想到带悔贪心呢?主要是因为我们发现不同的区间会彼此影响,而且有一个限制性的长期条件.因此先不管这个条件,最后再通过调整堆将这个条件调整至合法.

Example2

给定一个序列,每次可以选择相邻的两个数,使其中一个$- 1$,另一个$- 2$,求使得整个序列都小于等于$0$的最小操作次数.

我们明确一下带悔贪心的基本条件:

1. 首先,贪心是需要保证局部最优性的,并且需要保证不考虑全局的前提下,求局部最优解就是全局最优解的一部分.按我的理解,贪心是和dp一样需要有无后效性的,你前面的决策做了就是做了,带悔贪心只能改变后面的决策的形态,而不能改变前面的决策.

2. 不同的操作之间会彼此影响,并且我们在不看全局的状态的前提下,无法第一时间确定当前对后面最优影响的操作是啥.通常情况下,感觉带悔贪心的每个操作会影响的操作是有限的.

3. 感觉能做带悔贪心的好像很多都可以设计一个复杂度更高的dp.不过这个似乎很合理,因为(2)告诉我们它能影响的操作大概率是不多的.

我们看这个题,第一点基本随便编个贪心都可以满足:就是先不断做$( - 2 , - 1 )$,最后不够了再加个$( - 1 , - 2 )$补一下.而第二点呢?显然每个地方的操作只会影响前后两个位置接下来的操作(当然,被影响到的位置有可能继续影响别人).

那么为什么能想到带悔贪心呢?其实只要发现有的时候$( - 1 , - 2 ) + ( - 1 , - 2 )$比$( - 2 , - 1 )$更优秀就自然能引到带悔贪心了.

好,现在我们仍然是做那个看上去就不太对的贪心:先不断做$( - 2 , - 1 )$,最后不够了再加个$( - 1 , - 2 )$补一下.我们通过样例以及其它栗子发现:有的时候$( - 1 , - 2 ) + ( - 1 , - 2 )$比$( - 2 , - 1 )$更优秀,这启发我们:能不能在做后面位置的时候将前面的$( - 2 , - 1 )$变成$( - 1 , - 2 ) + ( - 1 , - 2 )$呢?注意这里我们不能直接换:带悔贪心要求我们不能改变前面操作的状态.因此我们引入一个操作:如果当前前面存在一个$( - 2 , - 1 )$操作,那么我可以在这个位置进行一个$( 0 , - 3 )$操作.显然$( 0 , - 3 ) + ( - 2 , - 1 ) = ( - 1 , - 2 ) + ( - 1 , - 2 )$.我们完成了反悔的操作!

但是,我们直接认为$( - 1 , - 2 )$不可能反悔的原因是:它是一个补位操作,一个位置只有可能进行一次,这玩意不可能能反悔.可现在不一样了,我们的操作序列中有了两个$( - 1 , - 2 ) + ( - 1 , - 2 )$,怎么办呢?你当然可以对着这个操作再观察怎么反悔,但事实上有更高效的思路:我们直接考虑$( - 3 , 0 )$怎么反悔.这个看上去很疑惑:我们为了使$( - 2 , - 1 )$变成$( - 1 , - 2 ) + ( - 1 , - 2 )$而引入了一个新操作,这个新操作在原序列中是不存在的:它甚至有个很奇怪的限制条件:必须在前面存在$( - 2 , - 1 )$的时候才可以发动.那为什么我们可以直接考虑它如何反悔呢?

先看第一个问题:$( - 3 , 0 )$这个技能的发动是有前提条件的:前面必须有$( - 2 , - 1 )$才可以.但你注意我们是在贪心啊,我们很清楚每个地方用了几个$( - 2 , - 1 )$,也很清楚每个地方用了几个$( - 3 , 0 )$.

再看第二个问题:这个新操作为何能反悔呢?其实第一个问题解决这个问题也就解决了,由于贪心,我们知道了巨大多的信息,这个信息量是dp不能比的.因此这个条件如果dp的话看上去需要多记一维,但是贪心完全不用.

我们可以根据类似上面的操作迅速编出它怎么反悔:$( - 3 , 0 ) \rightarrow ( - 1 , - 2 ) + ( - 2 , - 1 ) = ( - 3 , 0 ) + ( 0 , - 3 )$,或者$( - 3 , 0 ) \rightarrow ( - 1 , - 2 ) + ( - 1 , - 2 ) + ( - 1 , - 2 ) = ( - 3 , 0 ) + ( 0 , - 3 ) + ( 0 , - 3 )$.

最后遇到一个点,能用$( 0 , - 3 )$就用$( 0 , - 3 )$,不够用的再补齐.这个原因也很简单:如果我们在这里不用$( - 3 , 0 )$而用其它的代替的话,你会发现无论如何都等价于$( - 3 , 0 )$然后后面再反悔.

再总结一下这个题中包含的带悔贪心:

这个带悔贪心包含若干个操作,这些操作之间可以互相转化,使得在前面进行的一个操作可以和在后面进行的一个操作一起,等价于前面进行了另一个操作.如同最经典的带悔贪心的模型,我们每次进行一个操作后,都会加入若干个可以进行的操作(在这个题中,一开始就在每个位置加入了无穷多的$( - 2 , - 1 )$和$( - 1 , - 2 )$的操作)(写一下代码就会发现,我们其实记录下了每个位置插入了多少个可行的$( - 3 , 0 )$操作).这些操作构成一个封闭的东西,使得反悔任意一个操作的反悔操作本身都可以使用若干操作表示出来.

寻找下界并证明

Example1([EER1]代价)

给你一个长度为$n$的序列$a$,保证$a_1 = a_n = 1$.每次你可以选择一个$i ( 1 < i < n )$将$a_i$删去并付出$a_{ i - 1 } a_i a_{ i + 1 }$的代价.删去$a_i$后序列两端会接起来,求删成两个$1$的最小代价.

首先注意到,如果有一个$1 < i < n$满足$a_i = 1$,那这个点最后删显然更优秀:如果我们把它删了,不仅肯定比最后删它劣(最后删它只需要$1$的代价),还有可能使原本能和它相邻的点这次和一个更大的数相邻了,显然不优秀.因此整个序列被若干个$1$所划分.接下来我们只考虑中间所有数$\geq 2$的情况.

再思考一个事实:当$a , b \geq 2$时,一定有$ab \geq a + b$.而考虑每两个相邻的点一定会被乘起来扔进答案,也就是说答案下界一定是$\sum_{ i = 2 }^{ n - 2 } a_i a_{ i + 1 } + \min_{ i = 2 }^{ n - 1 }{ a_i }$.注意到这个下界是可以构造出来的:找到每一段最小的点然后从左/右挨个删点即可.

Example2(loj3318)

首先考虑:给出一个排列,从原排列换到它的最小步数一定是它的逆序对数.因为我们可以每次找到应当被放到边界的点,然后不断把它换过去.

考虑现在构造$a$数组,每次对于还没选的最大值,显然要扔到尽可能靠后的位置,然后不断递归处理.

Example3

给定一张图,每个点上有一个权值$a_i$,我们每次可以删掉一个点以及其所有连边,代价是所有相邻的点的权值和.求删光图的最小代价.

首先注意到答案一共要更新边数次,不妨考虑边.

一条边可能对答案有两种贡献,也就是与它相邻的两个点的点权.它会对答案贡献后删的那个点的点权.显然所有边取最小值时是一个下界.这个下界是可以构造出来的:我们按照点权从大往小删即可.

Example4([UOJ280]题目难度排序)

先考虑$a_i$互不相同,那可以每次选一个最大的数,满足它加进去后整个集合的中位数$\leq$还没选的数的最小的数.注意到这里一定能构造出合法解,且如果选了另一个数一定更劣.

那如果可能存在$a_i$相同呢,我们先按照大小排序,然后选出一对小于等于所有数的中位数的$( a_i , a_{ i + 1 } )$,然后这么选:$a_i , a_{ i + 1 } , a_n , a_{ i - 1 } , a_{ n - 1 } , a_{ i - 2 } . . .$,一直到左边全部被填完,然后按照互不相同的方法填.

首先这么做一定是合法解,因为中位数会在$a_i$上震荡.其次这么做为什么是最优解呢?我们考虑一开始如果选了另一对大于中位数的相等的数,那一定不合法,因为最后会剩一些小数,会把这些东西震荡到一个更小的中位数.而如果一开始选了一个单点,接下来一定要不断选更大的点,这样比它小的数就没法加进去了.而等左边全部被填完后,由于这个时候中位数已经没有办法保持不变了,所以必定接下来要增大,而中位数不断增大只能按照互不相同的方法填.

Example5([CF1098D]Eels)

首先,我们猜测:我们一开始先让最小的两个互相吃,可能是最优秀的.接下来我们尝试证明这个猜测.

首先,对于一个不危险的操作来说,假设这次操作的两个数是$a$和$b$,其中$2 a < b$.我们尝试判断一下这个操作满足什么条件.这个时候,注意到如果$b$之前吃过别的鱼,假设是$c$和$d$(不妨假设$d \geq c$),有$b = c + d$,由鸽笼原理,发现$d > a$.这意味着:如果$a$都没被操作掉,那么$d$必不可能被操作掉,这也就是说$b$不可能出现.因此$b$在这次操作前一定没有吃过别的鱼.那互相残杀的鱼的重量就都一定小于$b$,且$a$就是所有一开始小于$b$的鱼的和.

我们按照鱼的重量从小到大排序,你会发现一次不危险操作涉及到的鱼一定是一条满足自己大于比自己小的所有鱼的重量和的两倍的鱼,我们称其为大鱼,也就是$w_i > 2 \sum_{ j = 1 }^{ i - 1 } w_j$,我们对此计数就可以完成一次操作.

那么问题又来了,这个东西一定是最小的吗?

我们考虑一个事实:我们要最小化不危险操作的数量,但很明显的一点是:每只大鱼都必须经过一次不危险操作才能变成一只更大的鱼,当然,如果它选择自杀,那么吃掉它的那只鱼会继承它的地位,在不死的情况下仍然要进行至少一次不危险操作才能变成更大的鱼,因此这显然是一个下界.而又可以构造出答案.

那么如何多组询问呢?首先发现大鱼不会很多,最多$\log w$个,我们考虑一下这个两倍的用处,我们按照值域$[ 1 , 1 ] , [ 2 , 2 ] , [ 3 , 4 ] , [ 5 , 8 ] , . . . , [ 2^{ k - 1 } + 1 , 2^k ]$将鱼分成若干组,不难发现大鱼只有可能是每个区间中最小的数字,因为不然,那么这个区间中最小的数字乘以二一定比它自己大.这个东西就很好维护了.

Example6(称球游戏)

给定$n$个球(其中有一个次品球,重量和其它球不一样)和一架天平,求最少通过多少次操作才能找到这个球.

我们通过这个游戏来引入信息论和判定树作为一个构造下界的工具.

首先引入一套语言体系来简化文字:

1. $S$表示标准球.

2. $< A , B >$表示称量集合$A$和集合$B$,$< A , B > = 0$表示平衡,$< A , B > = A$表示$A$较重,$< A , B > = B$表示$B$较重.

信息论

如果一个随机变量$x$有$n$种取值,出现概率分别为$p_1 , p_2 , \cdots , p_n$,则其熵为$H ( x ) = f ( p_1 , p_2 , \cdots , p_n ) = \sum{ C p_i \ln \frac{ 1 }{ p_i } }$,$C$为正整数,通常取$1$.(事实上这里的定义与真正的信息论的定义有一定的差别,不过原理是类似的,这里简化了一些.)

定理1:在得到关于随机变量$x$的一个熵为$h$的信息后,$x$的熵会减少$h$.

定理2:当一个随机变量的各种取值概率相等时,它的熵最大.

用信息论估计一下称球游戏的上界,如果我们已知次品轻重,由于一共有$n$个球,每个球等概率成为次品,因此总熵是$\ln n$,每称一次能得到的信息有三种:平衡,左边重,右边重,因此称一次能得到的熵是$\ln 3$,也就是说我们至少要猜$\frac{ \ln n }{ \ln 3 } = \log_3 n$次.如果我们不知道次品的轻重,那么至少要猜$\frac{ \ln 2 n }{ \ln 3 } = \log_3 2 n$次.

这就是称球游戏的信息论下界,接下来我们要做的无非就是证明这个下界能否取得到.

判定树

我们考虑将称量的决策树建立出来,每个叶子节点表示我们得到的答案,每个非叶子节点代表一次称量,每个非叶子节点有三个儿子,分别表示如果称量的结果是左偏/右偏/平衡时,接下来的策略.显然判定树的深度就是最坏情况下称量的次数.

$n$个叶子的树的最小深度是$\lceil \log_3 n \rceil$,这得出和信息论一样的下界估计(信息论的结论好像就是拿哈夫曼树证明的,不太懂).

子问题1(已知次品重量)

不妨假设$f ( n )$表示有$n$个球的最少次数,注意到$f ( 3 ) = 1$.

根据信息论,$f ( n ) \geq \lceil \log_3 n \rceil$,下面证明等号成立:

首先考虑证明$f ( 3^m ) = m$,$m = 1$时已经得证.$m > 1$时,考虑将所有球分成等数量的三份,称量其中两份.由于已知次品重量,这一次就可以找到次品在哪一份中,因此$f ( 3^m ) \leq f ( 3^{ m - 1 } ) + 1$.综合信息论下界$f ( 3^m ) \geq m$,我们不难得出以上结论.至于$n \ne 3^m$的情况,我们类似这个过程按照$n \bmod 3$的值讨论一下即可,于是有$f ( n ) \leq f ( \lceil \frac{ n }{ 3 } \rceil ) + 1$.

子问题2(不知次品轻重,已有一个标准球,需知道次品轻重)

根据信息论下界,$f ( n ) \geq \lceil \log_3 2 n \rceil$.

比起上面的问题,这个问题在于:如果我们称量不平衡,是不知道次品球在两堆中的哪一堆的.但我们思考到:虽然我们不知道在哪一堆,但我们得到了一个额外的信息:如果它在哪一堆,它的重量我们也就知道了.

下面证明引理:

引理

有两堆球,第一堆有$n$个球,第二堆有$m$个,已知其中有一个次品,并且次品如果在第一堆中只可能是重球,在第二堆中只可能是轻球.设此时的称量次数是$g ( n , m )$,则$g ( n , m ) = \lceil \log_3 ( n + m ) \rceil$.

先证明信息论下界,不难发现仍然是$g ( n , m ) = \lceil \log_3 ( n + m ) \rceil$.

首先不难发现,$g ( 1 , 0 ) = g ( 0 , 1 ) = 0 , g ( 1 , 1 ) = g ( 2 , 0 ) = g ( 0 , 2 ) = 1$.

仍然使用数学归纳,假设$n + m < k ( k \geq 3 )$的时候成立,我们接下来证明$n + m = k$的时候仍然成立.

情况1

若$n = 3 p , m = 3 q$,我们将$n$分成等数量的三堆:$A_1 , B_1 , C_1$,将$m$分成等质量的三堆$A_2 , B_2 , C_2$.

接下来称量$\langle A_1 + A_2 , B_1 + B_2 \rangle$.

1. 如果$\langle A_1 + A_2 , B_1 + B_2 \rangle = 0$,那么答案在$C_1 \cup C_2$中,此时有$g ( n , m ) = g ( \frac{ n }{ 3 } , \frac{ m }{ 3 } ) + 1$.

2. 如果$\langle A_1 + A_2 , B_1 + B_2 \rangle = A_1 + A_2$,由于若次品在$A_2$中,那么它不可能是重球,因此次品不可能在$A_2$中,同理不可能在$B_1$中,只可能在$A_1 \cup B_2$中,此时有$g ( n , m ) = g ( \frac{ n }{ 3 } , \frac{ m }{ 3 } ) + 1$.

3. $\langle A_1 + A_2 , B_1 + B_2 \rangle = B_1 + B_2$,同理.

此时数学归纳成立.

情况2

$n = 3 p + 1 , m = 3 q + 2$.此时我们将第一堆分成$A_1 ( p ) , B_1 ( p ) , C_1 ( p + 1 )$,将第二堆分成$A_2 ( q + 1 ) , B_2 ( q + 1 ) , C_2 ( q )$,然后$\langle A_1 + A_2 , B_1 + B_2 \rangle$,接下来和情况1一样,于是有$g ( n , m ) = \max \{ g ( p , q + 1 ) , g ( p + 1 , q ) \} = \lceil \log_3 \frac{ n + m }{ 3 } \rceil + 1$.

同理,当$n , m \bmod 3$的值是其它组合的时候,也都可以类似操作.引理得证.

由此引理得证.

回到原问题,进行数学归纳,我们继续来讨论$n \bmod 3$的值.

情况1

当$n = 3 p$时,直接分成$A ( p ) , B ( p ) , C ( p )$,然后$\langle A , B \rangle$.如果平衡则接下来需要$f ( p ) = \lceil \log_3 2 p \rceil$次,不然根据引理,需要$\lceil \log_3 ( p + p ) \rceil$次,因此$f ( n ) = \lceil \log_3 2 p \rceil + 1 = \lceil \log_3 6 p \rceil = \lceil \log_3 2 n \rceil$.

情况2

当$n = 3 p + 1$时,一种自然的想法是分成$A ( p + 1 ) , B ( p ) , C ( p )$,但是这种想法是错误的!我们考虑判定树,这种情况下,所有的叶子被分成了$2 p + 2 , 2 p , 2 p$,这显然是不优秀的.正确的做法是分成$A = \{ S , 1 , \cdots p \} , B = \{ p + 1 , \cdots 2 p + 1 \} , C = \{ 2 p + 2 , \cdots 3 p + 1 \}$.由于存在标准球,此时如果$\langle A , B \rangle = A or B$,那么转化成$g ( p , p + 1 ) = \lceil \log_3 ( 2 p + 1 ) \rceil$,不然转化成$f ( p ) = \lceil \log_3 2 p \rceil$.

剩下的情况也都类似,该问题解决.

子问题3(不知次品轻重,无标准球,需知道次品轻重)

考虑在第一次称量后,无论结果如何都会得到一个标准球,因此后面的问题都等价于子问题2,只需考虑第一次操作.再思考一下不难发现,在子问题2中,只有$n \bmod 3 = 1$的时候才会需要用到标准球,因此只有这里需要多一步.拟合一下函数,可以得到该问题$f ( n ) = \lceil \log_3 ( 2 n + 2 ) \rceil$.

子问题4(不知次品轻重,已有一个标准球,无需知道次品轻重)

这个问题复杂一些,而且难以估计下界.但我们可以用一下最优化dp来估计下界.

首先假设有无穷个标准球,我们每次将$a$个球放左边,$b$个球放右边,$a \leq b$,在左边补上$b - a$个标准球.

1. 如果天平不平衡,转化为引理问题(因为此时找到次品是谁必然知道它的轻重),因此需要$\lceil \log_3 ( a + b ) \rceil + 1$步.

2. 如果天平平衡,需要$f ( n - a - b ) + 1$步.

我们有$f ( n ) = \min_{ a , b } \{ \max \{ f ( n - a - b ) , \lceil \log_3 ( a + b ) \rceil \} \} + 1$.

注意到接下来的步数只与$a + b$有关,取$b - a \leq 1$,于是一个标准球已经够用了.

构造方程后手算几项,注意到$f ( n ) = \lceil \log_3 ( 2 n - 1 ) \rceil$.

接下来归纳法就简单了,只需要对于$n \bmod 3$的余数讨论一下,然后再讨论一下$a$的取值即可.

Example7(Ucup 3rd Stage 8 H)

每次可以询问一个区间,交互库返回这个区间中的次大元素所在位置,求$n$所在位置.要求询问次数$\leq \lceil 1 . 5 \log_2 n \rceil$,询问区间总长度$\leq 3 n$.

一个自然的想法是先问一下全局次大值,然后二分,但这样询问区间总长度就会爆掉.

因此考虑设$T ( n )$表示长度为$n$的,已知次大值(并且次大值)的最小次数.我们考虑每次判断一下最大值在哪边,因此把这个区间拆成两半,然后询问一下次大值所在的那一半,这样就可以判断最大值在不在那一半.

那么我们当然有方程$T ( n ) = \min_{ m < n } \{ \max \{ T ( m ) + 1 , T ( n - m ) + 2 \} \}$.

当然有$m_n \leq m_{ n + 1 }$,于是直接dp即可.

Exchange Arguments

模型1

给定$n$个元素$x_1 , . . . , x_n$,以及一个定义域为这些元素的序列,定义域为有序集合的函数$F$.求出对于所有的$n$阶排列$p$,表达式$F ( \{ x_{ p_1 } , x_{ p_2 } , . . . , x_{ p_n } \} )$最小值.

事实上会发现一些NPC问题也可以直接转化为这个模型,但是并无贪心解.我们接下来考虑这个模型内哪些问题是有贪心解的.

Example1(国王游戏)

给定$n$个二元正整数对$( a_i , b_i )$,将它们按照任意顺序排成一列.定义排成一列的代价为每个二元组的$a$乘上序列中这个二元组之后的所有二元组的$b$之和的总和,求最小代价.$n , a_i , b_i \leq 10^6$.

转化为上面的形式,也即:$F ( \{ ( a_1 , b_1 ) , . . . , ( a_n , b_n ) \} ) = \sum_{ 1 \leq i < j \leq k } a_i b_j$.

考虑调整法,令排列$( q_1 , . . . , q_n ) = ( p_1 , . . . , p_{ i - 1 } , p_{ i + 1 } , p_i , p_{ i + 2 } , . . . , p_n )$.则:

因而如果$a_{ p_i } b_{ p_{ i + 1 } } - a_{ p_{ i + 1 } } b_{ p_i } > 0$,则$F ( \{ ( a_{ p_1 } , b_{ p_1 } ) , . . . , ( a_{ p_n } , b_{ p_n } ) \} ) > F ( \{ ( a_{ q_1 } , b_{ q_1 } ) , . . . , ( a_{ q_n } , b_{ q_n } ) \} )$,也就是说$( p_1 , . . . , p_n )$不是最优解.因此只有满足$\forall 1 \leq i < n$,$\cfrac{ a_{ p_i } }{ b_{ p_i } } \leq \cfrac{ a_{ p_{ i + 1 } } }{ b_{ p_{ i + 1 } } }$可能是最优解.

如果一个$p$满足这样的性质,则所有$\cfrac{ a }{ b }$相等的数在排列中一定是连续的一段.而根据式子,这样的排列交换$\cfrac{ a }{ b }$相等的两个位置,是不会使答案改变的.因此直接按照$\cfrac{ a }{ b }$排序即可.

我以前所使用的调整法大概是先构造一个贪心策略,然后证明这个策略改变后一定不优秀或更劣.但是这样对于多峰函数会卡在一个局部最优解上而找不到全局最优解.但是,如果我们说不满足这个条件的一定不是最优解(可以使用调整得到更优解),我们再证明满足这个条件(即调整过程DAG的终止点)的都是最优解,继续做下去,就是很严谨的.

换句话说,我们要用调整法,就一定要证明调整过程中的DAG的零出度点是最优解.

模型通解

设给出的元素的集合为$S$,定义$S$上的一种二元比较关系$\leq$,将所有元素按照比较关系排序.在上一个问题中,不难发现以下性质:

1. 强完全性:$\forall a , b \in S$,$a \leq b \lor b \leq a = 1$.

2. 传递性:$\forall a , b , c \in S$,$a \leq b , b \leq c \Rightarrow a \leq c$.

3. $\forall a , b \in S$,如果$a \leq b$,则对于任意一个包含$\{ a , b \}$作为子段的元素序列$\{ s_1 , . . . , s_{ k - 1 } , a , b , s_{ k + 2 } , . . . , s_n \}$和$\{ s_1 , . . . , s_{ k - 1 } , b , a , s_{ k + 2 } , . . . , s_n \}$都有:$F ( \{ s_1 , . . . , s_{ k - 1 } , a , b , s_{ k + 2 } , . . . , s_n \} ) \leq F ( \{ s_1 , . . . , s_{ k - 1 } , b , a , s_{ k + 2 } , . . . , s_n \} )$.

问题满足以上性质,那么我们按照这种二元比较关系对元素排序后的答案一定是最优的.原因在于,首先这种操作构成DAG,而定义$\leq$后自然也就定义了$=$,所以DAG的零出度点自然是最优解点.

分析题目时,应该先分析第三条性质得到$\leq$的定义,然后判断是否符合前两条性质.

Example2

给定$n$个包含小写字符的字符串$s_1 , . . . , s_n$,找到一个$n$阶排列$p$,将$s_{ p_1 } , s_{ p_2 } , . . . , s_{ p_n }$顺序拼接得到$S$,使$S$的字典序最小.

令$s \leq t$当且仅当$s + t$的字典序$\leq$t+s

此时我们注意到:$s + t$的字典序小于等于$t + s$的字典序当且仅当$s^{ \infty } \leq t^{ \infty }$.原因是:不妨设$s$的长度$\leq t$的长度.若$s$不是$t$的前缀,那显然只需比较$t$的前缀和$s$的字典序即可,此时上面两个条件等价;若$s$是$t$的前缀,则我们需要比较$t$的前缀和$t$的后缀,注意到$t$的前缀还是$s$,于是需要比较$s$和$t$的后缀.类似可得.

于是这题可以使用后缀数组求任意两个字符串的后缀的最长公共前缀实现.

Example3

有$n$个箱子,第$i$个箱子有重量$w_i$和承载量$v_i$,$( w_i , v_i > 0 )$,将它们堆成一列使得每一个箱子上面的箱子总重量都不大于它的承载量.

考虑最大化$\min_{ i = 1 }^n \{ v_i - \sum_{ j = 1 }^{ i - 1 } w_j \}$,并判断是否$\geq 0$.

我们令$b_i = - ( v_i + w_i ) , a_i = - v_i$,则我们要最大化$\min \{ \sum_{ j = 1 }^{ i - 1 } b_i - \sum_{ j = 1 }^i a_i \}$.

我们接下来将证明所有形如这样的题的通法.

首先,定义$x \leq y$当且仅当$F ( \{ x , y \} ) \leq F ( \{ y , x \} )$,那么对于两个元素$( a_1 , b_1 ) , ( a_2 , b_2 )$,显然$( a_1 , b_1 ) \leq ( a_2 , b_2 )$当且仅当$\min \{ - a_1 , b_1 - a_1 - a_2 \} \geq \min \{ - a_2 , b_2 - a_1 - a_2 \}$.接下来我们证明这样的定义是满足性质的.

对于性质(3),显然成立,因为交换两个相邻位置不会对前面或后面产生影响,而前后对于这两个位置的影响也都可以抵消.

性质(1)显然成立.

再分析一下这个式子,这相当于不等式左边的两个元素都大于等于右边的最小值.我们讨论一下两种情况:

1. 都大于等于第一个元素,则相当于$a_1 \leq a_2 \land b_1 - a_1 \geq 0$.

2. 都大于等于第二个元素,则相当于$b_1 \geq b_2 \land b_2 - a_2 \leq 0$.

可能这里后面和$0$比较没有移项来得简洁.但是,相减的两项是同一个元素的两项,我们显然把它俩放在一类是更优秀的.

注意到需要对$b - a$的符号进行讨论:

1. 若$sgn ( b_1 - a_1 ) > sgn ( b_2 - a_2 )$,则不等式成立.

2. 若$sgn ( b_1 - a_1 ) = sgn ( b_2 - a_2 ) = 1$,则不等式成立当且仅当$a_1 \leq a_2$.

3. 若$sgn ( b_1 - a_1 ) = sgn ( b_2 - a_2 ) = 0$,则不等式成立.

4. 若$sgn ( b_1 - a_1 ) = sgn ( b_2 - a_2 ) = - 1$,则不等式成立当且仅当$b_1 \geq b_2$.

这四条中(2)和(4)的证明是显然的,(3)则是因为此时$b_1 = a_1$,$b_2 = a_2$,两条件必有一真.(1)则是因为此时满足$b_1 - a_1 > b_2 - a_2 \land sgn ( b_1 - a_1 ) \geq 0 \land sgn ( b_2 - a_2 ) \leq 0$.也就有$a_2 - a_1 > b_2 - b_1 \land b_1 \geq a_1 \land b_2 \leq a_2$.怎么着都能成立.

由此发现,对于$sgn ( b - a )$相同的类,内部排序是一定满足传递性的.

但是不同类之间并没有满足传递性,因此我们把排序条件修正为:

模型2

给定$n$个元素$x_1 , . . . , x_n$,以及一个定义域为这些元素的序列,值域为有序集合的函数$F$.求出对于给定整数$k$,所有的$n$阶排列$p$的长度为$k$的子序列,表达式$F ( \{ x_{ p_1 } , x_{ p_2 } , . . . , x_{ p_k } \} )$最小值.

如果$k = n$,则就是模型1.不然,我们考虑先选出一个大小为$k$的子集,然后使用模型1.不难发现,我们最后取出的$\{ x_{ p_1 } , x_{ p_2 } , . . . , x_{ p_k } \}$一定是$n = k$时最优解的一个子序列.这在一些情况下可以降低问题的难度.

Example

有$n$个物品,第$i$个物品有非负费用$c_i$和价值$v_i$,两个人进行如下博弈:

1. 第一个人要么选择一个物品,付出$c_i$的代价;要么选择结束游戏.

2. 第二个人可以选择删除这个物品,这会使博弈回到第一步,且第一个人付出的代价不会消失(这个操作最多可以进行$k$次);也可以选择不操作,此时第一个人获得$v_i$的收益,博弈结束.

3. 第一个人的总收益为收益减去付出的所有代价,第一个人希望最大化收益,第二个人希望最小化收益.$( n \leq 1 . 5 \times 10^5 , k \leq 9 )$

注意到第一个人要么一开始就结束游戏,要么连续选择$k + 1$个,然后收益为$\min_{ i = 1 }^{ k - 1 } \{ v_{ x_i } - \sum_{ j = 1 }^i c_{ x_j } \}$(如果第一个人把一个收益很大的放在最后选,那第二个人可以直接结束游戏防止他选到).注意到这和模型1的Example3是类似的,于是我们可以先排序,然后dp出子序列,复杂度$O ( n \log n + nk )$.

构造

增量构造

Example1

平面上有$n$条直线,将整个平面划分成若干部分.求证:这些部分可以黑白染色使得两个边相邻的部分颜色不相同,并给出构造方案.

考虑数学归纳,现在已经有$n$条直线的答案,求$n + 1$条直线的答案.我们将直线加到这个平面上,并将在这条直线其中一边的部分颜色全部取反.

Example2

给定若干个角度$a_1 , \cdots , a_n \in \{ 90 \degree , 270 \degree \}$,要求构造一个$n$边形(边必须平行于坐标轴),使得其内角依次是$a_1 , \cdots , a_n$.

首先有解条件显然是判定它们的和是否是$180 \degree ( n - 2 )$.

注意到相邻的$90 \degree$和$270 \degree$无非是在原序列上修修改改,这个可以一起合并起来.不断合并就做完了.

Example3(CF1770H)

呃,简单来说就是把边界往里缩,每次找左上和右上的四个点做匹配,然后剩下的缩进去.

原题解的那个图特别清晰.

Example4(ABC232H)

放在这个模块下就好想了,剥一行一列就行.最后可能会剩个边界情况,简单讨论.

找中间状态

常见于操作可逆,想要让$S \rightarrow T$.这个时候可以找一个中间状态$A$,让$S \rightarrow A , T \rightarrow A$.

Example1

坐标系上每个整点有个灯,初始只有$( X , 0 )$亮着,每次把$( x , y )$,$( x , y + 1 )$,$( x + 1 , y )$状态反转,给出终止状态,求初始亮的点的坐标,保证有解且唯一解.

$n \leq 10^5$,坐标的绝对值均$\leq 10^{ 17 }$.

首先我们发现,如果我们上面有若干个亮点,我们一定能把他们全杀了,变到下面,但下面的亮点没办法处理.怎么办呢?

一个想法是,我们将所有的亮点全都推到一条直线$y = - inf$,然后比对.我们注意到$( X , 0 )$向下推的过程类似一个组合数递推的过程,由经典公式$\binom{ S }{ T } \equiv [ T \subseteq S ] \bmod 2$可知,我们取$inf = 2^{ 63 } - 1$即可.然后最后在这条线上一定是有一个区间是$1$,我们需要找到区间左端点,我们选择在直线上随便找到一个$1$,由于$inf$很大,大于$10^{ 17 }$,因此这一步是好找的.然后最后二分+算贡献就可以找到左端点.

这个题有个改版,$n \leq 10^4$,但是初始点可能是$( X , Y )$.

这个题怎么做呢?类似上面的,我们考虑找到两个点$( j , - inf )$和$( k , - inf )$是亮的,并且他们分别是最靠左的和最靠右的,然后我们就能反解出$X$和$Y$.而上述条件满足当且仅当$[ j - X \subseteq Y + inf ]$.

如果我们随便找一个点$( p , - inf )$满足条件,那我们接下来只需要枚举$w$,判断$( p - 2^w , - inf )$是否是亮的,这样就能找到最靠左的,同理可以找到最靠右的.

那么怎么找到这个点呢?我们二分,每次判断一个区间$[ l , r ]$中是否有亮的.这个是难以判断的,但是好判断的是,这个区间中亮的灯的数量是奇数还是偶数.因此我们拿这个判断就行,有奇数就去奇数,两个都是偶数随便去一个.

二维计算几何

参考:https://www.luogu.com.cn/blog/command-block/ji-suan-ji-he-suan-fa-hui-zong.

这一部分比较常用,知识点也比较简单,会主要聚焦于写法.

基本函数

eps

1

const double eps=1e-10

浮点数计算存在误差,因此大部分时候不能直接进行大小是否相等的判断,我们需要通过规定精度来减少这种误差.

sign

1
2
3
4
5

inline int sign(double x){
if(x<eps&&-x<eps)return 0;
if(x>eps)return 1;
return -1;
}

用于判断一个浮点数是正数还是负数.

myabs

1
2
3
4

inline double myabs(double x){
if(sign(x)==-1)return -x;
return x;
}

用来求绝对值.

mysqr

1
2
3

inline double mysqr(double x){
return x*x;
}

用来求平方.

Point/Vector

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

struct Point{
double x,y;
Point(double X,double Y){
x=X;y=Y;
}
inline double len(){//判断到原点的距离
return std::sqrt(x*x+y*y);
}
inline int que(){//判断点的象限
if(sign(x)== 1&&sign(y)== 1)return 1;
if(sign(x)==-1&&sign(y)== 1)return 2;
if(sign(x)==-1&&sign(y)==-1)return 3;
return 4;
}
};
inline Point operator +(const Point &A,const Point &B){
return Point(A.x+B.x,A.y+B.y);
}
inline Point operator -(const Point &A,const Point &B){
return Point(A.x-B.x,A.y-B.y);
}
inline Point operator *(const double &c,const Point &A){
return Point(c*A.x,c*A.y);
}
inline Point operator *(const Point &A,const double &c){
return Point(c*A.x,c*A.y);
}
inline Point operator /(const Point &A,const double &c){
return Point(A.x/c,A.y/c);
}
inline double dist(const Point &A,const Point &B){
return std::sqrt(mysqr(A.x-B.x)+mysqr(A.y-B.y));
}

存储基本的点的信息.也可以看作一个二维向量.

向量内积

1
2
3

inline double operator *(const Point &A,const Point &B){
return A.x*B.x+A.y*B.y;
}

也就是$\vec{ a } \cdot \vec{ b } = | \vec{ a } | | \vec{ b } | \cos \theta = x_a x_b + y_a y_b$.也就等于$\vec{ a }$在$b$上的投影与$\vec{ b }$的模长的乘积.

内积可以用来判断夹角:

1. 如果$\vec{ a } \cdot \vec{ b } = 0$,则说明$\vec{ a } \bot \vec{ b }$.

2. 如果$\vec{ a } \cdot \vec{ b } > 0$,则说明$\vec{ a }$和$\vec{ b }$正方向的夹角小于$90 \degree$.

3. 如果$\vec{ a } \cdot \vec{ b } < 0$,则说明$\vec{ a }$和$\vec{ b }$正方向的夹角大于$90 \degree$.

两个向量同时旋转相同角度,其内积结果不变.

向量叉积

1
2
3

double operator ^(const Point &A,const Point &B){
return A.x*B.y-B.x*A.y;
}

也就是$\vec{ a } \times \vec{ b } = x_a y_b - y_a x_b$.也就等于$\vec{ a } , \vec{ b }$两个向量张成的平行四边形(有向)的面积.

叉积可以用来判断方向:

1. 如果$\vec{ a } \times \vec{ b } = 0$,说明二者共线.

2. 如果$\vec{ a } \times \vec{ b } < 0$,说明从$\vec{ a }$到$\vec{ b }$的方向是顺时针.

3. 如果$\vec{ a } \times \vec{ b } > 0$,说明从$\vec{ a }$到$\vec{ b }$的方向是逆时针.

向量旋转

1
2
3
4
5

//插入Point内部
inline Point rotate(double theta){
double st=std::sin(theta),double ct=std::cos(theta);
return Point(x*ct-A.y*st,A.x*st+A.y*ct);
}

也就是将这个竖向量乘左乘旋转矩阵$\begin{bmatrix}\cos \theta & - \sin \theta \ \sin \theta & \cos \theta\end{bmatrix}$.

Line

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

struct Line{
Point a,b;
double len(){
return dist(a,b);//计算线段长度,直线和射线基本没用
}
};
bool onl0(const Point &A,const Line &L){
return sign((A-L.a)^(A-L.b))==0;
}//判断点是否在直线上
bool onl2(const Point &A,const Line &L){
return (sign((A-L.a)^(A-L.b))==0)&&
(sign(A.x-std::min(L.a.x,L.b.x))>=0)&&
(sign(A.x-std::max(L.a.x,L.b.x))>=0)&&
(sign(A.y-std::min(L.a.y,L.b.y))>=0)&&
(sign(A.y-std::max(L.a.y,L.b.y))<=0);

}//判断点是否在线段上

用来维护直线/射线/线段的基本信息.

判断线段相交

1
2
3
4
5
6
7
8
9

bool isinter(const Line &L1,const Line &L2){
if(std::max(L1.a.x,L1.b.x)<std::min(L2.a.x,L2.b.x))return 0;
if(std::max(L2.a.x,L2.b.x)<std::min(L1.a.x,L1.b.x))return 0;
if(std::max(L1.a.y,L1.b.y)<std::min(L2.a.y,L2.b.y))return 0;
if(std::max(L2.a.y,L2.b.y)<std::min(L1.a.y,L1.b.y))return 0;
if(((L1.a-L2.b)^(L2.a-L2.b))*((L1.b-L2.b)^(L2.a-L2.b))<0)return 0;
if(((L2.a-L1.b)^(L1.a-L1.b))*((L2.b-L1.b)^(L1.a-L1.b))<0)return 0;
return 1;
}

前四行被称为快速排斥实验,后两行被称为跨立实验,也就是相交的两线段,对于其中一个线段而言,它的两个端点必然在另一个线段的两侧.但我们注意到共线线段也会通过跨立实验,因此拿快速排斥实验来判掉这种情况.

注意,线段交点不同于直线交点,两条共线的交点是有可能在端点上的.这个需要特判一下.

当然一般判断线段是否相交可以直接求直线交点,然后判断在不在线段上.

求直线交点

1
2
3
4
5

Point inter(const Line &L1,const Line &L2){
double ls=(L1.b-L1.a)^(L2.a-L1.a);
double rs=(L1.b-L1.a)^(L2.b-L1.a);
return L2.a+(L2.b-L2.a)*ls/(ls-rs);
}

原理在于,画一下$x_{ L_1 } , x_{ L_2 } , y_{ L_1 } , y_{ L_2 }$围成的四边形,计算面积后用等高不等底计算.注意$ls$和$rs$所代表的面积一正一负(不一定谁是正),因此需要减一下.

点到线的最短距离

1
2
3
4
5
6
7
8

inline double disl0(const Point &A,const Line &L){
return myabs(((L.a-A)^(L.b-A))/dis(L.a,L.b));
}
inline double disl2(const Point &A,const Line &L){
if(sign((A-L.a)*(L.b-L.a))<0)return dist(A,L.a);
if(sign((A-L.b)*(L.a-L.b))<0)return dist(A,L.b);
return disl0(A,L);
}

直线好做,直接算垂线段长度,用面积除以底长.

线段用点积判一下夹角即可.

凸多边形面积

利用叉乘,任取平面上一点$O$,则$S = \frac{ 1 }{ 2 } \sum_{ i = 1 }^n \overrightarrow{ OP_i } \times \overrightarrow{ OP_{ i + 1 } }$.证明的话考虑分$O$在内部和$O$在外部两种情况分类讨论.注意此时的$P$必须逆时针排列.

另外有皮克定理:在一个平面直角坐标系内,以整点为顶点的简单多边形(任两边不交叉),它内部整点数为$a$,它的边上(包括顶点)的整点数为$b$,则它的面积$S = a + \frac{ b }{ 2 } - 1$.

基本算法

排序算法

极角排序

定义原点$O$并建立坐标系,所有点按照和$O$所连直线与$x$轴正方向的夹角排序.

极角排序通常使用叉乘来实现,因为叉乘可以快速计算两个向量的方向.但是注意到需要先判断象限,再判断叉乘.

1
2
3
4
5
6
7
8

bool cmp(Point A,Point B){//判断A能否在B前面
A=A-O,B=B-O;//O=(0,0)的时候可以省略
if(A.qua()!=B.qua()){
return A.qua()<B.qua();
}
if(sign(A^B)==0)return A.x<B.x;
return sign(B^A)==1;
}

水平序排序

1
2
3
4

bool cmp(Point A,Point B){
if(sign(A.x-B.x)==0)return sign(A.y-B.y)==-1;
return sign(A.x-B.x)==-1;
}

也就是$x$相同比$y$,否则比$x$.

二维凸包

定义

包住平面上某个点集的周长最小的简单多边形,一定是凸多边形.

实现

用水平序排序,然后从左往右扫一遍得到上凸壳,从右往左扫一遍得到下凸壳.

用一下以下函数:

1
2
3
4
5
6

inline bool anticlock(const Point &A,const Point &B,const Point &C){
return sign((A-B)^(B-C))==-1;
}
inline bool isline(const Point &A,const Point &B,const Point &C){
return sign((A-B)^(B-C))==0;
}

前者判断是否$ABC$三点是一个上凸的(注意$ABC$三点横坐标应该不降).后者判断三点共线.

旋转卡壳

定义

定义凸包上的对踵点对,也就是拿两条平行直线卡着凸包转,这两条直线会卡住凸包的两个点,这些点对组成的集合就是对踵点对集合.

实现

逆时针枚举边,然后看对面有什么被卡住了.由于凸包的凸性,在边逆时针转的时候,另一边的对踵点也会逆时针转.只要找到距离这条边所在直线最远的点即可.但这样的点可能有俩.可以简单特判,也可以加上微小随机扰动量使得这种情况可以忽略.

闵可夫斯基和

一般只讨论凸包的闵可夫斯基和.

定义

两个区域$A , B$的闵可夫斯基和定义为$\{ a + b \mid a \in A , b \in B \}$.

实现

事实上,新的区域所形成的凸包,一定是原本$A , B$的凸包的边按照某种顺序连接起来得到的结果.

我们考虑旋转一下$A , B$,使得$B$有一条边成为最右边的直上直下的一条边,然后考虑答案区域的最右边的边,这条边一定是$B$这个边加上$A$的最右边的点.这样这条边必定还在最终的凸包上.就算$A$最右边的是一条边,你也会发现最终的凸包最右边也一定是由$A$的这条边和$B$的这条边拼起来的.

显然,逆时针转一遍整个凸壳,将每条边改为向量(按照逆时针转的方向)然后极角排序,最后顺次链接就是答案.

半平面交

定义

定义半平面为满足$ax + by + c > 0$或$ax + by + c \geq 0$的点对$( x , y )$组成的集合,感性理解就是一条直线的一侧.

实现

首先直线不好描述左右侧,我们把直线改成向量,这样方便描述左右侧.并不妨假设所有的向量所表示的半平面在向量的左侧.如果两条向量方向相同,则取更靠左的那一条,也就是所在直线截距更大的那个,另一个直接删了就是了.当然你不想删可以把那个废物放前面,这样根据下面的操作过程中它会被弹掉.

我们这么实现:按照上面的顺序一个一个插入,维护一个单调队列.如果前两条向量的交点不在当前这条向量的控制范围,不难发现上一条向量是废物,弹掉它.这样做到最后,队首和队尾可能都有一些废物向量,把它们判掉弹掉即可.

三维计算几何

这一部分知识点比较困难,而几乎用不到,因此只讲简单知识点,就当是高中立体几何知识补档!

基本概念

直线

使用直线的方向向量$\vec{ s } = ( n , m , p )$和直线上一点$M_0 = ( x_0 , y_0 , z_0 )$.那么方程显然为:

如果换元,我们还有参数方程:

平面

使用平面上的一点$P_0 ( x_0 , y_0 , z_0 )$和该平面的法向量$\vec{ n }$来表示一个平面,不妨设$\vec{ n } = ( A , B , C )$,则该平面的方程显然为:

如果我们令$D = - ( Ax_0 + By_0 + Cz_)$,那么平面方程为:

夹角

两直线夹角.

直接求方向向量的夹角,然后取正值.

对于方向向量分别是$\vec{ s_1 } = ( n_1 , m_1 , p_1 ) , \vec{ s_2 } = ( n_2 , m_2 , p_2 )$,也就有$\varphi = \arccos ( \frac{ | \vec{ s }_1 \cdot \vec{ s }_2 | }{ | \vec{ s }_1 | | \vec{ s }_2 | } ) \\$.

直线与平面的夹角

同样使用向量,不妨设方向向量$\vec{ s } = ( n , m , p )$,法向量$\vec{ f } = ( a , b , c )$,那么$\varphi = \arcsin ( \frac{ | \vec{ s } \cdot \vec{ f } | }{ | \vec{ s } | | \vec{ f } | } )$.

另外,由上面这个式子,不难得到一些特殊情况下的判定标准:

1. 若直线与平面平行,则$am + bn + cp = 0$.

2. 若直线与平面垂直,则$\frac{ a }{ m } = \frac{ b }{ n } = \frac{ c }{ p }$.注意这里分母可能除以$0$,我们实际上应该是三个形如$a = mt$的参数方程,这里简化了.

交点

联立方程硬解.

基本定理

参考:https://zhuanlan.zhihu.com/p/401766934

三余弦定理(最小角定理)

这个定理说明直线与平面的夹角,是所有包含直线的平面与这个平面形成的夹角中最小的那一个.并且偏移量决定了差距.

三正弦定理(最大角定理)

这个定理说明二面角是另一个平面上的直线与平面的夹角中最大的那个,并且偏移量决定了差距.