Weekly Contest 393
C - Kth Smallest Amount With Single Denomination Combination
用ans = f(k)
表示结果, 根据题意, f(k)
具有单调性. 因此, 可用二分法.
- 左边界,
l = k
- 右边界,
r = min(coins) * k
- 二分判断, 对于金额
mid
, 用cnt
表示当前集合中的硬币按题意组成的不同金额(<mid
)的数量,cnt >= k
表示f[k] <= mid
,cnt < k
表示f[k] >= mid + 1
rust
/// runs in O(n*2^nlog(k * min(coins)))/O(1)
pub fn find_kth_smallest(coins: Vec<i32>, k: i32) -> i64 {
let check = |m: i64| -> bool {
let mut cnt = 0i64;
for mask in (1..(1usize << coins.len())) {
let mut lcm_res = 1i64;
for j in (0..coins.len()) {
if mask >> j & 1 == 1 {
lcm_res = lcm(lcm_res, coins[j] as i64);
if lcm_res > m {
break;
}
}
}
cnt += m / lcm_res * if mask.count_ones() % 2 == 1 { 1 } else { -1 };
}
cnt >= k as i64
};
let mut l = k as i64;
let mut r = *coins.iter().min().unwrap() as i64 * k as i64;
while l < r {
let mid = (l + r) >> 1;
if check(mid) {
r = mid;
} else {
l = mid + 1;
}
}
r
}
fn lcm<T>(mut a: T, mut b: T) -> T
where
T: Eq
+ Ord
+ Default
+ Copy
+ std::ops::Rem<Output = T>
+ std::ops::Mul<Output = T>
+ std::ops::Div<Output = T>,
{
a * b / gcd(a, b)
}
fn gcd<T>(mut a: T, mut b: T) -> T
where
T: Eq + Default + Copy + std::ops::Rem<Output = T>,
{
while b != T::default() {
(a, b) = (b, a % b)
}
a
}
D - Minimum Sum of Values by Dividing Array
抽象描述: 把一个数组nums
拆分成m
个子数组, 使得每个子数组的AND和等于andValues[i]
. 用vals[i]
表示第i
个子数组最后一个元素的值, 求某种拆分法使得sum{vals}
最小.
定义dfs(i, j, and)
表示, 把nums[0..i)
分成j
段, 最后一段已有元素的AND和为and
.
rust
use std::collections::HashMap;
const INF: i32 = i32::MAX >> 2;
/// runs in O(nmlogU)/O(nmlogU), in which U = max(nums)
fn minimum_value_sum(nums: Vec<i32>, and_values: Vec<i32>) -> i32 {
let mut memo = HashMap::new();
let ans = dfs(0, 0, -1, &mut memo, &nums, &and_values);
if ans < INF {
ans
} else {
-1
}
}
fn dfs(
i: usize,
j: usize,
and: i32,
memo: &mut HashMap<(usize, usize, i32), i32>,
nums: &Vec<i32>,
and_values: &Vec<i32>,
) -> i32 {
let n = nums.len();
let m = and_values.len();
// prune
if m - j > n - i {
return INF;
}
// reach end
if j == m {
return if i == n { 0 } else { INF };
}
// memo optimization
if memo.contains_key(&(i, j, and)) {
return *memo.get(&(i, j, and)).unwrap();
}
let and = and & nums[i];
// and is monotone descrasing
if and < and_values[j] {
return INF;
}
let mut res = dfs(i + 1, j, and, memo, nums, and_values); // not divide
// divide
if and == and_values[j] {
res = res.min(dfs(i + 1, j + 1, -1, memo, nums, and_values) + nums[i]);
}
memo.insert((i, j, and), res);
res
}