首页 > 代码库 > HDU 4919 Exclusive or
HDU 4919 Exclusive or
题意:
求题目中的式子 - -b
思路:
推递推公式 比赛时候队友就说数字上有关系 but没推出来 - -b 题解有过程:
推的过程中最巧妙的就是利用异或的性质 相邻两个数字相当于修改二进制最后两位 不过这样做通过异或出来的结果是相同的
题目中数字太大 用java比较好写 处理递推的问题常用记忆化搜索
代码:
import java.util.*; import java.io.*; import java.math.*; public class Main { public static BigInteger two = BigInteger.valueOf(2); public static BigInteger four = BigInteger.valueOf(4); public static BigInteger six = BigInteger.valueOf(6); public static HashMap<BigInteger, BigInteger> map = new HashMap<BigInteger, BigInteger>(); public static BigInteger F(BigInteger n) { if (map.containsKey(n)) return map.get(n); BigInteger tmp1 = n.divide(two); BigInteger tmp2 = n.mod(two); BigInteger tmp3 = tmp1.subtract(BigInteger.ONE); if (tmp2.compareTo(BigInteger.ONE) == 0) tmp1 = F(tmp1).multiply(four).add(tmp1.multiply(six)); else tmp1 = F(tmp1).multiply(two).add(F(tmp3).multiply(two)) .add(tmp1.multiply(four)).subtract(four); map.put(n, tmp1); return tmp1; } public static void main(String[] args) { Scanner cin = new Scanner(System.in); map.put(BigInteger.ZERO, BigInteger.ZERO); map.put(BigInteger.ONE, BigInteger.ZERO); while (cin.hasNext()) { BigInteger n = cin.nextBigInteger(); System.out.println(F(n)); } cin.close(); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。