[Top] To-do List
2018-08-09
每一个不曾起舞的日子，都是对生命的辜负。
Passages
（转）八大排序算法稳定性分析
2018-10-11
转自知乎：八大排序算法稳定性分析，原来稳定性是这个意思……
这是 €€F 非常喜欢的排序稳定性分析……
稳定性定义： 排序前后两个相等的数相对位置不变，则算法稳定。
稳定性的好处： 从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。
各排序算法的稳定性：
- 堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法；
- 基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
分享几道 NOIP 初赛的奇葩题目
2018-10-08
快看看 CCF 是怎么把初赛完成脑筋急转弯竞赛的……
孙某和张某是考古学家老李的学生。有一天，老李拿了一件古物来考验两人，两人都无法验证出来这件古物试谁的。老李告诉了孙某拥有者的姓，告诉张某拥有者的名，并且在纸条上写下以下几个人的人名，问他们知道谁才是拥有者？
纸条上的名字有：沈万三、岳飞、岳云、张飞、张良、张鹏、赵括、赵云、赵鹏、沈括。
- 孙某说：如果我不知道的话，张某肯定也不知道。
- 张某说：刚才我不知道，听孙某一说，我现在知道了。
- 孙某说：哦，那我也知道了。
请问：那件古物是谁的？
LightOJ 1073 DNA Sequence 题解：字符串+状压 DP+字符串压位/搜索
2018-10-04
Description
Link: LightOJ 1873 DNA Sequence
You are given a list of strings over the alphabet A (for adenine), C (cytosine), G (guanine), and T (thymine), and your task is to find the shortest string (which is typically not listed) that contains all given strings as substrings. If there are several such strings of shortest length, find the smallest in alphabetical/lexicographical order.
Time Limit: 4 second(s)
Memory Limit: 32 MB
矩阵乘法在动态规划中的应用（POJ 3233 Matrix Power Series、HDU 2065 “红色病毒”问题）
2018-10-02
\begin{bmatrix} x_{11} & x_{12} & x_{13} \\ x_{21} & x_{22} & x_{23} \\ x_{31} & x_{32} & x_{33} \end{bmatrix}
每增加一个维度，世界便会增加无限的美感。
高斯消元（Gaussian Elimination）入门
2018-09-28
数学上，高斯消元法（Gaussian Elimination），是线性代数中的一个算法，可用来为线性方程组求解，求出矩阵的秩，以及求出可逆方阵的逆矩阵。当用于一个矩阵时，高斯消元法会产生出一个行梯阵式。
解多元方程组特别方便。
数位 DP 入门：HDU 3555 Bomb
2018-09-27
简单来说，数位 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?
gdb 调试的使用
2018-09-27
Linux 下没有 Dev-cpp，每次遇到想要调试的代码就是坠痛苦的。所以我们还是得学点 gdb 调试的命令。
首先执行 g++ a.cpp -g，生成 a.out 或者 a.exe；
执行 gdb a.out，出现一大段介绍，进入 gdb 调试。
主定理（Master Theorem）与递归程序时间复杂度的计算
2018-09-16
主定理可以用来分析递归算法的时间复杂度（也叫渐进复杂度）。在以前，我们知道快速排序的时间复杂度是 \Theta (N \ast \log_2 N ) ，我们也知道它不稳定，但是我们仿佛不知道这个 \Theta (N \ast \log_2 N ) 是怎么来的……学习了主定理，我们就可以证明了～
这个“主定理”名字真的十分霸气：Master Theorem……
POJ 3465 Battle 题解：可“反悔”的贪心
2018-09-14
很多题目的贪心想法都是一个简单粗暴的贪心加上可“反悔”的操作。这样可以确保答案的正确性。
Description
You're Zhu Rengong, a formidable hero. After a number of challenging missions, you are finally facing the final Boss – a black dragon called Heilong. Due to his overwhelming power, you have to plan your actions carefully.