题目翻译

对于一个序列 \((a_1, a_2, a_3, ···, a_n)\) 进行以下操作：

\[(a_1, a_2, a_3, ···, a_n)→(|a_1 ? a_2 |, |a_2 ? a_3 |, ···, |a_n ? a_1 |) \]

请问这个序列最后会不会变成 \((0, 0, ···, 0)\) 。若没有变成全是 \(0\) 的序列， 则序列必定会经过多轮操作后进入一个循环， 如：

\[(4, 2, 0, 2, 0) → (2, 2, 2, 2, 4) → \]

\[( 0, 0, 0, 2, 2) \]

\[ → (0, 0, 2, 0, 2) → (0, 2, 2, 2, 2) → (2, 0, 0, 0, 2) → (2, 0, 0, 2, 0) → (2, 0, 2, 2, 2) → (2, 2, 0, 0, 0) → (0, 2, 0, 0, 2) → (2, 2, 0, 2, 2) → (0, 2, 2, 0, 0) → (2, 0, 2, 0, 0) → (2, 2, 2, 0, 2) → (0, 0, 2, 2, 0) → (0, 2, 0, 2, 0) → (2, 2, 2, 2, 0) → \]

\[( 0, 0, 0, 2, 2) \]

\[... \]

数据范围：

\(n \leq 15\)

\(a_i \leq 1000\)

思路详解

对于这个序列， 由于没有 \(+\) 运算并且在绝对值下所有值永远非负， 所以最大值一定不会变大。所以就可以论证题目是正确的所以我们就可以发现， 如果一次操作后这个序列的最大值没有变， 那就表明刚才这个序列的其中一个最大值的旁边有个零（\(|a - b| < a(b \neq 0)， |a - 0| = a\)）也就是：\((···, a_{max}, 0, ···)\)或者\((···， 0, a_{max}, ···)\)， 其实这两者是等价的。那如果再来一次操作最大值还是没变， 那么我们就可以知道要么是上次操作将 \(a_{max}\) 又减成了 \(0\) , 要么就是 \(0\) 没有变或 \(a_{max}\) 旁边还有一个 \(0\)， 也就是还是保持着存在最大值的旁边有 \(0\) 。

以此类推， 就可以发现， 如果不管怎样操作， 最大值都不变的话， 那只能是这个序列有且仅有 \(a_{max}\) 和 \(0\) 。就算运气再差， 我们也可以在这种情况下用暴力， 跑最多 \(2^n\) 次跑出全为 \(0\) 或者重复。 而如果不是这种序列， 根据刚才的扩展方式， 我们每次最大值不变都意味着又有一位的值是 \(a_{max}\) 或 \(0\) ， 那也就是说， 过了最多 \(n\) 次后， 这种序列就会变成有且仅有 \(a_{max}\) 和 \(0\) 的序列或最大值减小。

所以， 按照这样推理， 我们运气最差也就是最大值从 \(1000\) 一直降到 \(1\) 后开始 \(0\) 和 \(a_{max}\) 。就算是这样， 我们暴力的时间复杂度依然只有 \(O(n(2^n + na_{max}))\) ，也就是 \(O(716520)\) (???, 什么神奇的数， 这真的不是我故意的)。这东西是不可能超时的。 而且这只是最劣解， 实际不可能出现这种情况， 也就是说实际操作比算出来的还要快得多， 所以， 这道题根本就不用想复杂的算法， 只要细心读题， 认真看数据范围， 就可以发现这是一道暴力可以解决的题目。

吐槽

这道题是在讲 vector 的时候的例题， 可我真的没看出来怎么用 vector 。 也没办法， 强加上去也没有意义， 所以打这道题时就直接用的数组。 不过本着学了就必须用的原则， 打代码的时候还是打一打 vector 吧。

关于代码和这道题

因为这道题的核心就是推理时间复杂度为什么合理， 剩下的实现就只是一个暴力的空壳了。 所以， 如果连这种已经将操作过程清清楚楚地打在题目上了的暴力都不自己手打还要来抄， 还要来复制粘贴， 那就太没有意义了。所以说， 就没有放代码了。

还有关于这道题， 肯定很多人都是直接看到这个数据很小， 就直接打暴力就过了， 实际上并没有弄清楚原理。 如果你只是为了练个码力， 我也没有什么好说的， 但如果你真的想要在思维上的提升， 我觉得这个时间复杂度的推理还是很有必要的。 不过有一说一， 如果你是在一场关键的比赛上这样做的话...， 我只能送你一句话：“天作孽， 尤可恕。 自作孽， 不可活。”