The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

浙江省赛 F 解题报告

题意:P(x)=x各个数字位的乘积。x<=10^1000,求min{ans|ans>x && P(ans)=P(x)}。

        显然如果x的数字位含有0,分两种情况:

                1):只有一个0,如果0在个位数,那么x+10就是最优解了。如果0不在个位数,则x+1就是最优解。

                2):有2个或2个以上的0,那么x+1就是最优解。

                证明略,很容易看出的。

        接下来就是处理不含0的情况。

        把x的各个数字位分解质因子。只有2,3,5,7这4个素数。

        然后从高位深搜解,这里有加些剪枝。就是在搜索的时候每步都有保证搜到的解>=x。这样的话就会很快的搜到最优解。具体实现就是设一个flag值,flag为真表示当前搜的解>x否则=x。如果flag为真,则改数字位从1开始搜到9,如果flag不为真,则改状态的数字位从x原本的数字位开始搜,只要碰到改状态的数字大于原本的数字位就要改flag为真。这样就可以保证比较快的搜到解了。然后随便在了点杂七杂八的剪枝就差不多了。

        最后还要在判断刚才的搜索有没有找到解,如果没有找到解,那么只剩一种情况了,就是增加一个数字位'1';排序,输出。

        我的搜索已经写的很暴力了,str函数狂用,用时10ms。

        不知道有没有更高效的做法,或者有直接更妙的构造方法呢?

                                                                                                                                                         ——by yayamao

posted on 2010-04-17 20:52 abilitytao 阅读(413) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理