sky3141

题解

/ 注册

全部文章 / 题解（共13篇）

题解 | #汉诺塔#

C. 汉诺塔知识点：递归、递推、取模设表示个圆盘的普通版汉诺塔的最小步数。有递推式 f[0] = 0, f[i] = 2 * f[i-1] + 1。通过数学方法或找规律易得 f[n] = 2^n – 1 假设最大的圆盘在2号柱子上，那么可以分为三步：把别的盘子整齐地叠到1号柱子上...

C++ Java Python3 递归递推

2024-07-01

0 233

题解 | #因数之和#

B. 因数之和知识点：调和级数、前缀和如果一上来就开始打表找规律，那多半是寄了。我们考虑把所有数的因数之和都求出来。记表示的所有因数之和，枚举 ~ 的每个数，把加到所有满足为的倍数的里。分析一下时间复杂度：是经典的调和级数，使用积分可求得复杂度为。然后再开...

C++ Java Python3 调和级数前缀和

2024-07-01

0 256

题解 | #寿命修改#

A. 寿命修改知识点：线段树、摊还分析 meyi 老师锐评：这道题是最一眼的。如果青蛙不会死，这就是道裸的线段树板子题。考虑每个线段树结点维护三个东西：寿命和、活青蛙寿命最小值和活青蛙数量。如果修改操作导致区间内青蛙死亡（通过最小值判断），就暴力递归到叶子结点处理。每次递归到叶子的复杂度为 ...

C++ Java Python3 线段树摊还分析

2024-07-01

1 275