魔术球问题

发现好像没人来证明贪心啊……那我来写一下它的证明 欲证明：放一个数在已有的柱上（如果可以）总是比新开一个柱更优的 假如已经放了`x1..x2....xu..xv..xw....` 现在我要放`xx` 我有两种策略 在`xu`（`xu`代表可以与`xx`组成完全平方数的数）上放，或者新开一个柱子 即 `x1..x2....xx..xv..xw....` or `x1..x2....xu..xv..xw....xx` 然后再考虑`xx+1` 对于`x1..x2......xv..xw....`，上下两种都是一样的，就不说了 既然`xu`可以与`xx`组成完全平方数，则`xu+xx=a\*a` 可以发现，`xu+1+xx` **不可以放在xu上面**，（为什么呢？倘若可以，即`xu+1+xx==b\*b`，即`1=b\*b-a\*a`，而`b>a>=1……`） 那么，`xx+1`还不如放在`xx`上哩。 如果`xx+1`放在不是`xx`上的地方，则上面一种更优。因为倘若再来个什么`xa`，它大可以再开一个柱子。（有的同学可能发现这里的证明有点不完整，大概说一下，就是考虑`xa`放在`xu`上的所有柱子的形态和新开一个柱子的所有柱子的形态）。 代码很好写啦。（据说$n\leq 60$） ```cpp #include <iostream> #include <cstdio> #include <vector> using namespace std; int n, cnt, ans=1, isa[3205]; vector<int> d[62]; int main(){ for(int i=1; i*i<=3205; i++) isa[i*i] = true; cin>>n; while(1){ for(int i=1; i<=cnt; i++) if(isa[d[i][d[i].size()-1]+ans]){ d[i].push_back(ans); ans++; i = 0; continue; } if(cnt<n) d[++cnt].push_back(ans++); else break; } cout<<ans-1<<endl; for(int i=1; i<=n; i++){ for(int j=0; j<d[i].size(); j++) printf("%d ", d[i][j]); printf("\n"); } return 0; } ```