MENU

Category: 笔记

做题笔记 2023.2

CF808G Anthem of Berland

数据范围明示 dp。首先在模式串上跑 kmp,预处理失配指针,dp 时遇到问号就暴力枚举字符集中每个字母,复杂度为 $O(|\Sigma|\cdot|S|\cdot|T|)$,可以卡过。

Read More

广义串并联图方法学习笔记

广义串并联图指不存在同胚于 $K4$ 的子图的图,其中,我们称两个图同胚当且仅当这两个图可由同一个图通过边细分变换得到,边细分指删去一条边,新建一个点,并将新点与原边的两个端点连边。

Read More

2023 笔记

Catalan 数

Catalan 数表示为 $C_n$,有通项 $C_n=\dfrac{\binom{2n}{n}}{n+1}$ 和递推式 $C_n=\sum_{i=1}^nC_{i-1}C_{n-i}$,定义应该使用的是递推式。

Read More

Vieta Jumping

顾名思义,这是一种结合 Vieta Theorem 即韦达定理的解题方式,通常用于数论,在 OI 中好像没啥应用,但是总有些无良出题人把 IMO 或者 TST 改成 OI 题。

Read More