『初丶晴』的小窝

微积分学习笔记 - 04 指数、对数、双曲函数的导数与极限 进入 传送门，阅读刊载在专栏《微积分阅读笔记》下的全部文章。 六、指数函数与对数函数的导数本节通过对自然常数 $\mathrm{e}$ 的探究推出指数与对数函数的导数。请务必在阅读本节前了解指数与对数的基本运算性质。 6.1   $\mathrm{e}$ 的定义与相关极限$\mathrm{e}$ 的定义   对于极限，定义 \mathrm{e}=\lim\limits_{h\to 0^+}(1+h)^{\frac1h}关于它的求解与证明暂时略去。通过上述极限可以推出许多性质。 考虑极限 L=\lim\limits_{n\to \infty}(1+\dfrac rn)^n令 $h=\dfrac rn$，这样 $n=\dfrac rh$，对上述极限变形，有 L=\lim\limits_{h\to 0^+}(1+h)^{\frac rh}=\lim\limits_{h\to 0^+}((1+h)^{\frac 1h})^r=\mathrm{e}^r注意此时变成了 $h\to 0^+$ 处的极限。这样，就 ...

微积分学习笔记 - 03 隐函数求导 进入 传送门，阅读刊载在专栏《微积分阅读笔记》下的全部文章。 五、隐函数求导这一节与其他节相关很少，但后面也要经常用到，所以只好单拎出来。 5.1   隐函数求导考虑两个导数 \dfrac{\mathrm{d}}{\mathrm{d}x}(x^2) \quad,\quad \dfrac{\mathrm{d}}{\mathrm{d}x}(y^2)前者显然为 $2x$，但后者却不一定。这主要取决于变量 $y$ 与变量 $x$ 间的变化关系。 那怎样求它的导数呢？参考链式求导法则，变量 $x$ 的改变会导致变量 $y$ 的改变，而变量 $y$ 的改变又会导致 $y^2$ 的改变。 令 $u=y^2$，则 $\dfrac{\mathrm{d}u}{\mathrm{d}y}=2y$，则： \dfrac{\mathrm{d}}{\mathrm{d}x}(y^2)=\dfrac{\mathrm{d}u}{\mathrm{d}y}\dfrac{\mathrm{d}y}{\mathrm{d}x}=2y\dfrac{\mathrm{d}y}{\mat ...

微积分学习笔记 - 02 三角函数的极限和导数 进入 传送门，阅读刊载在专栏《微积分阅读笔记》下的全部文章。 三、三角函数的极限本节简短记录几个比较重要的三角函数极限，对后文推出三角函数的导数有重要作用。 3.1   正弦函数的极限首先考虑一个重要极限 \lim\limits_{x\to 0}\dfrac{\sin(x)}{x}这个极限的求解将借助单位圆完成。 三角形 OAC、扇形 OAB、三角形 ODB 的面积分别等于 $\dfrac{\sin(x)}{2}$，$\dfrac x 2$，$\dfrac{\tan(x)} 2$，有不等关系 \sin(x)

微积分学习笔记 - 01 极限导论与微分 进入 传送门，阅读刊载在专栏《微积分阅读笔记》下的全部文章。 一、极限导论1.1   极限的定义极限：对于函数 $f(x)$，任选 $\epsilon>0$，可以任选 $\delta>0$，使得：对于所有满足 $0<|x-a|<\delta$ 的 $x$，有 $|f(x)-L|<\epsilon$，则称函数 $f(x)$ 在 $a$ 处的极限为 $L$，记作： \lim\limits_{x\rightarrow a}=L上述定义可以简单理解成，在变量 $x$ 接近于 $a$ 时，函数值无限接近于 $L$。 例如，对于函数 $f(x)=x+1$，通过分析函数图像可知，有 $\lim\limits_{x\rightarrow 2}=3$。 再例如，对于函数 $g(x)=\begin{cases}x-1&\text{如果}x\not=2\\3&\text{如果}x=2\end{cases}$，事实上 $\lim\limits_{x\rightarrow 2}=1$。这是因为只有那些 ...

做题笔记[AGC002] A - Range Product 标签：数学 难度：★☆☆☆☆ 题目大意给你两个整数 $a$ 和 $b$ ($a≤b$)。 判断 $\prod\limits_{i=a}^b i$ 是正、负还是零。 数据范围$-10^9\le a\le b\le 10^9$。 解题思路判断正负性，经过 $0$ 的乘积为 $0$，再判断负数个数即可。 参考代码12345678910#include<iostream>using namespace std;int a,b;int main(){ cin>>a>>b; if(a<=0&&b>=0) cout<<"Zero"; else if(a>0||(b-a+1)%2==0) cout<<"Positive"; else cout<<"Negative"; return 0;} B - Box and Ball 标 ...

做题笔记[AGC001] A - BBQ Easy 标签：贪心 难度：★☆☆☆☆ 题目大意将 $2n$ 个数分为 $n$ 组，每个数有值 $L_i$，每组两个数，每个数都被且只被分到一组。一组的权值是两个数值的最小值，分组方案的值就是每组值之和，求分组方案的最大值。 数据范围$1\le n\le 100,1\le L_i\le 100$。 解题思路考虑贪心。将数组排序后按顺序两两分组即可。 参考代码123456789101112131415#include<iostream>#include<algorithm>using namespace std;#define MAXN 205int n,a[MAXN];int main(){ cin>>n; n*=2; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); int ans=0; for(int i=1;i<=n;i+=2) ans+=a[i]; cout<<a ...

模拟退火 一、模拟退火模拟退火算法用于计算运算量大或随机概率较高的多峰函数最值问题，在多次退火下，正确的概率表现的还是非常出色的。 1.1 $\quad$ 劣解的接受与 Metropolis 准则爬山算法只能应用于单峰函数，因为它每次只在附近只寻找更加优秀的解。放在多峰函数下容易陷入局部最大值，而无法找到全局最大值。 不同于爬山算法，在模拟退火算法中，我们在当前位置的一定范围内随机一个位置进行决策。如果这个决策比现在的决策更加优秀，我们无条件地接受；如果这个决策不如当前的决策我们以某种概率接受这个劣解。 具体地，我们像冶金工业退火一样，一开始，我们有一个温度 $T$，表示当前的活跃性。这个温度随着随机次数的增加而降低，当最终小于某一个温度 $t_0$ 时就终止退火。 我们设接受一个比当前解劣 $\Delta E$ 的劣解的概率为 $P(\Delta E)$。根据 Metropolis 准则，我们划定这个概率，并让其与当前温度有关。即表示：随机次数较小时，我们有更大概率接受劣解；随机次数过多时，我们有较小的概率接受劣解。这样既能保证向着最大值的方向查找，又能避免陷入局部最大值。 Met ...

渐近记号与主定理 渐近记号用来描述函数的运行时间，刻画运行时间的上界、确界、下界。使用递归定义的函数通常使用主定理分析时间复杂度。 一、渐近记号本节定义一些基本函数，用于描述时间复杂度。 1.1 $\quad$ 渐进记号、函数与运行时间1.1.1 $\quad$ $\Theta$ 记号我们使用 $\Theta$ 记号描述函数的渐近紧确界。 形式化地， $\Theta (g(n))=\{f(n):\exists c_1,c_2,n_0:\forall n\ge n_0,0\le c_1g(n)\le f(n)\le c_2g(n) \}$。 其中，冒号意为“使得”。 也就是说，存在常量 $c_1,c_2,n_0$，可以将 $f(n)$ 夹入 $c_1g(n)$ 和 $c_2(n)$ 中。$\Theta(g(n))$ 要求每个成员 $f(n)\in \Theta(g(n))$ 渐近非负。 我们通常使用 $\Theta(1)$ 表示常量或某个变量的常量函数。 1.1.2 $\quad$ $O$ 记号当函数只有一个渐近上界时，使用 $O$ 记号。 形式化地， $O (g(n))=\{f(n): ...

后缀数组与应用 后缀数组 (Suffix Array) 是处理字符串问题的有力工具之一，通常利用后缀数组 $sa$ 处理字符串子串与后缀串排序、公共前缀等问题。 一、后缀数组通过计算后缀数组与排名数组，辅助解决系列问题。 1.1 $\quad$ 约定与定义对于一个长度为 $n$ 的字符串 $s$，我们定义 $s_i\dots s_n$ 构成的子串为 $s$ 在 $i$ 位置上的后缀，下面给出几个函数的定义： $sa_i$：后缀数组。表示 $s$ 的所有后缀串中，按字典序排名，第 $i$ 小的后缀串的起始位置。 $rk_i$：名次数组。表示起始位置为 $i$ 的后缀串的排名（按字典序）。 不难发现，上面两个函数互为反函数，即： \begin{aligned} sa[rk[i]]=i\\ rk[sa[i]]=i \end{aligned} $height_i$：高度数组。表示排名为 $i$ 的后缀串与排名为 $i-1$ 的后缀串的最长公共前缀。特殊地，$height_1=0$，因为没有比它排名小的后缀串。形式化地： ht[i]=\text{LCP}(sa[i],sa[i-1] ...

Ramsey 定理 一、Ramsey 定理Ramsey 定理是关于鸽巢原理的重要拓展，甚至可以从另一个维度解释鸽巢原理。 1.1 $\quad$ 基本定义我们先给出一些定义。 对于由 $n$ 个点构成的图，两两节点直接都有边直接相连，则成这张图是完全图。 我们把 $p$ 个点的完全图，记作 $K_p$。 我们用两种颜色对所有边进行染色，染色成 $a$ 或者 $b$，如果下面两个条件至少满足其一： 存在 $n$ 个点的子集，使其构成的完全图中所有边的颜色为同一种颜色 $a$； 存在 $m$ 个点的子集，使其构成的完全图中所有边的颜色为同一种颜色 $b$。 我们记作 K_p\rightarrow K_m,K_n我们记 Ramsey 数 $r(n,m)$ 是使 $K_p\rightarrow K_n,K_m$ 的最小正整数 $p$。我们不难发现 r(n,m)=r(m,n) 例子 $\quad$ 在 $6$ 个人构成的集合中，要么 $3$ 个人互相认识，要么 $3$ 个人互相不认识。 我们给出这个例子的证明。 我们对于 $6$ 个点的完全图，两个人间互相认识则边染红色，否则边染蓝色。 ...