斐波那契数列与黄金分割比的关系
斐波那契数列与黄金分割比的关系 前言 众所周知,斐波那契数列的递推公式为: 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−2i=0i=1i≥2 为什么会把斐波那契数列与黄金分割比联系再一起呢?其实和斐波那契的通项公式有关。 斐波那契数列的通项公式 我们考虑使用生成函数推导斐波那契数列的通项公式(别问我为什么,问就是博客正好写了,搬运一下)。 关于生成函数 生成函数是指以某个序列为系数的多项式,其形式为: F(x)=∑i=0aixiF(x) = \sum_{i=0} a_i x^i F(x)=i=0∑aixi 其中 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...
OI集训 Day23
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...
OI集训 Day22
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(nlogn)O(n \log n)O(nlogn)。 除此之外,还有一个 heightheightheight 数组表示 saisa_isai 和 sai−1sa_{i-1}sai−1 两个后缀的 LCP (Longest Common Prefix) 的长度。 模版题:Luogu-P10469 后缀数组 提交记录:Link 例题 Luogu-P3809 后缀排序 题目大意 给定一个长...
OI集训 Day21
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 个瓜子,每次在瓜子中等概率拿出一个,有以下两种情况: 如果拿出的是瓜子,则吃掉,并把壳扔回瓜子中。 如果拿出的是壳,则将...
OI集训 Day20
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∑nbasen−isimodP 其中 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+∑...
OI集训 Day18
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 为奇数时的构造。下面是其中一条曼哈顿回路。 后记 ...
OI集训 Day19
Content:欢乐 ACM Date:2025.8.4 内容 休息一天喵o(〃^▽^〃)o~
OI集训 Day17
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⨂nSGi。 阶梯取石子游戏 题目描述 有 nnn 堆石子放在台阶上,A、B 轮流取,每次从任意一堆中取出至少一个石子,放到下一个台阶上(如果在第 1 个台阶,则扔掉),不能取的输,问谁赢。 思路 可以发现最后的答案之和奇数层的石子有关,所以整个游戏的 SG 函数为所有奇数层 SG 函数的异或和。 树状取石子游戏 题目描述 在一颗大小为 nnn 的树上有 nnn 堆石子,A、B 轮流取,每次从任意一堆中取出至少一个石子,移动到他的父亲节点(如果在 1 ...



