CSP-S 提高级 · CSP 2023 提高级第一轮 第 4 题

假设有 $n$ 根柱子，需要按照以下规则依次放置编号为 $1,2,3,\cdots$ 的圆环：每根柱子的底 部固定，顶部可以放入圆环；每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有 $4$ 根柱子时，最多可以放置（）个圆环

这是 2023 年 CSP 提高组的一道经典题。规则：n 根柱子，依次放置编号 1,2,3... 的圆环，要求任何两个相邻（上下相邻）圆环的编号之和为完全平方数。问 4 根柱子时最多能放多少个。

构建图论模型：将每个编号看作一个节点，若 i+j 是完全平方数则连边。问题转化为在图中找一条最长的路径，但受限于只有 4 根柱子（每条路径顶多 4 条分支）。

实际模拟最优放置可得结果为 11 个圆环。

这题容易觉得答案很小（7 或 9），但实际上可以通过巧妙的排列达到 11。关键在于合理分配圆环到各柱子，使得相邻和总是平方数。直接模拟很难，需要找到平方和配对规律。

考察知识点： 构造 — 完全平方数配对

思路分析：

要求相邻编号之和为完全平方数。可能的完全平方数有：4, 9, 16, 25, 36, ...

对于编号 i，它能配对的 j 满足 i+j = k²，即 j = k² - i。

比如编号 1 可以和 3(4-1)、8(9-1)、15(16-1)... 等放在同一根柱子的相邻位置。

此题是 2023 年 CSP-S 的经典构造题，通过构造最优放置方案，4 根柱子最多可放 11 个圆环。

技巧： 这种"相邻和为完全平方数"的构造题，核心是列出各数可能的平方和配对，然后尝试最长路径。对于竞赛题，记住常用的小规模结论——4 根柱子=11，3 根柱子=7 等。