【LibreOJ6003】【网络流24题】魔术球问题 的通项公式与线性解法
假设有 n 根柱子,现要按下述规则在这n 根柱子中依次放入编号为1,2,3,4,⋯的球。
- 每次只能在某根柱子的最上面放球。
- 在同一根柱子中,任何 2 个相邻球的编号之和为完全平方数。
试设计一个算法,计算出在 n 根柱子上最多能放多少个球。
这道题其实是有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