这个题目做得好辛苦。题目大意是给三个算术表达式,前两个相加等于第三个,每位数都用字母代替,问最后字母对应的数是多少。数据范围n <= 26。由于进位不确定,因此需要枚举进位,再用高斯消元求解。我报着试一试的态度敲了一个2 ^ n * n ^ 3的程序上去,果然超时了。不知道应该如何优化,到网上看了一下,因为每次枚举的都是常数,因此可以先把每个未知数用常量表示出来,这样每次枚举回带求解的复杂度就降到了O(n ^ 2)。感觉这种做法很巧妙,不过实现的时候出了很多问题,搞了一下午才搞定- -!
首先需要保存对于每个变量,它对应的每个常数的系数是多少。开始的时候我列方程的方向想错了,相当成模n域的方程组来求解。结果写了很久之后发现因为n不一定是素数,所以求解的时候解可能有多个,这样的话就比较复杂了。后来一怒之下索性当成实数域来求解,重新列了方程,这样解就是唯一的了,但是中间运算全是浮点数,很担心精度问题,交上去居然过了。
这个题目加速消元的思想还是很值得借鉴的,高斯消元的优化问题不多,但是感觉都挺有意思,就像用弦图加速高斯消元。根据方程的不同特点来选择合适的优化方法很重要啊。
posted on 2009-06-10 21:49
sdfond 阅读(213)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm - Ad Hoc