当前位置：首页 > news >正文

ZOJ-3987 Numbers 2017CCPC秦皇岛站G题 (二进制乱搞、贪心)

news 来源：原创 2024/5/19 1:10:06

题意：

给一个数n和一个数m，让你将n这个数分成m个数(相加为n)，且这m个数的or值最小。输出该或值。(n <= 1e1000, m <= 1e100)

思路：

由于让我们输出最小的或值，那么我们不必关心分的过程，直接去构造这个或值就好。因为要求分成m份，我们可以看成n是由m个不同二进制位1组成的。所以首先通过sum不断的从0位向高位加m*2^k次方，直到sum大于等于n停止，然后就可以开始从这个位向低位去构造。对于当前位k，由于是从高位到低位，所以我们肯定更不想选择较高位的1，更想让较低位的1来贡献给n这个数，所以如果从k-1位到0位所有的位都选择m个都不能构造出大于当前n所需要贡献的剩余数值，那么表示必然要选择若干个这第k位的1，而由于我们最终要求得或值，既然必须得用这第k位的贡献，那么我们就让它贡献尽可能多的贡献，从而减少后续所需的贡献。依此贪心下去，必定能构造出n，从而也能求出最终的或值。

复杂度为O(n的二进制位数)，由于数较大，只能java大数写了。

代码：

import java.math.BigInteger;
import java.util.Scanner;

public class Main 
{
	public static BigInteger two = BigInteger.valueOf(2);
	public static BigInteger one = BigInteger.ONE;
	public static BigInteger zero = BigInteger.ZERO;
	public static BigInteger n, m;
	public static BigInteger bas[] = new BigInteger[4005];
	public static void init()
	{
		bas[0] = one;
		for(int i = 1; i <= 4000; ++i)
		bas[i] = bas[i-1].multiply(two);
	}
	public static void work()
	{
		BigInteger sum = zero, tmp = n, ans = zero;
		int up = 0;
		for(int i = 0; sum.compareTo(n) < 0; ++i)
		{
			sum = sum.add(m.multiply(bas[i]));
			up = i;
		}
		for(int i = up; i >= 0; --i)
		{
			BigInteger t = bas[i].subtract(one);
			if(t.multiply(m).compareTo(tmp) >= 0) continue;
			BigInteger k = tmp.divide(bas[i]);
			k = k.min(m);
			tmp = tmp.subtract(bas[i].multiply(k));
			ans = ans.add(bas[i]);
		}
		System.out.println(ans);
	}
	public static void main(String[] args) 
	{
		// TODO Auto-generated method stub
		init();
		Scanner cin = new Scanner(System.in);
		int t = cin.nextInt();
		for(int _ = 1; _ <= t; ++_)
		{
			n = cin.nextBigInteger();
			m = cin.nextBigInteger();
			work();
		}
	}
}

继续加油~