1 Little Nikita

题目描述：

我以另一种方式描述一下题目。你共有 $n$ 次机会，每次机会你可以进行 $+1$ 操作或者是 $-1$ 操作。请问 $n$ 次操作之后能否得到数字 $m$ 。

数据约束：

$1 \le n, m \le 100$

解题思路：

初中学习的二元一次方程组，有正整数解就可以。

复杂度：$O(1)$ 。

2 Binary Colouring

题目描述：

给定一个数 $x$ ，生成一个由 -1 和 0 和 1 构成数组 $A$ 。数组 $A$ 的要求如下：

• $x = \sum_{i = 0}^{n – 1} a_i \times 2^i$
• $\forall i \in [0, n – 2] \rightarrow ai = 0 \or a{i+1} = 0$

数据约束：

$1 \le x \le 2^{30}$

解题思路：

很明显，第一条约束其实就是一个数的二进制表示法（不考虑 -1）。所有，先吧 $x$ 的二进制表示数组给求出来。

那么，第二跳约束就是数组中不能有连续的非零数出现。对于一个数的二进制表示来说，就是不能有连续的 1 出现。那么问题转化为，怎么对连续的 1 进行处理？

我们考虑一下二进制序列 ...01110... ，右侧为低位。如果我们对示例中最右侧的 1 进行 +1 操作，则会得到 ...10000... ，连续的 1 就消除了。又因为我们加了一个 1，所以我们也需要进行减 1 操作，即 ...100(-1)0... 。此时，满足了题目要求。

那么解法就是，从 $x$ 的二进制数最低位开始扫描，若遇到连续的 1 ，就进行上述操作，直到没有连续的 1 为止。

复杂度：时间复杂度 $O(\log x)$ ，空间复杂度：$O(\log x)$ 。

3 Nikita and LCM

题目描述：

一个长度为 $n$ 的数组 $A$ ，我们规定特殊子数组为：该数组是 $A$ 的子数组，且该数组的最小公倍数未在数组 $A$ 中出现。

求数组 $A$ 中符合要求的特殊子数组的最长长度。

数据约束：

$1 \le n \le 2000$ ，$1 \le a_i \le 10^9$

解题思路：

开始没有思路，往动态规划想了。受了一点题解的启发，主要是这个发现：数组 $A$ 的最小公倍数的大于等于数组的最大值。

如果数组 $A$ 的最小公倍数大于了数组的最大值，则答案就是 $n$ 。否则，数组中所有数字都是数组最大值的因数。那么，我们遍历最大值的每一个因数 $d$ ，当 $d$ 不存在与数组 $A$ 中时，寻找数组 $A$ 中所有为 $d$ 的因数的数组成一个数组。如果得到的新数组的最小公倍数刚好等于 $d$ ，这个数组就是合法的。最后答案就是所有合法数组的长度的最大值。

复杂度：时间复杂度 $O(\sqrt{C} + d(C)^2 \times \log C)$ ，空间复杂度 $O(n)$ 。