随笔 - 68  文章 - 57  trackbacks - 0
<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

常用链接

留言簿(8)

随笔分类(74)

随笔档案(68)

搜索

  •  

最新评论

阅读排行榜

评论排行榜

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

posted on 2009-06-10 21:49 sdfond 阅读(197) 评论(0)  编辑 收藏 引用 所属分类: Algorithm - Ad Hoc

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理