平方和球柱：出题人解法——保存分层构造¶
最大数量的证明¶
记 \(C(n)=\lfloor(n+1)^2/2\rfloor-1\) .
上界。 设已经放入了 \(T=C(n)+1=\lfloor(n+1)^2/2\rfloor\) 个球。考察最大的 \(n+1\) 个编号，即 \(T-n,\ldots,T\) .其中任意两个不同编号之和严格大于 \(n^2\) 且严格小于 \((n+1)^2\) ，所以不能相邻。每根柱子的编号从底到顶严格递增，这些大编号在该柱上必然构成连续的顶端部分；若某柱有两个，就会有两个相邻的大编号，产生矛盾。因此需要至少 \(n+1\) 根柱子，上界成立。
达到上界的构造。 一根柱子只放球一。对于奇数 \(n>1\) ，在当前 \(n\) 根柱子上放两层，从顶到底描述如下，局部列编号为 \(j=0,\ldots,n-1\) ：
再在中间 \(n-2\) 根柱子的下方递归放入规模 \(n-2\) 的方案。上下两层相邻和为 \(n^2\) ；第二层与递归部分第一层的相邻和为 \((n-1)^2\) .剩余相邻关系由归纳保证。两层使用最大的 \(2n\) 个编号，因为 \(C(n)-C(n-2)=2n\) ，所有编号不重不漏。
对于偶数 \(n\) ，最上层从左到右为 \(C(n),C(n)-1,\ldots,C(n)-n+1\) ，前 \(n-1\) 根柱子的下方放规模 \(n-1\) 的方案。相接两层的编号和为 \(n^2\) ，并且 \(C(n)-C(n-1)=n\) .故也合法且恰好用尽一到 \(C(n)\) .
所有列从顶到底严格递减，因此逆向按编号从小到大放入，正好遵守原操作时序。构造与上界合起来证明最优数量就是 \(C(n)\) .
程序组织¶
为每根柱子准备一个向量，从顶到底记录编号。初始待写编号为 \(C(N)\) .偶数规模时，先从左到右为每列写入一个递减的编号，随后只保留前 \(N-1\) 列。奇数规模时，先从右到左写入一层，再从左到右写入一层；去掉最外两列后继续。最后中间一列加入球一。
该填充顺序正好实现上面的两层公式。每个编号写入一次，且各列自上而下的先后关系得到保留，最终逐列输出即可。
复杂度、适用范围与来源¶
时间为 \(O(N^2)\) 次整数操作，存储所有球需要 \(O(N^2)\) 空间；按输出字符计需 \(O(N^2\log N)\) 时间。alternative.cpp 可通过完整数据，显式方案也便于检查或供后续处理。首选按列生成将额外空间降至常数。
出题人解法提供容量公式与分层构造，GPT-6 整理证明、向量实现和独立验证。方案经平方和、唯一性、顺序及数量检查；小规模最大容量另与二分图最大匹配比较。性能见记录。