| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
中等 |
2258 |
第 380 场周赛 Q3 |
|
给你一个整数 k 和一个整数 x 。整数 num 的价值是它的二进制表示中在 x，2x，3x 等位置处 设置位 的数目（从最低有效位开始）。下面的表格包含了如何计算价值的例子。
| x | num | Binary Representation | Price |
|---|---|---|---|
| 1 | 13 | 000001101 | 3 |
| 2 | 13 | 000001101 | 1 |
| 2 | 233 | 011101001 | 3 |
| 3 | 13 | 000001101 | 1 |
| 3 | 362 | 101101010 | 2 |
num 的 累加价值 是从 1 到 num 的数字的 总 价值。如果 num 的累加价值小于或等于 k 则被认为是 廉价 的。
请你返回 最大 的廉价数字。
示例 1：
输入：k = 9, x = 1 输出：6 解释：由下表所示，6 是最大的廉价数字。
| x | num | Binary Representation | Price | Accumulated Price |
|---|---|---|---|---|
| 1 | 1 | 001 | 1 | 1 |
| 1 | 2 | 010 | 1 | 2 |
| 1 | 3 | 011 | 2 | 4 |
| 1 | 4 | 100 | 1 | 5 |
| 1 | 5 | 101 | 2 | 7 |
| 1 | 6 | 110 | 2 | 9 |
| 1 | 7 | 111 | 3 | 12 |
示例 2：
输入：k = 7, x = 2 输出：9 解释：由下表所示，9 是最大的廉价数字。
| x | num | Binary Representation | Price | Accumulated Price |
|---|---|---|---|---|
| 2 | 1 | 0001 | 0 | 0 |
| 2 | 2 | 0010 | 1 | 1 |
| 2 | 3 | 0011 | 1 | 2 |
| 2 | 4 | 0100 | 0 | 2 |
| 2 | 5 | 0101 | 0 | 2 |
| 2 | 6 | 0110 | 1 | 3 |
| 2 | 7 | 0111 | 1 | 4 |
| 2 | 8 | 1000 | 1 | 5 |
| 2 | 9 | 1001 | 1 | 6 |
| 2 | 10 | 1010 | 2 | 8 |
提示：
1 <= k <= 10151 <= x <= 8
我们注意到，如果
我们定义二分查找的左边界
接下来，我们进行二分查找，对于每一个
最后，我们返回左边界
时间复杂度
class Solution:
def findMaximumNumber(self, k: int, x: int) -> int:
@cache
def dfs(pos, limit, cnt):
if pos == 0:
return cnt
ans = 0
up = (self.num >> (pos - 1) & 1) if limit else 1
for i in range(up + 1):
ans += dfs(pos - 1, limit and i == up, cnt + (i == 1 and pos % x == 0))
return ans
l, r = 1, 10**18
while l < r:
mid = (l + r + 1) >> 1
self.num = mid
v = dfs(mid.bit_length(), True, 0)
dfs.cache_clear()
if v <= k:
l = mid
else:
r = mid - 1
return lclass Solution {
private int x;
private long num;
private Long[][] f;
public long findMaximumNumber(long k, int x) {
this.x = x;
long l = 1, r = (long) 1e17;
while (l < r) {
long mid = (l + r + 1) >>> 1;
num = mid;
f = new Long[65][65];
int pos = 64 - Long.numberOfLeadingZeros(mid);
if (dfs(pos, 0, true) <= k) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
private long dfs(int pos, int cnt, boolean limit) {
if (pos == 0) {
return cnt;
}
if (!limit && f[pos][cnt] != null) {
return f[pos][cnt];
}
long ans = 0;
int up = limit ? (int) (num >> (pos - 1) & 1) : 1;
for (int i = 0; i <= up; ++i) {
ans += dfs(pos - 1, cnt + (i == 1 && pos % x == 0 ? 1 : 0), limit && i == up);
}
if (!limit) {
f[pos][cnt] = ans;
}
return ans;
}
}class Solution {
public:
long long findMaximumNumber(long long k, int x) {
using ll = long long;
ll l = 1, r = 1e17;
ll num = 0;
ll f[65][65];
auto dfs = [&](this auto&& dfs, int pos, int cnt, bool limit) -> ll {
if (pos == 0) {
return cnt;
}
if (!limit && f[pos][cnt] != -1) {
return f[pos][cnt];
}
int up = limit ? num >> (pos - 1) & 1 : 1;
ll ans = 0;
for (int i = 0; i <= up; ++i) {
ans += dfs(pos - 1, cnt + (i == 1 && pos % x == 0), limit && i == up);
}
if (!limit) {
f[pos][cnt] = ans;
}
return ans;
};
while (l < r) {
ll mid = (l + r + 1) >> 1;
num = mid;
memset(f, -1, sizeof(f));
int pos = 64 - __builtin_clzll(mid);
if (dfs(pos, 0, true) <= k) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
};func findMaximumNumber(k int64, x int) int64 {
var l, r int64 = 1, 1e17
var num int64
var f [65][65]int64
var dfs func(pos, cnt int, limit bool) int64
dfs = func(pos, cnt int, limit bool) int64 {
if pos == 0 {
return int64(cnt)
}
if !limit && f[pos][cnt] != -1 {
return f[pos][cnt]
}
var ans int64
up := 1
if limit {
up = int(num >> (pos - 1) & 1)
}
for i := 0; i <= up; i++ {
v := cnt
if i == 1 && pos%x == 0 {
v++
}
ans += dfs(pos-1, v, limit && i == up)
}
if !limit {
f[pos][cnt] = ans
}
return ans
}
for l < r {
mid := (l + r + 1) >> 1
num = mid
m := bits.Len(uint(num))
for i := range f {
for j := range f[i] {
f[i][j] = -1
}
}
if dfs(m, 0, true) <= k {
l = mid
} else {
r = mid - 1
}
}
return l
}function findMaximumNumber(k: number, x: number): number {
let [l, r] = [1n, 10n ** 17n];
let num: bigint;
const f: bigint[][] = Array.from({ length: 65 }, () => Array(65).fill(-1n));
const dfs = (pos: number, cnt: number, limit: boolean): bigint => {
if (pos === 0) {
return BigInt(cnt);
}
if (!limit && f[pos][cnt] !== -1n) {
return f[pos][cnt];
}
let ans: bigint = 0n;
let up: number = 1;
if (limit) {
up = Number((num >> BigInt(pos - 1)) & 1n);
}
for (let i = 0; i <= up; i++) {
let v: number = cnt;
if (i === 1 && pos % x === 0) {
v++;
}
ans += dfs(pos - 1, v, limit && i === up);
}
if (!limit) {
f[pos][cnt] = ans;
}
return ans;
};
while (l < r) {
let mid: bigint = (l + r + 1n) >> 1n;
num = mid;
let m: number = num.toString(2).length;
for (let i = 0; i < f.length; i++) {
f[i].fill(-1n);
}
if (dfs(m, 0, true) <= BigInt(k)) {
l = mid;
} else {
r = mid - 1n;
}
}
return Number(l);
}