C/C++教程

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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!