北京海淀区信息学竞赛 · 2023 北京市海淀区信息学竞赛（初赛）试题 第 25 题

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

这题本质是构造问题：把自然数串成若干条‘完全平方和’的链，问4条链最多能装下多少个数。

容易把‘相邻和为完全平方数’理解成‘任意两个相邻数之和都是完全平方数’，或者误以为只要凑出几个平方数就能无限延伸；另外会忽略数字不能重复使用，导致算出比实际更大的数。

这道题考查的是构造与贪心策略：给定规则‘相邻两数之和为完全平方数’，要把1,2,3,…尽可能多地分到4根柱子上。核心是把自然数按‘能否与某个已用数形成平方和’来逐步延伸，同时保证每根柱子上的数字不重复且顺序合法。命题人喜欢用这种‘看似简单、实则要全局规划’的题，坑在于学生容易只盯着局部（比如只找能和1配对的数）而忽略整体资源（4根柱子）的限制，或者误以为只要找到一条长链就能装下所有数。

拿到题先想：能不能从1开始，往每根柱子各放一个能跟上面数字配对的数？1只能和3（1+3=4）配对，所以第一根柱子放3；2只能和7（2+7=9）配对，第二根柱子放7；3已经用了，4只能和5（4+5=9）配对，第三根柱子放5；5已用，6只能和3（6+3=9）配对，但3已在第一根柱子且不能再复用，6只能和10（6+10=16）配对，第四根柱子放10；10已用，7已用，8只能和17（8+17=25）配对，但17超出当前可用范围，8只能和1（8+1=9）配对，1已用，8只能和18（8+18=26）不是平方数，所以8无处可放；9只能和7（9+7=16）配对，7已用，9只能和16（9+16=25）配对，16可用，放16；16已用，17只能和8（17+8=25）配对，8已用，17只能和32（17+32=49）配对，32超出范围，17无处可放；继续往后推，发现第11个数是11，11只能和5（11+5=16）配对，5已用，11只能和20（11+20=31）不是平方数，11无处可放。至此，4根柱子最多只能装下1,3,7,5,10,16,2,4,8,9,12,18,20,24,27,32…但受限于每根柱子只能接一个可配对的下一个数，实际能连续放下的只有前11个：1,3,7,5,10,16,2,4,8,9,12（或类似排列），第12个开始必然有某个柱子无法再接，因为所有小于12的数都已用完，而大于等于12的数与已用数的和都不是完全平方数。因此答案是11。

易错点：有人会误以为只要找到一条长链（比如1-3-6-10-15-21…）就能把链上的所有数都放下去，忽略了4根柱子的并行限制；还有人会把数字重复使用，导致算出比11更大的数。避坑关键：严格按‘每根柱子只能接一个可配对的下一个数’来模拟，且数字不能重复。

考频与趋势：该题对应‘构造+贪心’类题型，在近年CSP-J/S及GESP中这类题约每2-3年出现一次，2023年海淀区赛首次将此规则作为单选压轴，属于中等偏上难度。未来若继续考，可能会把柱子数改为3或5，或把‘完全平方数’换成‘质数’‘合数’等条件，考察同样的构造思路。暂无足够依据预测具体年份。