第四题 - 可分数列
题目链接跳转:点击跳转
题目很简单,但需要仔细想一会儿才行。这道题的解决思路就是 找规律!没错,就是找一下规律就好了。我们只需要关注如何将这 4N+24N + 24N+2 个数列在去掉两个元素后可以被平均分成 NNN 个等差数列。
通过手动模拟的方式,注意到我们只需要把这些数字竖着排列就可以解决问题。另每一列有四个元素,但其中有两列有五个元素(代表 4N+24N + 24N+2 的 +2+2+2 部分),共有 NNN 列。例如数列 [1,3,5,7,9,11,13,15,17,19,21,23,25,27][1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27][1,3,5,7,9,11,13,15,17,19,21,23,25,27]。竖着排列之后就是这个样子的:
可以看到这些元素构成了三个等差数列,且两个等差数列的长度为 555。那么对于长度为 444 的等差数列我们完全可以不用管,直接输出就好了。而对于这两个长度为 555 的等差数列,我们考虑从这两个等差数列中各删除一个数字来构成新的等差数列。综合来看,我们发现删除元素 333 和 252525 后,新的两个等差数列依旧满足题目限定的条件。
再多列举几个例子,发现规律也是相通的。那么因此我们可以得出结论,对于任意一个长度为 4N+24N + 24N+2 的等差数列,只需要删除这个等差数列的第 222 项和第 4N+14N + 14N+1 项,剩下的 4N4N4N 个元素一定可以组成 NNN 个长度为 444 的等差数列。
> 关于本题的更多信息,可以阅读 アイドル 老师的题解作为补充:链接跳转。
找到规律后代码就很好写了,本题的 AC 代码如下: