Yanyan's Wiki 操作系统 (2022)

算法竞赛入门

算法废人的口胡系列


  • 容斥原理与计数 (视频) (JSOI-2022 冬令营)
    • 容斥原理是一类重要的计数工具,它实现了 “化并为交”:将 $|A\cup B\cup C\cup D|$ 这样 “不规则” 的计数问题 (例如凸多边形的并可以任意 “不规则”) 的计数问题改写成子集交 (如 $|A \cap B\cap C|$,凸多边形的交依然是凸多边形) 的线性组合,从而能够解决一大类看起来很 “独特” 的计数问题。这个视频会带大家 “用集合的视角理解计数”,并用 “求线性方程组” 的方法重新理解容斥原理。
  • Sigma 求和:一个“数学编程语言” (视频) (JSOI-2021 夏令营)
    • 求和 ($\Sigma$) 是算法竞赛中普遍使用的运算符——但它与我们平时接触的代数运算 (加减乘除) 不同,更像是一个 “编程语言”。这个视频里介绍如何求和算子的入门和一些常用的技巧,包括一些求和问题 (例如 $\sum_{1 \le k < n} \lfloor\sqrt k\rfloor$) 的求解和 Mobius 函数的使用。
  • 线性代数基础 (视频) (JSOI-2021 夏令营)
    • 还记得我们在中学学 “代数” 之前,在小学学过的 “算术” 吗——对,就是用固定的规则算出一个表达式的值。对于大家可能头疼的 “线性代数”,同样是从 “线性算术” 发展而来的。令人惊奇的是,带着 “线性算术” 去理解线性代数,矩阵、特征值、高斯消元法……都会有新的理解。
  • 生成函数选讲 (视频) (JSOI-2021 冬令营)
    • 把三个熟悉的数学概念:多项式 $ax^2+bx+c$、递推 $f(n)=f(n-1)+f(n-2)$、无限循环小数 $0.\dot{9}$ 结合到一起会发生什么?作为中学生 “高等数学” 的启蒙课,我们探索幂生成函数、指数生成函数、狄利克雷生成函数乘法 (卷积) 的推导和妙用。
  • 最大流/最小割定理 (视频) (JSOI-2020 冬令营)
    • 最大流/最小割定理一直是组合优化里一个理解的难点。在这一课中,我们通过一个更简单的问题:求有向图中的一条路径 (或证明有向图中没有路径),引出割的概念,自然地推导出 Ford-Fulkerson 算法背后的直觉和最大流-最小割定理,并将它推广成网络流大家熟悉的线性规划形式。
Creative Commons License    苏 ICP 备 2020049101 号