首页 > 其他 > 详细

bzoj2656

时间:2016-07-10 13:58:34      阅读:235      评论:0      收藏:0      [点我收藏+]

题目链接:传送门

题目大意:已知 a0=0;a1=1; n为偶数 an=a(n/2);n为基数 an=a(n/2)+a(n/2+1);

题目思路:因为n过大,所以要用java高精度,还有最多20组数据,所以记忆化搜索一下

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    public static HashMap<BigInteger, BigInteger> M=new HashMap<BigInteger,BigInteger>();
    public static Scanner in=new Scanner(new BufferedInputStream(System.in));
    public static void main(String args[]){
        M.put(BigInteger.valueOf(0),BigInteger.valueOf(0));
        M.put(BigInteger.valueOf(1),BigInteger.valueOf(1));
        solve();
        in.close();
    }
    public static void solve(){
        int group=in.nextInt();
        while(group--!=0){
            BigInteger num1=in.nextBigInteger();
            BigInteger ans=dfs(num1);
            System.out.println(ans);
        }
    }
    public static BigInteger dfs(BigInteger a){
        if(M.containsKey(a)) return M.get(a);
        BigInteger ta=a;
        if(a.mod(BigInteger.valueOf(2)).compareTo(BigInteger.valueOf(1))==0){
            a=a.divide(BigInteger.valueOf(2));
            BigInteger temp1=dfs(a);
            a=a.add(BigInteger.valueOf(1));
            BigInteger temp2=dfs(a);
            temp1=temp1.add(temp2);
            M.put(ta,temp1);
            return temp1;
        }
        else{
            a=a.divide(BigInteger.valueOf(2));
            BigInteger tt=dfs(a);
            M.put(ta,tt);
            return tt;
        }
    }
}

 

bzoj2656

原文:http://www.cnblogs.com/Kurokey/p/5657535.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!