摘要: 題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3682題目大意：給你一個立方體，要求去掉若干個垂直于xy或xz或yz的柱子后，去掉的總立方塊個數。題解：發揮想象力，模擬。1.判斷兩兩相交例子：設柱子的值為(x,y,z)，其中用0表示和該軸平行柱子A：(x1,y1,0)，表示過xy平面的x1,y1點，且垂直于xy平面柱子B：(0,y2,z2)，表示過y...  閱讀全文      摘要: 題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3681題目大意：機器人從F出發，走到G可以充電，走到Y關掉開關，D不能走進，要求把所有開關關掉，且電量最少，并求出該最小電量。題解：不錯的題目，由于發現數據較小1<=n,m<=15，所以可以采用狀態壓縮DP解決。算法分3步：1.預處理，計算F、G、Y兩兩的距離(BFS)2.二分法求解最少電量...  閱讀全文

題目鏈接：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);
                }
            }
        }
    }
}