algorithm

LC390.消除游戏 Created: January 2, 2022 1:46 PM 声明：我写的文章只是为了只有一个目的———把方法讲清楚、讲通透。 OJ上很少存在某个人原创的方法，大部分只是对已有的方法的重复。 ⚠️长度警告 Brute Force 暴力法 我们先来分析数组手动模拟的不可行性。 注意到 $1 \le n \le 10^9$。假设每个数 16bit，存放所有中间数需要最多 $16 \times 10^9$bit 也就是约 2GB！！。 就算预处理第一轮去除所有奇数，也要1GB。 要知道一般的OJ平台的上限仅仅是MB级别。因此，显然不可行。 我们必须寻求一些数学方法，一个是从数列的角度，一个是从函数的角度。 数列的角度 从题目的描述来看，我们的输入，无论怎么消除，仅仅只是一串等差数列。 回顾等差数列的三要素：1. 首项 $a_1$； 2. 公差 $d$； 3. 项数 $n$； 并有如下公式成立： $$a_n = a_1 + (n-1)\cdot d$$ 因此，就没有必要再存储数列中的每个元素的值了。 如果把输入看作是一个等差数列 $a^0$。e.g. 1, 2, 3, 4 ,5 那么，消除第一轮的产生一个新的等差数列 $a^1$。e.g. 2, 4 那么，消除第二轮的产生一个新的等差数列 $a^2$。e.g. 2 以此类推，消除$turn$轮产生一个新的等差数列 $a^{turn}$。 不难看出，每一轮消除过后存在一下差别： 公差 $d$ 加倍了 首项 $a_1$ 变了 项数 $n$ 变了 于是我们就要探索一下这三者是怎么变的：...