这是 rCore Tutorial Book 第一章「应用程序与基本执行环境」的练习。
💬 博客评论 IP 错乱的问题已修复。最近更新：修复 Edge 浏览器的导航栏阴影显示（230627）。
📧 现在可以使用邮箱订阅本博客。欢迎订阅！
📧 现在可以使用邮箱订阅本博客。欢迎订阅！
rCore Tutorial Chapter 1 练习
树链剖分（Heavy-Light Decomposition）小结
矩阵乘法在图论中的简单应用
C++ 手写 Bitset 代码模板
引言
Bitset 是一种利用对布尔数组压位存储的方法，达到优化时间常数、空间常数的目的的黑科技。利用 Bitset，可以方便地对布尔数组进行按位逻辑运算，优化 32 或 64 的常数。在某些素质极差的卡常题中运用会有奇效。
（转）八大排序算法稳定性分析
转自知乎：八大排序算法稳定性分析，原来稳定性是这个意思……
这是 €€F 非常喜欢的排序稳定性分析……
稳定性定义： 排序前后两个相等的数相对位置不变，则算法稳定。
稳定性的好处： 从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。
各排序算法的稳定性：
- 堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法；
- 基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
矩阵乘法在动态规划中的应用
$$ \begin{bmatrix} x_{11} & x_{12} & x_{13} \\ x_{21} & x_{22} & x_{23} \\ x_{31} & x_{32} & x_{33} \end{bmatrix} $$
每增加一个维度，世界便会增加无限的美感。
高斯消元入门
数学上，高斯消元法（Gaussian Elimination），是线性代数中的一个算法，可用来为线性方程组求解，求出矩阵的秩，以及求出可逆方阵的逆矩阵。当用于一个矩阵时，高斯消元法会产生出一个行梯阵式。
解多元方程组特别方便。
gdb 调试的使用
Linux 下没有 Dev-cpp，每次遇到想要调试的代码就是坠痛苦的。所以我们还是得学点 gdb 调试的命令。
首先执行 g++ a.cpp -g，生成 a.out 或者 a.exe；
执行 gdb a.out，出现一大段介绍，进入 gdb 调试。
主定理与递归程序时间复杂度的计算
主定理可以用来分析递归算法的时间复杂度（也叫渐进复杂度）。在以前，我们知道快速排序的时间复杂度是 $ \Theta (N \ast \log_2 N )$ ，我们也知道它不稳定，但是我们仿佛不知道这个 $ \Theta (N \ast \log_2 N )$ 是怎么来的……学习了主定理，我们就可以证明了～
这个“主定理”名字真的十分霸气：Master Theorem……
斜率优化小结
在一维线性动态规划里，我们经常见到形如 $f(i)=min/max(f(j)+c_i)$（其实可以看成 $f(i)=min/max(a_i+b_j)$ ）这样形式的转移方程。朴素做法是 $\Theta (N^2)$。显然这样的形式可以用单调队列维护，优化到 $\Theta (N)$。但是如果遇到 $f(i)=min/max(a_i\ast b_j+c_i+d_j)$ 这样的，似乎用单调队列就难以维护了……因为 $a_i\ast b_j$ 既与 $i$ 有关，又与 $j$ 有关。这时候就要用到另一种优化方式：斜率优化。