posts - 11, comments - 2, trackbacks - 0, articles - 0

Waterloo local 1999.10.02

Posted on 2009-02-10 13:19 hello_world 阅读(1112) 评论(2)  编辑 收藏 引用
Waterloo local 1999.10.02
题目分类
 Mine Sweeper  简单题
 Choose and divide  预处理,精度很重要
   
   
Origami 递规,求点的轴对称点

Choose and divide :
求组合数C(p, q) / C(r, s)的值(精确到小数点后五位,结果小于10^7)p, q, r, s 都小于10000

这个表达式中无非是1~10000这个范围内的数乘乘除除,所以我们可以开一个board[10000],board[i] 记录乘了多少个i, 或者除了多少个i(用负数表示除)
问题在于处理精度上,这道题我认为他精度卡的很紧,如果对于board从小到大的顺序计算,精度上会出问题,必须从大到小算
为什么从大到小计算精度更高呢? 我仍然没搞懂
我一开始的想法是用对数做,这样乘变成加, 除变成减,时间上提高了效率,但只能够在4位小数的意义上和测试数据相同,5位小数就wa了

Origami :
将一张纸对折 n ( n<=8 )次, 问你某个点 p 上重叠了多少次
这道题精度不是什么问题,我的想法是递规找 p 的对称点, 有多少个有意义的对称点,就重叠了多少次,注意一下细节, 这道题目给我最大的提示是,做题目先打好腹稿,完全有把握再动手

Feedback

# re: Waterloo local 1999.10.02  回复  更多评论   

2009-02-11 15:43 by 秋风
Origami :
将一张纸对折 n ( n<=8 )次, 问你某个点 p 上重叠了多少次
这道题精度不是什么问题,我的想法是递规找 p 的对称点, 有多少个有意义的对称点,就重叠了多少次,注意一下细节, 这道题目给我最大的提示是,做题目先打好腹稿,完全有把握再动手


直接求折叠后分成了几块 再判断一下是否在折线上应该就可以了吧?

# re: Waterloo local 1999.10.02  回复  更多评论   

2009-02-11 17:55 by hello_world
@秋风
但直接求不好求,你是直接求的吗?可不可以说详细点

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