SkyWT

SkyWT

我们的征途是星辰大海

🚧 博客系统即将搬迁,将集成到 skywt.cn/blog。欢迎体验!
📧 现在可以使用邮箱订阅本博客。欢迎订阅!

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


简单来说,数位 DP 大概就是把一个数字拆开按位进行 DP 的一种思想。

HDU 3555 Bomb

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

More...


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

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

More...


据说今年所有学校都没有推荐名额???

More...


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

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

More...


这题思路很简单,但是调试花了我一个下午……最后发现是一种情况没取 abs……(吐血)

题目链接:POJ 3977 Subset

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


所谓二分图(Bipartite Graph)就是这样的一个图:

简单地说,就是一张图里的所有点可以分为两组(如上图),并且每条边都跨越两组。这样的图就是二分图。

More...