【LibreOJ6003】【网络流24题】魔术球问题 的通项公式与线性解法

xiaoxiao2021-02-28  12

假设有 n 根柱子,现要按下述规则在这n 根柱子中依次放入编号为1,2,3,4,⋯的球。

每次只能在某根柱子的最上面放球。在同一根柱子中,任何 2 个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在 n 根柱子上最多能放多少个球。

这道题有贪心做法,由于答案的数量是O(n^2)所以,复杂度为O(n^3),至于贪心做法的正确性,可以通过证明方案的唯一性来证明,这里不再研究贪心算法。

这道题其实是有O(1)出答案,O(答案数量)出方案的做法的。

附上前10个点经过整理后的方案

[1] 1 [2] 3  1  2

[3] 5  4  6  3  1  7  2 [4]11  5  4 10  6  3  1  9  7  2  8 [5]13 12 14 11  5  4 15 10  6  3  1 16  9  7  2 17  8 [6]23 13 12 22 14 11  5  4 21 15 10  6  3  1 20 16  9  7  2 19 17  8 18 [7]25 24 26 23 13 12 27 22 14 11  5  4 28 21 15 10  6  3  1 29 20 16  9  7  2 30 19 17  8 31 18 [8]39 25 24 38 26 23 13 12 37 27 22 14 11  5  4 36 28 21 15 10  6  3  1 35 29 20 16  9  7  2 34 30 19 17  8 33 31 18 32 [9]41 40 42 39 25 24 43 38 26 23 13 12 44 37 27 22 14 11  5  4 45 36 28 21 15 10  6  3  1 46 35 29 20 16  9  7  2 47 34 30 19 17  8 48 33 31 18 49 32 [10]59 41 40 58 42 39 25 24 57 43 38 26 23 13 12 56 44 37 27 22 14 11  5  4 55 45 36 28 21 15 10  6  3  1 54 46 35 29 20 16  9  7  2 53 47 34 30 19 17  8 52 48 33 31 18 51 49 32 50

转载请注明原文地址: https://www.6miu.com/read-2400191.html

最新回复(0)