众所周知，网络流24题不需要网络流（doge）。
Statement
有 (n) 根柱子，依次放入编号为 $1,2,3,cdots $ 的球。每次只能在顶端放，且同一根中任何两个相邻球的编号之和为完全平方数。
求最多能放多少个球。
Solution
(color{black}{小}color{red}{卷猫}) 曰：可以枚举答案转化为判定性问题。
那么就二分最多能放的个数，然后对于所有 (i+j=k^2(i<j)) 的东西连边，跑最小路径覆盖即可。
但是！这道题还有更为优美的性质：贪心。也就是在已有的柱子上，能放就放，放不了新开，这样就是最优解。
这篇博客 给出了对于贪心正确性的证明，首先得到贪心的答案是
如果最终答案比 (f(n)) 大，那么至少放了 (f(n)+1) 个球。
当 (nequiv 1(mod 2)) 时，即 ((n^2-1)/2+n+1) 个。（另一种同理）
在 (1sim (n^2-1)/2+n+1) 个数中，最后 (n+1) 个数最大和为 (n^2+2n<(n+1)^2) ，最小和为 (n^2+2>n^2) ，所以这 (n+1) 个数必定属于 (n+1) 个柱子，而不可能在 (n) 个柱子中放下。于是贪心的答案就一定正确。
但是博客并没有给出 (f(n)) 的通项式证明。
1 3 6 10 15 21 28 36 45 55
2 7 9 16 20 29 35 46 54
4 5 11 14 22 27 37 44 56
8 17 19 30 34 47 53
12 13 23 26 38 43 57
18 31 33 48 52
24 25 39 42 58
32 49 51
40 41 59
50
观察上面 (n=10) 的情况，不妨设第 (i) 个柱子最底下的数为 (g[i]) ，根据贪心实现和上面的式子，等价于证明 (g[i]=lfloor i^2/2 floor) （当 (i>2) 时）（事实上，这是数列 A007590 ）。那么我们需要证明的就是 (lfloor (n-1)^2/2 floor+1sim lfloor n^2/2 floor-1) 之间的数可以被 (n-1) 个柱子放下，而 (lfloor n^2/2 floor) 不行。不妨增设一个额外条件：在放上这 (n) 个数之前，(n-1) 个柱子顶端的数都是当前放好的最大的 (n-1) 个数。
假设这个结论对 (n-1) 成立。考虑 (n) 。
如果 (n) 为偶数，注意到有 (lfloor (n-1)^2/2 floor +1+lfloor (n-1)^2/2 floor=(n-1)^2) ，那么 (lfloor (n-1)^2/2 floor +1sim lfloor n^2/r floor -1) 的任何一个数都能和顶端的 (n-1) 个数配对，但 (lfloor n^2/2 floor) 不能和其中任何一个配对。这样的情形对于偶数 (n) 显然成立。
如果 (n) 为奇数，有 (lfloor (n-1)^2/2 floor +1+lfloor (n-1)^2/2 floor-1=(n-1)^2) ，那么 (lfloor (n-1)^2/2 floor +1sim lfloor n^2-1 floor) 都能和 (lfloor (n-2)^2/2 floor+1sim lfloor (n-1)^2/2 floor-1) 配对，此时上一组剩下的 (lfloor (n-1)/2 floor) 和当前剩下的 (lfloor n^2/2 floor) （也就是新的柱子的顶端）分别是顶端的数中的最小、最大值，并且依然满足顶端的数是最大的 (n) 个数。
根据归纳假设，结论对任意 (n) 都成立。