• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CF431D Random Task

开发技术 开发技术 4小时前 2次浏览

题面:

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
喜欢 (0)