SkyWT

SkyWT

我们的征途是星辰大海

⚙️ 本网站主题尚未开发完善,可能偶现奇怪的 bug。
✨ 最近更新:添加全站 PJAX 无刷新(220930)。

树链剖分,可以把一棵树划分成多条链,对于每条链可以用线段树等数据结构进行维护,将树形结构的问题转化。

常见的方法是轻重链剖分,即 Heavy-Light Decomposition。

More...


矩阵乘法的很多应用都是围绕矩阵乘法的定义式展开的:

$$C[i,j]=\sum_{k=1}^{b} A[i,k]\ast B[k,j]$$

本质上是一种动态规划吧。

More...


引言

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

More...


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

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

各排序算法的稳定性:

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

More...


$$ \begin{bmatrix} x_{11} & x_{12} & x_{13} \\ x_{21} & x_{22} & x_{23} \\ x_{31} & x_{32} & x_{33} \end{bmatrix} $$

每增加一个维度,世界便会增加无限的美感。

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...