关于一个运算优化的问题

litaoye · 发表于 2009-3-12 14:00:40

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

是一个ACM的题,地址如下。 http://acm.timus.ru/problem.aspx?space=1&num=1318 大概意思就是给出5000个左右的128位的整数，求：

我也作了不少优化（包括分治），虽然可以过，但似乎同别人的算法似乎还有不小的差距，请高手们帮我想想还有什么好的方法没有！我想用二叉树可能会好一点，但思路还不太清晰。

无心人 · 发表于 2009-3-12 14:46:27

$A_k, A_j$什么关系，可以相等么？首先排序么？我看不懂他的意思

无心人 · 发表于 2009-3-12 14:47:45

论坛有计算$log_10$的代码

litaoye · 发表于 2009-3-12 14:48:07

可以相等,初始是无序的,不过可以排序! 另外忘了说明了,LOG10之后,只保留整数部分就可以!

原帖由 无心人 于 2009-3-12 14:46 发表 $A_k, A_j$什么关系，可以相等么？首先排序么？

无心人 · 发表于 2009-3-12 14:50:42

是$A_k, A_j$遍取所有的可能？即如果有100个，则生成10000个XOR值？？

litaoye · 发表于 2009-3-12 14:53:55

原帖由 无心人 于 2009-3-12 14:50 发表是$A_k, A_j$遍取所有的可能？即如果有100个，则生成10000个XOR值？？

是这个意思!然后取log10的整数部分,都加在一起!

无心人 · 发表于 2009-3-12 14:55:29

按照我目前的理解如果无序，且遍取所有可能是无需排序的只要进行一次遍历就可以了大概1000万次的XOR 然后求$log_10$ 这个是整数算法应该能在1秒左右完成

无心人 · 发表于 2009-3-12 14:57:31

5000 的128位值还不需要用文件操作直接能一次读取到内存然后是个 for (i = 0; i < N - 1; i ++) for (j = i + 1, j < N; j ++) 的两重循环

无心人 · 发表于 2009-3-12 15:00:21

就是测试128位数字的$ log_10$麻烦些不过，用个Cache，加上几个判断就能做好完全的整数运算很快的看论坛有求32位的代码

litaoye · 发表于 2009-3-12 15:04:02

我说一下我现在用的方法吧!先求出10^0 - 10 ^ 38，并分别计算最高位所在的位置。对A数组排个序，然后只需计算A[k]同比A[k]小的数logXor就可以了，最后的结果*2 在计算过程中，先求出5000个数的最高位，并分类，如果最高位m高于10^n,且低于10^n+1，那么这个数同最高位小于m的数进行Xor并取log10后的结果，都是n，因此有些数是可以批量算的（但所占比例不是很大）。基本上就是做了这些优化。

账号		自动登录	找回密码
密码			欢迎注册

[求助] 关于一个运算优化的问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。