CF431D Random Task

本文主要是介绍CF431D Random Task，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面：

CF431D Random Task

题意：

给定两个数 \(m\) 和 \(k\) ，要求输出一个 \(ans\) ，满足在 $[ ans + 1 , 2 ans] $ 这个区间中恰有 \(m\) 个数的二进制表示中恰有 \(k\) 个 1 （输出的 \(ans\) 为任一满足题意的即可）。

解法：

这题的第一步也是最重要的一步，在于挖掘题目性质。

性质一：

我们用 \(cnt_i\) 表示在 \([i + 1 , 2 i]\) 这个区间内二进制表示中恰有 \(k\) 个 1 的数的个数 。

那么这个 \(cnt_i\) 一定随 \(i\) 的增大而 单调不减 。

证明：

\(cnt_i\) 中包含的数为 \([i + 1 , 2 i]\) 。
\(cnt_{i+1}\) 中包含的数为 \([i+2,2i+2]\) 。

可以看出两个区间中 \([i+2,2i]\) 这一段是重合的 。

前者可表示为 \(\{i+1\} \cup [i+2,2i]\) 。
后者可表示为 \(\{2i+1 , 2i + 2\} \cup [i + 2 , 2i]\) 。

而 \(2i+2 = (i + 1) << 1\) ，它们两者包含 1 的个数相同。所以我们可以知道 \(cnt_{i+1}\) 比 \(cnt_i\) 对其大小贡献多的部分在于 \(2i+1\) ， 其他部分完全相同，所以 \(cnt_i\) 单调不减 。

自此，我们可以知道这道题的答案具有可二分性。

性质二：

如果我们用 \(f_i\) 表示在 \([1,i]\) 这个区间内二进制表示中恰有 \(k\) 个 1 的数的个数，那么 \(cnt_i\) 即为 \(f_{2i} - f_i\) 。

重难点：如何算出 \(f_i\) :

这里我们就需要一些组合数学的知识了。

首先我们需要把一个数字十进制转二进制。

void change(int x){
    if(x == 0) return ;
    change(x >> 1);
    s += ((x & 1) + '0');
}

然后对这个二进制数进行 \(f_i\) 的计算 。

举个例子：\(i_{10} = 183\) ， \(k = 3\) 时 ， \(i_2 = 10110111\) 。

我们把 \([1,10110111]\) 按位从高到低拆成若干个区间：

\([0,10000000) , [10000000 , 10100000) …… [10110110,10110111) , \{10110111\}\) 。

在第一个区间中，可以理解成 7 个数中选 3 个的组合数个数 。第二个区间中，已经有一个 1 被确定，那么其组合数为 5 个数中选 2 个的组合数个数 ……

以此类推，设 \(w\) 为一个区间右端点最低的 1 处于的位置，\(h\) 为区间左端点 1 的个数，那么该区间符合条件数的个数为 \(C_{w - 1}^{k - h}\) 。然后 \([1,i]\) 的答案其实就是各区间的答案相加。

代码实现极其简单而又清新：

for(int i=0;i<siz;i++){
    if(s[i] == '0') continue;
    if(k - numone <= 0) break;
    sum += zhs[siz - i - 1][k - numone];
    numone ++;
}

综上：这题只需要先预处理 \(C_1^1\) ~ \(C_{64}^{64}\) ，然后二分答案判断 \(mid\) 的 \(f_{2mid} - f_{mid}\) 是否等于 \(m\) 就行啦。

时间复杂度：

预处理是 \(O(64^2)\) 的 ，二分答案 + 计算 \(f_i\) 是 \(O(\log^2 n)\) 的。

所以总复杂度为 \(O(\log^2 n)\) 。

Code

这篇关于CF431D Random Task的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！