讨论 / 虫食算
rqnoj用户 2013-10-27 10:01:00
点我顶贴 收藏 删除
高价求思路!
#1 刘载清@2013-10-27 10:00:00
回复 删除
http://wenku.baidu.com/view/5c7142eeaeaad1f346933f

经典的搜索题。最单纯的搜索的时间复杂度为O(n!),是会非常严重的超时的。计算机是很“笨”的,它不会思考,在盲目搜索的过程中,很容易出现这种情况: 计算机在某一位搜索出了一个算式1 + 1 = 3,并且继续搜索。 明显,人眼很容易就看出这是不合法的,但计算机不会。于是,我们想到了第一个剪枝:每次搜索的时候,从最后向前判断是否有不合法的式子。 这一个剪枝非常简单,但是效果却非常的好。因为它剪去了很多不必要的搜索。为了配合这一种剪枝更好的实行,搜索顺序的改变也成为大大提高程序效率的关键:从右往左,按照字母出现顺序搜索,有很大程度上提高了先剪掉废枝的情况,使程序的效率得到大大的提高。 有了以上两个剪枝,程序就已经可以通过大部分测试点了。但是有没有更多的剪枝呢?答案是肯定的。 根据前面的剪枝,我们可以找到类似的几个剪枝: 对于a + b = c的形式,假如: A***?*** + B*?**?** C***???* 其中*代表已知,?代表未知。那么,A + B与C的情况并不能直接确定。但是,假如(A + B) % N与(A + B + 1) % N都不等于C的话,那么这个等式一定是不合法的。因为它只有进位和不进位的两种情况。 同样,我们在一个数组里记录了Used[i]表示一个数字有没有用过,那么,对于某一位A + B = C的等式,如果已经得到了两个数,另一个数还待搜索的时候,我们还可以根据这个加入一个剪枝: 例如A + ? = C的形式, 考虑不进位的情况,则?处为P1 = (C - A + N) % N 假如考虑进位的情况,则?处为P2 = (C - A - 1 + N) % N 假如P1、P2均被使用过,那么这个搜索一定是无效的,可以剪去。 有了以上的剪枝,就可以很轻松地通过所有的测试数据了。当然,还有很多值得思考的剪枝以及其他的思路,例如枚举进位、解方程(但是可能需要枚举)等,在这里就不详细讨论了。

#2 rqnoj用户@2013-10-27 10:01:00
回复 删除
这么快!

这么快!

查看更多回复
提交回复