题目描述
DreamGrid has a nonnegative integer n. He would like to divide n into m nonnegative integers a1,a2,…,am and minimizes their bitwise or (i.e. n=a1+a2+…+am and a1 OR a2 OR … OR am should be as small as possible).
input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n and m (0≤n＜101000,1≤m＜10100).
It is guaranteed that the sum of the length of n does not exceed 20000.
output
For each test case, output an integer denoting the minimum value of their bitwise or.
样例输入
5 3 1 3 2 3 3 10000 5 1244 10
样例输出 Copy
3 3 1 2000 125
题意：
给出一个数n nn，构造出一个数列 a 1 . . . a m a_1 ... a_ma
1
...a
m
，使得所有数之和a 1 + . . . + a m a_1 + ... + a_ma
1
+...+a
m
为n nn，并且还要使得a 1 ∣ . . . ∣ a m a_1 | ... | a_ma
1
∣...∣a
m
尽可能的小，问最小的o r oror运算之后的值是多少
首先可以看到题目的数据范围很大，考虑使用Java大数B i g I n t e g e r BigIntegerBigInteger
很容易想到这是个贪心，并且涉及位运算我们可以按照每一位进行考虑，首先将2的次方数预处理出来，存放在一个B i g I n t e g e r BigIntegerBigInteger数组里面
然后考虑从小往大里面进行相加，每次加入m mm个二的次方数，一直到s u m ≥ n sum \geq nsum≥n ，然后我们记录这个时候的p o s pospos
然后我们这个时候再从后向前p o s − > 0 pos->0pos−>0 依次求出a [ i ] − 1 ∗ m a[i]-1 * ma[i]−1∗m 是否 ≥ n \geq n≥n，如果说≥ n \geq n≥n就跳过，反之求出现在的n nn还能凑出多少个a [ i ] a[i]a[i]，设个数为c n t cntcnt，c n t = m i n ( c n t , m ) cnt = min(cnt,m)cnt=min(cnt,m)那么就将a n s ansans中加入a [ i ] a[i]a[i]，然后将n nn减去c n t cntcnt个a [ i ] a[i]a[i]
main_code:
import java.math.BigInteger; import java.util.Scanner; public class Main { public static BigInteger a[] = new BigInteger[5007];///2 ** x public static void main(String[] args) { Scanner cin = new Scanner(System.in); int pos = 0; a[0] = BigInteger.valueOf(1); for(int i=1;i<=5000;i++){ a[i] = a[i-1].multiply(BigInteger.valueOf(2)); } // System.out.println(a[3]); int T = cin.nextInt(); BigInteger n,m; while(T > 0) { T -= 1; n = cin.nextBigInteger(); m = cin.nextBigInteger(); if (m.equals(BigInteger.valueOf(1))) {/// m == 1 System.out.println(n); continue; } BigInteger tn = n; BigInteger sum = BigInteger.valueOf(0), ans = BigInteger.valueOf(0); for (int i = 0; ; i++) { if(sum.compareTo(n) >= 0) break; sum = sum.add(m.multiply(a[i])); pos = i; } for (int i = pos; i >= 0; i--) { BigInteger t = a[i].subtract(BigInteger.valueOf(1)); if (t.multiply(m).compareTo(tn) >= 0) { continue; } BigInteger cnt = tn.divide(a[i]); cnt = cnt.min(m); ans = ans.add(a[i]); tn = tn.subtract(cnt.multiply(a[i])); } System.out.println(ans); } } } /** 5 3 1 3 2 3 3 10000 5 1244 10 * **/ /************************************************************** Problem: 4827 Language: Java Result: 正确 Time:1058 ms Memory:85000 kb ****************************************************************/
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树leetcode-贪心122-买卖股票的最佳时机 II8056 人正在系统学习中
