ZOJ 3987(バイナリ列挙+java大数)
タイトルリンク:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3987
題意:1つの数nと1つの数mをあげて、nという数をmの数に分けて加算して、このmの数のor値が最小になります.
考え方:直接バイナリの角度から考えて、m個数のor値を最小にして、つまりm個数の中で最高位はできるだけ低くすべきで、私達はまず1つのk
(2^k−1)*m>n>(2^(k−1)*mであれば、m個のバイナリ数のうち少なくとも1個の数の最高位がkであることが分かる.今私たちはあるいは演算をするので、この時できるだけ多くの数のk位を1にしなければならないので、答えans+=2^kは、nが0になるまで高位から低位にプッシュします.
コード:
題意:1つの数nと1つの数mをあげて、nという数をmの数に分けて加算して、このmの数のor値が最小になります.
考え方:直接バイナリの角度から考えて、m個数のor値を最小にして、つまりm個数の中で最高位はできるだけ低くすべきで、私達はまず1つのk
(2^k−1)*m>n>(2^(k−1)*mであれば、m個のバイナリ数のうち少なくとも1個の数の最高位がkであることが分かる.今私たちはあるいは演算をするので、この時できるだけ多くの数のk位を1にしなければならないので、答えans+=2^kは、nが0になるまで高位から低位にプッシュします.
コード:
import java.util.*;
import java.math.*;
public class Main{
public static void main(String[] args){
Scanner cin=new Scanner(System.in);
int T=cin.nextInt();
while(T-->0){
BigInteger n=cin.nextBigInteger();
BigInteger m=cin.nextBigInteger();
BigInteger ans=BigInteger.valueOf(0);
BigInteger nn=n;
int len=0;
while(nn.compareTo(BigInteger.ZERO)>0){
nn=nn.divide(BigInteger.valueOf(2));
len++;
}
for(int i=len-1;i>=0;i--){
BigInteger num1=BigInteger.valueOf(2).pow(i).subtract(BigInteger.ONE);
BigInteger num2=num1.multiply(m);
while(num2.compareTo(n)<0){
BigInteger num3=n.divide(BigInteger.valueOf(2).pow(i));
if(num3.compareTo(m)>0) num3=m;
n=n.subtract(BigInteger.valueOf(2).pow(i).multiply(num3));
ans=ans.add(BigInteger.valueOf(2).pow(i));
}
}
System.out.println(ans);
}
}
}