引言

Bitset 是一种利用对布尔数组压位存储的方法,达到优化时间常数、空间常数的目的的黑科技。利用 Bitset,可以方便地对布尔数组进行按位逻辑运算,优化 32 或 64 的常数。在某些素质极差的卡常题中运用会有奇效。

More...


转自知乎:八大排序算法稳定性分析,原来稳定性是这个意思……
这是 €€F 非常喜欢的排序稳定性分析……

稳定性定义: 排序前后两个相等的数相对位置不变,则算法稳定。
稳定性的好处: 从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。

各排序算法的稳定性:

  1. 堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法;
  2. 基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

More...



数学上,高斯消元法(Gaussian Elimination),是线性代数中的一个算法,可用来为线性方程组求解,求出矩阵的秩,以及求出可逆方阵的逆矩阵。当用于一个矩阵时,高斯消元法会产生出一个行梯阵式。

解多元方程组特别方便。

More...


Linux 下没有 Dev-cpp,每次遇到想要调试的代码就是坠痛苦的。所以我们还是得学点 gdb 调试的命令。

首先执行 g++ a.cpp -g,生成 a.out 或者 a.exe
执行 gdb a.out,出现一大段介绍,进入 gdb 调试。

More...


主定理可以用来分析递归算法的时间复杂度(也叫渐进复杂度)。在以前,我们知道快速排序的时间复杂度是 $ \Theta (N \ast \log_2 N )$ ,我们也知道它不稳定,但是我们仿佛不知道这个 $ \Theta (N \ast \log_2 N )$ 是怎么来的……学习了主定理,我们就可以证明了~

这个“主定理”名字真的十分霸气:Master Theorem……

More...


在一维线性动态规划里,我们经常见到形如 $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$ 有关。这时候就要用到另一种优化方式:斜率优化。

More...


今天考试的时候遇到一题背包题目,我直接打了暴力的 0/1 背包,理论复杂度是 $\Theta (N^3\ast W)$,大概是 $10^9$ 这个级别……时限 1s,交上去就全部 TLE 了……然后我就想起了这个终极优化模板,加上以后居然全 A 了!时间居然只有 200ms 左右……

$10^9$ 级别居然都可以压过去!!!

More...