题目名称	396. [网络流24题]魔术球问题（简化版）
输入输出	`balla.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	sywgz 于2009-11-02加入
开放分组	全部用户
提交状态
分类标签	最值子图网络流数学贪心二分图二分法
	分享题解

通过：406，提交：873，通过率：46.51%
Marvolo	100	0.000 s	0.00 MiB	C++
YGOI_真神名曰驴蛋蛋	100	0.000 s	0.00 MiB	C++
rewine	100	0.000 s	0.00 MiB	C++
AAAAAAAAAA	100	0.000 s	0.00 MiB	C++
hee	100	0.000 s	0.00 MiB	C++
LCWhiStLe	100	0.000 s	0.00 MiB	C++
LuciFer_T-J	100	0.000 s	0.17 MiB	Pascal
Satoshi	100	0.000 s	0.31 MiB	C++
夜の死	100	0.001 s	0.17 MiB	Pascal
sora	100	0.001 s	0.17 MiB	Pascal

关于魔术球问题（简化版）的近10条评论(全部评论)
一测，wa3点，静态debug半天，无果去看别人代码，诶呀他们怎么都是因为开小了啊...我数组开了2e5... 继续静态debug...实在找不到哪里错了.... 然后。。。发现我完全平方数的表只打到了1600qwq CSU_Turkey 2017-12-28 20:08 22楼
不开优化开关反而ac 开了反而超时。。。不太明白为什么 nonamenotitle 2017-03-22 22:23 21楼
老人视力。。文件balla,in与balla.in都打错。。。再见 2017-02-10 16:45 20楼
回复 @L_in : 你们就不会把边和点往死里开么...... AntiLeaf 2017-01-07 17:29 19楼
为啥现在数组越界不E了差评！半汪 2017-01-07 16:54 18楼
在Linux下如果不强转貌似不会转，然后就WTE了 Go灬Fire 2017-01-03 16:05 17楼
半天找规律的结果.. 突然发现黑书上有公式！ for(i=2;i<=n2;i++) { ans[cnt]=ans[cnt-1]+i2;cnt++; ans[cnt]=ans[cnt-1]+i*2;cnt++; } Hakurou! 2016-09-13 20:11 16楼
数组一直在开小... _Itachi 2016-09-12 09:58 15楼
queue太慢…… TenderRun 2016-07-20 17:52 14楼
从小到大枚举可以放的球数，需要的柱子数=最小路径覆盖数，求最大可行解边的估算：$I,j\leq 1600$，$I+j$是完全平方数，这样的无序点对个数。 $\sum_{I是完全平方数}\frac{i}{2}=\frac{n(n+1)(2n+1)}{2*2}$ Rapiz 2016-07-07 17:34 13楼

396. [网络流24题]魔术球问题（简化版）

★★☆ 输入文件：balla.in 输出文件：balla.out 简单对比
时间限制：1 s 内存限制：128 MiB

问题描述：
假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为 1，2，3，4......的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可
放11个球。
´编程任务：
对于给定的n，计算在 n根柱子上最多能放多少个球。

´数据输入：
文件第1 行有 1个正整数n，表示柱子数。
´结果输出:
文件的第一行是球数。

数据规模

n<=60 保证答案小于1600

输入文件示例

输出文件示例

方案如下

1 8
2 7 9
3 6 10
4 5 11

每一行表示一个柱子上的球

本题原版