文档章节

2012百度之星第二场初始题-1

李勇2
 李勇2
发布于 2015/03/02 09:38
字数 962
阅读 24
收藏 0
点赞 0
评论 0

问题描述:

    给定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位二进制数本身的空间;

           

 

           

           

   

             

   


本文转载自:http://blog.csdn.net/liyong748/article/details/7627866

共有 人打赏支持
李勇2

李勇2

粉丝 45
博文 188
码字总数 62209
作品 0
广州
程序员
18届清华硕士狂拿18家互联网公司offer

2018校招总结(外企,国内大公司,国内创业公司) 本篇是我参加2018春招实习和秋招的求职经历,除了笔试面试中遇到的一些问题,更多的是一些个人想法。 春招和秋招面了不少公司,实习offer有...

野梦M ⋅ 2017/12/18 ⋅ 1

秒杀多线程第一篇 多线程笔试面试题汇总

系列前言 本系列是本人参加微软亚洲研究院,腾讯研究院,迅雷面试时整理的,另外也加入一些其它IT公司如百度,阿里巴巴的笔试面试题目,因此具有很强的针对性。系列中不但会详细讲解多线程同...

彭博 ⋅ 2012/04/12 ⋅ 0

秒杀多线程第一篇 多线程笔试面试题汇总

系列前言 本系列是本人参加微软亚洲研究院,腾讯研究院,迅雷面试时整理的,另外也加入一些其它IT公司如百度,阿里巴巴的笔试面试题目,因此具有很强的针对性。系列中不但会详细讲解多线程同...

晨曦之光 ⋅ 2012/05/21 ⋅ 0

秒杀多线程第一篇 多线程笔试面试题汇总

系列前言 本系列是本人参加微软亚洲研究院,腾讯研究院,迅雷面试时整理的,另外也加入一些其它IT公司如百度,阿里巴巴的笔试面试题目,因此具有很强的针对性。系列中不但会详细讲解多线程同...

长平狐 ⋅ 2012/12/10 ⋅ 0

Java类初始化顺序,大神3个示例带你躺坑。。

最近发现微信群里面有些群友在讨论类的初始化顺序,如类的静态变量、成员变量、静态代码块、非静态代码块、构造器,及继承父类时,它们的初始化顺序都是怎样的,下面我通过例子来说明这个情况...

架构之路 ⋅ 2017/11/23 ⋅ 0

System center 2012 R2 实战四、sharepoint2010服务器场介绍及安装

上一章我们安装了sharepoint2010,只是非常简单的安装上了,并且进行了几个简单的排错,然后又集成了一下reporting services,还记得吗,上一章我们安装sharepoint的时候选中的是独立安装,也...

科技小能手 ⋅ 2017/11/12 ⋅ 0

黑客游戏| Owasp juice shop (一)

0x01 前言 最近看到一篇关于owasp juice shop的文章,觉的很有意思,斗哥就自己撸了个环境,上手后深深觉的这是一个很棒的漏洞靶场,所以就把该环境介绍给大家,该漏洞靶场是由owasp开发的,...

漏斗社区 ⋅ 2017/11/28 ⋅ 0

Windows server 2008 R2 安装sharepoint2010

sharepoint2010最佳的系统平台是Windows server 2008R2,今天我们就在08R2上,安装一次sharepoint2010~ Come on~搞起 1.打开服务器管理器 2.选择Web服务服务器及应用服务器 3.添加相应角色 ...

科技小能手 ⋅ 2017/11/12 ⋅ 0

百度2010暑期实习笔试面试全面备战

百度2010暑期实习笔试面试全面备战 百度2010暑期实习网申将于2010年5月29日截止。 笔试阶段 5月30日前,对于通过了简历筛选的申请人百度将会通过系统发送笔试通知。注册时请务必填写正确有效...

长平狐 ⋅ 2013/01/06 ⋅ 0

百度2010年 Astar程序设计大赛启动

5月18日午间消息,由中文搜索引擎百度举办的“2010 Astar百度之星程序设计大赛”正式面向全国高校学生和广大编程爱好者启动,本届“Astar大赛”主题为“乐CODE乐CODE”。 除延续往届的赛程及...

红薯 ⋅ 2010/05/18 ⋅ 5

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Sqoop

1.Sqoop: 《=》 SQL to Hadoop 背景 1)场景:数据在RDBMS中,我们如何使用Hive或者Hadoop来进行数据分析呢? 1) RDBMS ==> Hadoop(广义) 2) Hadoop ==> RDBMS 2)原来可以通过MapReduce I...

GordonNemo ⋅ 52分钟前 ⋅ 0

全量构建和增量构建的区别

1.全量构建每次更新时都需要更新整个数据集,增量构建只对需要更新的时间范围进行更新,所以计算量会较小。 2.全量构建查询时不需要合并不同Segment,增量构建查询时需要合并不同Segment的结...

无精疯 ⋅ 今天 ⋅ 0

如何将S/4HANA系统存储的图片文件用Java程序保存到本地

我在S/4HANA的事务码MM02里为Material维护图片文件作为附件: 通过如下简单的ABAP代码即可将图片文件的二进制内容读取出来: REPORT zgos_api.DATA ls_appl_object TYPE gos_s_obj.DA...

JerryWang_SAP ⋅ 今天 ⋅ 0

云计算的选择悖论如何对待?

导读 人们都希望在工作和生活中有所选择。但心理学家的调查研究表明,在多种选项中进行选择并不一定会使人们更快乐,甚至不会产生更好的决策。心理学家Barry Schwartz称之为“选择悖论”。云...

问题终结者 ⋅ 今天 ⋅ 0

637. Average of Levels in Binary Tree - LeetCode

Question 637. Average of Levels in Binary Tree Solution 思路:定义一个map,层数作为key,value保存每层的元素个数和所有元素的和,遍历这个树,把map里面填值,遍历结束后,再遍历这个map,把每...

yysue ⋅ 今天 ⋅ 0

IDEA配置和使用

版本控制 svn IDEA版本控制工具不能使用 VCS-->Enable Version Control Integration File-->Settings-->Plugins 搜索Subversion,勾选SVN和Git插件 删除.idea文件夹重新生成项目 安装SVN客户......

bithup ⋅ 今天 ⋅ 0

PE格式第三讲扩展,VA,RVA,FA的概念

作者:IBinary 出处:http://www.cnblogs.com/iBinary/ 版权所有,欢迎保留原文链接进行转载:) 一丶VA概念 VA (virtual Address) 虚拟地址的意思 ,比如随便打开一个PE,找下它的虚拟地址 这边...

simpower ⋅ 今天 ⋅ 0

180623-SpringBoot之logback配置文件

SpringBoot配置logback 项目的日志配置属于比较常见的case了,之前接触和使用的都是Spring结合xml的方式,引入几个依赖,然后写个 logback.xml 配置文件即可,那么在SpringBoot中可以怎么做?...

小灰灰Blog ⋅ 今天 ⋅ 0

冒泡排序

原理:比较两个相邻的元素,将值大的元素交换至右端。 思路:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第...

人觉非常君 ⋅ 今天 ⋅ 0

Vagrant setup

安装软件 brew cask install virtualboxbrew cask install vagrant 创建project mkdir -p mst/vmcd mst/vmvagrant init hashicorp/precise64vagrant up hashicorp/precise64是一个box......

遥借东风 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部