题目描述：
给你一个整数 k 和一个整数 x 。
令 s 为整数 num 的下标从 1 开始的二进制表示。我们说一个整数 num 的 价值 是满足 i % x == 0 且 s[i] 是 设置位 的 i 的数目。
请你返回 最大 整数 num ，满足从 1 到 num 的所有整数的 价值 和小于等于 k 。
注意：
- 一个整数二进制表示下 设置位 是值为
1 的数位。 - 一个整数的二进制表示下标从右到左编号，比方说如果
s == 11100 ，那么 s[4] == 1 且 s[2] == 0 。
数据范围：
$1\le k \le 10^{15}, 1\le x\le 8$
题解：
之前写的数位dp都是统计数的个数的，这个题目也是需要数位dp做，但是需要统计价值。
区别就是 $dp$ 数组的含义，假设 $dp[step][val]$ 为枚举到 $step$ 位，并且该位不受最大值限制，前面价值为 $val$ 时的总价值和。
也就是需要修改模板，在 step == n 时，返回 $val$ ，而不是返回 $!islead$ 。
也要使用二分check，check的时候使用数位dp检查。由于是否存在前导零对答案没有影响，因此可以不用使用 isLead。
还需要提前把数字转化为二进制。
最后还剩一个问题：二分的上界取多少合适？
$1$ 到 $num$ 中的数字 $v$ ，除以 $2^{x-1}$ 后如果是奇数，就说明 $v$ 至少包含一个我们需要的 $1$ 。而 $1$ 到 $num$ 中有 $\left\lfloor\dfrac{\textit{num}+1}{2}\right\rfloor$ 个奇数，所以取 $num$ 为 $(k + 1)2^x$ 可以保证价值和至少是 $k+1$ ，一定不满足二分判定。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
string s;
int n;
int x;
long long dp[64][64];
long long dfs(int step, int val, bool isLimit)
{
if (step == n)
return val;
if (!isLimit && dp[step][val] != -1)
return dp[step][val];
long long ans = 0;
int up = isLimit ? s[step] - '0' : 1;
for (int i = 0; i <= up; ++i)
{
ans += dfs(step + 1, val + (i == 1 && ((n - step) % x == 0)), isLimit && i == up);
}
if (!isLimit)
dp[step][val] = ans;
return ans;
}
bool check(long long mid, long long k, int _x)
{
s.clear();
while (mid)
{
if (mid & 1)
s.push_back('1');
else
s.push_back('0');
mid >>= 1;
}
n = s.length();
x = _x;
reverse(s.begin(), s.end());
memset(dp, -1, sizeof(dp));
long long ret = dfs(0, 0, true);
return ret <= k;
}
long long findMaximumNumber(long long k, int x)
{
long long l = 1, r = (k + 1) << x;
long long ans;
while (l <= r)
{
long long mid = l + (r - l >> 1);
if (check(mid, k, x))
{
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
return ans;
}
};
|