算法竞赛入门系列

算法废人的口胡系列

回归线下活动

对于学习计算机科学和软件工程的学生来说,熟悉 Linux 操作系统是一项宝贵的技能。对于参加算法竞赛的同学,Linux 有什么特别之处?在比赛时怎么 “正确” 地打开 Visual Studio Code?如果你还不知道万能的 Ctrl-Shift-P,那么这个讲座就适合你!

贪心算法看似 “简单”,但却也捉摸不定:互联网上有很多简短的题解、不太明白的 “证明”,让贪心变得更神秘。我们将用最基础的数学工具,帮助大家还原解决贪心问题时的推导过程。

递归 (汉诺塔) 一直以来都是同学们的噩梦——学习了许多年编程的同学依然感到一知半解。我们从 C++ 函数和数学函数 (类似 f(x)=x2+2x+1f(x) = x^2 + 2x + 1) 之间的区别和联系入口,重新理解递归和栈。

疫情时期的讲座视频

多项式是一类十分基础的数学对象——因为可以为多项式确定系数,我们能将 “信息” 编码在多项式中,并通过多项式运算实现信息的保存和 “加工”。本次课以插值 (通过平面上的点确定多项式) 为主线,并讲解如何在基础上理解快速傅里叶变换、幂级数等重要数学工具。

用更直观的方式理解矩阵和线性变换:我们可以把它们在三位空间里绘制出来!在这个课程中,我们为大家准备了真实的三维模型,通过这种方式,我们可以更直观地理解计算机图形学中的几何建模、高斯消元等问题。

容斥原理是一类重要的计数工具,它实现了 “化并为交”:将 ABCD|A\cup B\cup C\cup D| 这样 “不规则” 的计数问题 (例如凸多边形的并可以任意 “不规则”) 的计数问题改写成子集交 (如 ABC|A \cap B\cap C|,凸多边形的交依然是凸多边形) 的线性组合,从而能够解决一大类看起来很 “独特” 的计数问题。这个视频会带大家 “用集合的视角理解计数”,并用 “求线性方程组” 的方法重新理解容斥原理。

求和 (Σ\Sigma) 是算法竞赛中普遍使用的运算符——但它与我们平时接触的代数运算 (加减乘除) 不同,更像是一个 “编程语言”。这个视频里介绍如何求和算子的入门和一些常用的技巧,包括一些求和问题 (例如 1k<nk\sum_{1 \le k < n} \lfloor\sqrt k\rfloor) 的求解和 Mobius 函数的使用。

还记得我们在中学学 “代数” 之前,在小学学过的 “算术” 吗——对,就是用固定的规则算出一个表达式的值。对于大家可能头疼的 “线性代数”,同样是从 “线性算术” 发展而来的。令人惊奇的是,带着 “线性算术” 去理解线性代数,矩阵、特征值、高斯消元法……都会有新的理解。

把三个熟悉的数学概念:多项式 ax2+bx+cax^2+bx+c、递推 f(n)=f(n1)+f(n2)f(n)=f(n-1)+f(n-2)、无限循环小数 0.9˙0.\dot{9} 结合到一起会发生什么?作为中学生 “高等数学” 的启蒙课,我们探索幂生成函数、指数生成函数、狄利克雷生成函数乘法 (卷积) 的推导和妙用。

最大流/最小割定理一直是组合优化里一个理解的难点。在这一课中,我们通过一个更简单的问题:求有向图中的一条路径 (或证明有向图中没有路径),引出割的概念,自然地推导出 Ford-Fulkerson 算法背后的直觉和最大流-最小割定理,并将它推广成网络流大家熟悉的线性规划形式。