关于一个运算优化的问题

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