2012百度之星第二场初始题-1
博客专区 > 李勇2 的博客 > 博客详情
2012百度之星第二场初始题-1
李勇2 发表于3年前
2012百度之星第二场初始题-1
  • 发表于 3年前
  • 阅读 20
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

问题描述:

    给定n个正整数, 要求从这些正整数中 取出若干个, 对他们进行xor(异或)计算, 寻找可能产生的最大值。


    xor运算有点类似于加法运算,但是它操作的是二进制的数字; 例如 101010 xor 111000 = 010010

    ok解决任何问题,首先找出一些实际的例子, 例如在 集合 {5, 3} 中寻找;

    首先写成2进制的形式:

    1001  = 5

    0011  = 3

    有点类似于一个现行方程组矩阵的样子;

    而我们寻找的解是什么呢? 是这个方程组的xor 下的线性变化 产生的最大值 ?

    为什么? 

        xor 满足交换律 和 结合律;

        线性变化,就是在不同的方程之间使用xor操作, 用产生的结果替换 原来的方程, 这个新的方程组和原来的方程组等价;

             为什么等价?

                      A xor B = C   =>  C xor B = A   C xor A = B  

                      原来的方程组可以逆向得到, 所以等价


   怎么得到最大值?

            采用高斯消元法 可以得到一个等价方程组, 例如集合{101010,  111000,  110101,  001111} 

            消元之后的结果是:

                100101
                010000
                001101
                000010

             这个方程组的每个方程的维度是6, 但是整个方程组的度 是 4; 即六维空间里面的一个4维的对象;

             这4个方程任意xor的最大值是就是这四个方程全部xor的结果:

            111010

            为什么? 比如第四列为0, 为了使第四列为1, 必须舍弃 第1 或 3 方程, 显然都不行;

             而如果使6列为1, 需要舍弃 1 或者 3方程, 显然也不行;

             而如果舍弃某个 方程,也不合适, 会导致某一位变成0

             而由 xor的交换律 和结合律 可以知道: 所有组合的最后化简的结果 每个方程最多出现一次 因为 A xor A = 0   0 xor B = B


如何证明这四个方程组的最大值就是 原来集合中的最大值呢? 

             由xor的计算的可逆性,我们可以知道:

             因为在集合 {101010, 111000, 110101, 001111} 中的任意元素都可以由最后我们计算的四个方程表示;

             所以集合中任意元素组合的xor结果都可以用 最后计算的4个方程表示。

             而这4个方程xor的结果 最大值是 111010  

             

上面的例子:

           这个例子是方程的个数小于 维度的一个例子;  可以有3种情况:

           个数 小于 维度;  独立方程的个数 就是原方程组方程的个数;

           个数 等于 维度;   独立方程的个数 等于 维度

           个数 大于 维度;   独立方程的个数 等于 维度


而要计算次大值:

           可以从化简结果中舍弃一个最小的方程; 

           为什么?

                  舍弃最小的方程, 将会导致 某一位 变成0, 而这一位是独立的; 其它位不会变化;

                  如果要使其它位变化, 

                                           要么这个位本身是独立的, 那么 就比舍弃最小的要大;

                                           要么这个位依赖于其它位, 那么要么依赖于最小的独立位, 要么依赖于其它的独立位, 这样产生的结果要么等价于舍弃最小的方程,要么等价于舍弃其它方程, 都不合适



产生结果的实际个数:

           4个方程的 任意组合 产生的结果的个数 是 2^4 = 16 (包含一个空集合); 也就是4个方程的任意组合结果有16个

           对于一个32位二进制数, 最多有 2^32 种结果, 也就是32位二进制数本身的空间;

           

 

           

           

   

             

   


标签: 百度 c
共有 人打赏支持
李勇2
粉丝 43
博文 183
码字总数 60421
×
李勇2
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: