ZJU/ZOJ 1331 Perfect Cubes 解题报告

题目大意是求出a<=200的所有a^3=b^3+c^3+d^3的组合，其中b<c<d。

很容易想到暴力的4重循环枚举做法，时限是10s，我估计应该是可以AC的。但次方是递增的，因此很容易想到最后一重循环可以用二分查找代替。具体做法是先预处理出2到200的次方用一个数组记录，然后按递增顺序枚举a、b、c，有一个很显而易见的剪枝是如果算出的d的次方比c的次方要小可以直接break，然后二分查找d的值，如果能够找到就输出这种组合。其实还可以进一步优化，次方和的组合总共只有20100种，算出再后排序就可以改成两重循环+二分查找了，但还要注意处理第一个数相同而第二三个数不同的情况。不过这题的输出数据只有一个，所以有一个最强优化--打表……

2993787 2008-07-21 16:03:27 Accepted 1331 FPC 00:00.09 412K IwfWcf