posts - 33,  comments - 33,  trackbacks - 0

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3680
题意:给定两数n,m(0< n,m < 10^500),要求用三种操作(-,+,*2)完成从m变换到n
题解:咋眼看还以为是简单水题,http://poj.org/problem?id=3278 就是这题的原始版,
并且这个题目下面还白纸黑字写明(0<N,M<10500),匆忙写个BFS提交,结果RE,其实题目的数据范围
应该是0<N,M<10^500。。。
暴搜行不通,就要有个好点的方法,想了一下想不到,结果看了个解题报告,才知道怎么解决

如果m > n:只有减操作
如果n > m:可以从后往前推算:
设f(x,n)表示数x变换到n需要的步数 f(x,n)
那么如果x为奇数:f(x,n) = f(x/2,n) + 2
如果x为偶数 :f(x,n) = f(x/2,n) + 1
当前答案即为 abs(m-x) + f(x,m)
一直计算直到2*x > m 。
只需要计算x和x+1的步数即可,如何证明?
以下以(x,n,y)表示,其中y = f(x,n)
 分别讨论x和x+1的奇偶性,(x/2,n,y1)和((x+k)/2,n,y2)的大小(作差)
结果发现当k>=2时,y2 > y1。

由于要大数,所以用java比较方便。。。
 

代码:
import java.io.*;
import java.util.*;
import java.math.*;

public class Main 
{    
    
public static Scanner in = new Scanner(System.in);
    
public static BigInteger Abs(BigInteger num)
    
{
        
return num.abs();
    }

    
public static BigInteger Min(BigInteger num1,BigInteger num2)
    
{
        
return num1.min(num2);
    }

    
public static void main(String[] args) 
    
{
        BigInteger n,m;
        
while(true)
        
{
            n 
= in.nextBigInteger();
            m 
= in.nextBigInteger();
            
if((n.compareTo(BigInteger.ZERO) == 0|| (m.compareTo(BigInteger.ZERO) == 0))
            
{
                
break;
            }

            
else
            
{
                
if(m.compareTo(n) > 0)
                
{
                    System.out.println(m.subtract(n));
                }

                
else
                
{
                    BigInteger x1,x2,y1,y2,x;
                    x 
= n;
                    x1 
= BigInteger.ZERO;
                    x2 
= BigInteger.ONE;
                    BigInteger ans 
= n.subtract(m);
                    
while(x.multiply(BigInteger.valueOf(2)).compareTo(m) > 0)
                    
{
                        
//x为偶数
                        if(x.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO) == 0)
                        
{
                            y1 
= Min(x1.add(BigInteger.valueOf(1)),x2.add(BigInteger.valueOf(2)));
                            
//x+1为奇数
                            y2 = Min(x1.add(BigInteger.valueOf(2)),x2.add(BigInteger.valueOf(2)));
                        }

                        
else
                        
{
                            
//x为奇数
                            y1 = Min(x1.add(BigInteger.valueOf(2)),x2.add(BigInteger.valueOf(2)));
                            
//x+1为偶数
                            y2 = Min(x1.add(BigInteger.valueOf(2)),x2.add(BigInteger.valueOf(1)));
                        }


                        x 
= x.divide(BigInteger.valueOf(2));
                        x1 
= y1;
                        x2 
= y2;
                        
//x的步数
                        ans = Min(ans,Abs(x.subtract(m)).add(y1));
                        
//x+1的步数
                        ans = Min(ans,Abs(x.subtract(m).add(BigInteger.ONE)).add(y2));
                    }


                    System.out.println(ans);
                }

            }

        }

    }

}

posted on 2010-11-10 16:47 bennycen 阅读(1039) 评论(3)  编辑 收藏 引用 所属分类: 算法题解

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