首页 > 其他 > 详细

枚举大小为k的子集

时间:2018-09-22 23:11:07      阅读:66      评论:0      收藏:0      [点我收藏+]

标签:时间   {}   spa   操作   cpp   spl   span   条件   play   

这种位操作不大可能分析出来,先看代码再分析。

代码

使用条件:\(k>0\)

void solve(int n,int k)
{
    for(int comb = (1 << k) - 1; comb < (1 << n);)
    {
        // ...
        int x = comb & -comb, y = comb + x;
        comb = (((comb & ~y) / x ) >> 1) | y;
    }
}

证明

\[ \begin{array}{} 首先是辅助变量x,y\x \rightarrow comb最低位\y \rightarrow comb的倒数第一段1取0,该1段前一个位置的0取1\设上述y改变的部分为len\comb\&\sim y \rightarrow len前取0,len中取1,len后取0\(comb\&\sim y)/x \rightarrow 长度为len的全1串\((comb \& \sim y) / x ) >> 1 \rightarrow 右移1位,len-1\综上\(((comb \& \sim y) / x ) >> 1) | y \rightarrow 把comb的len的前一个位置的0取1,末尾添上len-1个1 \end{array} \]

然后这就是不重不漏的枚举。
所以时间复杂度\(O\left(\binom{n}{k}\right)\)

枚举大小为k的子集

标签:时间   {}   spa   操作   cpp   spl   span   条件   play   

原文:https://www.cnblogs.com/autoint/p/9691503.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号