FallenLeaf's Blog

斐波那契数列与黄金分割比的关系 前言 众所周知，斐波那契数列的递推公式为： fi={0i=01i=1fi−1+fi−2i≥2f_i = \begin{cases} 0 & i=0 \\ 1 & i = 1 \\ f_{i-1}+f_{i-2} & i \ge 2 \end{cases} fi​=⎩⎨⎧​01fi−1​+fi−2​​i=0i=1i≥2​ 为什么会把斐波那契数列与黄金分割比联系再一起呢？其实和斐波那契的通项公式有关。 斐波那契数列的通项公式 我们考虑使用生成函数推导斐波那契数列的通项公式（别问我为什么，问就是博客正好写了，搬运一下）。 关于生成函数 生成函数是指以某个序列为系数的多项式，其形式为： F(x)=∑i=0aixiF(x) = \sum_{i=0} a_i x^i F(x)=i=0∑​ai​xi 其中 xxx 的存在并没有什么意义，所以又被称为形式幂级函数 我们定义斐波那契数列的生成函数 F(x)F(x)F(x) 为： F(x)=∑i≥0fixiF(x) = \sum_{i \ge 0} f_i x^i F(x)=i≥0∑​fi​...

Content：交互、通信、提交答案题 Date：2025.8.8 题目 CodeForces-P1672E notepad.exe 题目大意 交互题。 有 nnn 个长度分别为 lil_ili​ 的单词，要求将这些单词排放在一个记事本当中，每两个单词之间需要空格（换行不需要）。你最多可以询问 n+30n+30n+30 次，每次可以询问一个宽度 www，裁判会告诉你至少需要高度为 hhh 的记事本才可以放下所有的单词，求 min⁡{hw}\min\{ hw \}min{hw}。 思路 考虑先用 30 次找出将所有单词放在一行所需的最少宽度 w0w_0w0​，然后对于每一个 1≤i≤n1 \le i \le n1≤i≤n，询问排列成 iii 行需要的最少行数，询问次数正好 n+30n + 30n+30 次。 提交记录：Link CodeForces-1010B Rocket 题目大意 交互题。 你可以问裁判 60 次问题，裁判会根据一个循环节长度为 nnn 的数组回答你的问题：如果 ai=0a_i = 0ai​=0，则第 iii 次回答的是假话；如果 ai=1a_i = 1ai​...

Content：字符串进阶-2 Date：2025.8.7 课堂内容 后缀数组 后缀数组主要指两个数组 sasasa 和 rankrankrank： saisa_isai​ 表示所有后缀中按字典序大小从小到大排序后排名为 iii 的后缀的起始位置。 rankirank_iranki​ 表示以 iii 为起始位置的后缀的排名。 其中这两个数组有如下性质： saranki=ranksai=isa_{rank_i} = rank_{sa_i} = i saranki​​=ranksai​​=i 可以使用倍增 + 基数排序的方式求解 sasasa 和 rankrankrank 数组，复杂度 O(nlog⁡n)O(n \log n)O(nlogn)。 除此之外，还有一个 heightheightheight 数组表示 saisa_isai​ 和 sai−1sa_{i-1}sai−1​ 两个后缀的 LCP (Longest Common Prefix) 的长度。 模版题：Luogu-P10469 后缀数组 提交记录：Link 例题 Luogu-P3809 后缀排序 题目大意 给定一个长...

Content：字符串算法进阶 Date：2025.8.6 Luogu-P13270 最小表示法 题意 给定一个长度为 nnn 的字符串 sss，求 sss 的最小表示法。 思路 首先如果暴力的话，复杂度是 O(n2)O(n^2)O(n2) 的，但是我们发现如果我们当前已经发现了一个最小表示法，我们想要找到一个比这个还小的表示法，那么一定存在一个位置，使得这个位置上的字符不相等，根据这个就可以把复杂度优化到 O(n)O(n)O(n)。 提交记录：Link。 Luogu-P5357 AC自动机 题意 给定一个字符串 sss 和 nnn 个模式串 tit_iti​，求每个模式串在字符串 sss 中的出现次数。 思路 首先我们可以对 sss 建一个 AC 自动机，然后统计每个模式串在这个 AC 自动机的字典树上经过了那些节点，然后打标记。再建出 Fail 树，然后在 Fail 树上对标记求和。 提交记录：Link。 模拟题 - 嗑瓜子 题意 有一个人在嗑 nnn 个瓜子，每次在瓜子中等概率拿出一个，有以下两种情况： 如果拿出的是瓜子，则吃掉，并把壳扔回瓜子中。 如果拿出的是壳，则将...

Content：字符串 Date：2025.8.5 课堂内容 字符串哈希 定义哈希函数 H(s)H(s)H(s): H(s)=∑i=1nbasen−isi mod PH(s) = \sum_{i=1}^n base^{n-i} s_i \bmod P H(s)=i=1∑n​basen−isi​modP 其中 basebasebase 大于字符集大小。这个哈希函数的冲突概率为 1P\frac{1}{P}P1​。 通过这个定义，我们可以通过前缀和处理，得到这个字符串上每个区间的哈希值。 树哈希 （重点） 定义哈希函数 H(u)H(u)H(u)，表示以 uuu 为根节点的子树的哈希值。 H(u)=∑iH(son(u,i))1+∑j<i2×size(son(u,j))+1+2×base2×size(u)−1H(u) = \sum_{i} H(son(u, i))^{1 + \sum_{j<i} 2 \times size(son(u, j))} + 1 + 2 \times base^{2 \times size(u) - 1} H(u)=i∑​H(son(u,i))1+∑...

Content：构造 Date：2025.8.3 课堂内容 完全图匹配构造 描述 对于一个 nnn （n∣2n \mid 2n∣2） 个顶点的完全图，将其分为 n−1n-1n−1 个匹配。 思路 我们将其中一个点提出来，剩下的 n−1n-1n−1 个点形成一个正多边形，然后将提出的那个点放在中心。 对于每一条 “斜率” 相同的边，我们把他们放在一个方案中，然后对这个方案进行旋转，就构造了 n−1n-1n−1 个匹配。 完全图曼哈顿路构造 描述 对于一个包含 nnn 个点的完全图，要求将其分成 ⌊n/2⌋\lfloor n / 2 \rfloor⌊n/2⌋ 条曼哈顿路。 思路 当 n∣2n \mid 2n∣2 时 我们将这些点排成一个正 nnn 边形，然后做如下构造： 还是通过第一个构造方案的旋转得出其他的方案。 当 n∤2n \nmid 2n∤2 时 我们考虑通过上面的构造延伸，构造一个 正 (n−1)(n-1)(n−1) 边形，然后在中间加入一个点，把每一条曼哈顿路的起点和中点和这个点相连，就得到了 nnn 为奇数时的构造。下面是其中一条曼哈顿回路。 后记 ...

Content：欢乐 ACM Date：2025.8.4 内容 休息一天喵o(〃＾▽＾〃)o~

Content：博弈论 Date：2025.8.2 课堂内容 SG 函数 表示当前游戏局面的函数，后手必胜当且仅当 SG 函数为 0。 多个游戏的组合的 SG 函数为每个游戏的 SG 函数的 异或和。 经典模型 取石子游戏 题目描述 有 nnn 堆石子，A、B 轮流取，每次从任意一堆中取出至少一个石子，不能取的输，问谁赢。 解法 一堆大小为 nnn 的 SG 函数为 nnn，根据 SG 函数的性质，可以发现整个游戏的 SG 函数为 ⨂i=1nSGi\displaystyle \bigotimes_{i=1}^n SG_ii=1⨂n​SGi​。 阶梯取石子游戏 题目描述 有 nnn 堆石子放在台阶上，A、B 轮流取，每次从任意一堆中取出至少一个石子，放到下一个台阶上（如果在第 1 个台阶，则扔掉），不能取的输，问谁赢。 思路 可以发现最后的答案之和奇数层的石子有关，所以整个游戏的 SG 函数为所有奇数层 SG 函数的异或和。 树状取石子游戏 题目描述 在一颗大小为 nnn 的树上有 nnn 堆石子，A、B 轮流取，每次从任意一堆中取出至少一个石子，移动到他的父亲节点（如果在 1 ...