关于一个运算优化的问题

liangbch

我之前提交的代码有bug，没有通过ACM评测系统。下面贴一个通过ACM评测的版本。
提交时间2009- 3-12  21:53:14  ID：2492367。（直接从ACM网站粘贴，没有任何改动），请大家不要将这份代码提交的ACM在线评测系统。否则将会出来好多好多个0.4秒的版本，这有违公平原则。

游客，本帖隐藏的内容需要积分高于 200 才可浏览，您当前积分为 0

[ 本帖最后由 liangbch 于 2009-3-19 14:05 编辑 ]

无心人

我有另外一个思路

想做一个预先表
存储log值

无心人

Haskell生成的表
[(0,0,0),(1,0,0),(2,0,0),(3,0,1),(4,1,0),(5,1,0),(6,1,2),(7,2,0),(8,2,0),(9,2,3)
,(10,3,0),(11,3,0),(12,3,0),(13,3,4),(14,4,0),(15,4,0),(16,4,5),(17,5,0),(18,5,0
),(19,5,6),(20,6,0),(21,6,0),(22,6,0),(23,6,7),(24,7,0),(25,7,0),(26,7,8),(27,8,
0),(28,8,0),(29,8,9),(30,9,0),(31,9,0),(32,9,0),(33,9,10),(34,10,0),(35,10,0),(3
6,10,11),(37,11,0),(38,11,0),(39,11,12),(40,12,0),(41,12,0),(42,12,0),(43,12,13)
,(44,13,0),(45,13,0),(46,13,14),(47,14,0),(48,14,0),(49,14,15),(50,15,0),(51,15,
0),(52,15,0),(53,15,16),(54,16,0),(55,16,0),(56,16,17),(57,17,0),(58,17,0),(59,1
7,18),(60,18,0),(61,18,0),(62,18,0),(63,18,19),(64,19,0),(65,19,0),(66,19,20),(6
7,20,0),(68,20,0),(69,20,21),(70,21,0),(71,21,0),(72,21,0),(73,21,22),(74,22,0),
(75,22,0),(76,22,23),(77,23,0),(78,23,0),(79,23,24),(80,24,0),(81,24,0),(82,24,0
),(83,24,25),(84,25,0),(85,25,0),(86,25,26),(87,26,0),(88,26,0),(89,26,27),(90,2
7,0),(91,27,0),(92,27,0),(93,27,28),(94,28,0),(95,28,0),(96,28,29),(97,29,0),(98
,29,0),(99,29,30),(100,30,0),(101,30,0),(102,30,31),(103,31,0),(104,31,0),(105,3
1,0),(106,31,32),(107,32,0),(108,32,0),(109,32,33),(110,33,0),(111,33,0),(112,33
,34),(113,34,0),(114,34,0),(115,34,0),(116,34,35),(117,35,0),(118,35,0),(119,35,
36),(120,36,0),(121,36,0),(122,36,37),(123,37,0),(124,37,0),(125,37,0),(126,37,3
8),(127,38,0)]

第一项是二进制最高位， 第二项对应log_10值，第三项非0表示需要和10^n比较的n

无心人

[(0,0,0,1),(0,0,0,10),(0,0,0,100),(0,0,0,1000),(0,0,0,10000),(0,0,0,100000),(0,0
,0,1000000),(0,0,0,10000000),(0,0,0,100000000),(0,0,0,1000000000),(0,0,2,1410065
408),(0,0,23,1215752192),(0,0,232,3567587328),(0,0,2328,1316134912),(0,0,23283,2
76447232),(0,0,232830,2764472320),(0,0,2328306,1874919424),(0,0,23283064,1569325
056),(0,0,232830643,2808348672),(0,0,2328306436,2313682944),(0,5,1808227885,1661
992960),(0,54,902409669,3735027712),(0,542,434162106,2990538752),(0,5421,4665377
0,4135583744),(0,54210,466537709,2701131776),(0,542101,370409800,1241513984),(0,
5421010,3704098002,3825205248),(0,54210108,2681241660,3892314112),(0,542101086,1
042612833,268435456),(1,1126043566,1836193738,2684354560),(12,2670501072,1182068
202,1073741824),(126,935206946,3230747430,2147483648),(1262,762134875,2242703233
,0),(12621,3326381459,952195850,0),(126217,3199043520,932023908,0),(1262177,1925
664130,730304488,0),(12621774,2076772117,3008077584,0),(126217744,3587851993,160
04768,0),(1262177448,1518781562,160047680,0)]

10方幂表

无心人

[(1,0,0,0),(10,0,0,0),(100,0,0,0),(1000,0,0,0),(10000,0,0,0),(100000,0,0,0),(100
0000,0,0,0),(10000000,0,0,0),(100000000,0,0,0),(1000000000,0,0,0),(1410065408,2,
0,0),(1215752192,23,0,0),(3567587328,232,0,0),(1316134912,2328,0,0),(276447232,2
3283,0,0),(2764472320,232830,0,0),(1874919424,2328306,0,0),(1569325056,23283064,
0,0),(2808348672,232830643,0,0),(2313682944,2328306436,0,0),(1661992960,18082278
85,5,0),(3735027712,902409669,54,0),(2990538752,434162106,542,0),(4135583744,466
53770,5421,0),(2701131776,466537709,54210,0),(1241513984,370409800,542101,0),(38
25205248,3704098002,5421010,0),(3892314112,2681241660,54210108,0),(268435456,104
2612833,542101086,0),(2684354560,1836193738,1126043566,1),(1073741824,1182068202
,2670501072,12),(2147483648,3230747430,935206946,126),(0,2242703233,762134875,12
62),(0,952195850,3326381459,12621),(0,932023908,3199043520,126217),(0,730304488,
1925664130,1262177),(0,3008077584,2076772117,12621774),(0,16004768,3587851993,12
6217744),(0,160047680,1518781562,1262177448)]

小头方式的10方幂

litaoye

我这里又改了一下,结果算不对了!不过我对进入0.2没什么信心，C#光是处理输入的字符，恐怕都要这么长时间！

我也说不好现在的算法的复杂度是多少，等我通过了测试再跟大家仔细说吧！

litaoye

呵呵，超出我的想象了，现在C#用时是0.156，更加有成就感了！

我觉得我用的可能是一个N*log(n)的算法。先对数组排序，然后不断地将数据按照待计算的位（0或1）分为2组！

组之间的运算，可能直接用乘法就能算！

比如集合A Xor 集合B

我先将A分为A1和A2两组，B分为B1和B2两组，这样求和就成了A1 Xor B1 + A1 Xor B2 + A2 Xor B1 + A2 Xor B2
其中会有2组可以直接用乘法算出结果，另外2组继续递归到更低的位进行计算。

相信如果用C++或汇编来完成这个程序，超过0.062也是有可能的！

litaoye

算了一下0-99999，在我的机器上需要460毫秒。我想我现在应该可以满意了！

如果再想提高效率，恐怕只能在一些计算细节上下功夫了！我去仔细研究一下宝宝的代码！

如果大家需要C#的代码，我就贴上来。

liangbch

我的成绩0.171被楼主的0.156超过了，我又尝试做了一点微小的优化，甚至将C++的代码改成标准C的，依然没有用，仍然是0.171,

litaoye

原帖由 liangbch 于 2009-3-15 12:38 发表
我的成绩0.171被楼主的0.156超过了，我又尝试做了一点微小的优化，甚至将C++的代码改成标准C的，依然没有用，仍然是0.171,

你试试加一个计数，专门处理相同的数，可能就能超过0.171