注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

一个集合任意子集的异或和都不为0的子集为啥组成了一个拟阵  

2013-04-13 19:56:03|  分类: 知识点 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
求一个集合的一个子集A,使得A中没有任何一个子集的元素抑或和为0,且A中元素之和最大。

解法是……这个家伙组成了一个拟阵……所以排个序顺着贪心,用高斯消元检验合法性。

为啥是拟阵?好吧我承认之前都是直接背的这个结论。

回忆:
一个拟阵是满足下列条件的一个序对 M=(S,L):
(1)S是一个有穷集合。
(2)L是S的一个非空子集簇,即L是由S的子集作为元素构成的集合,且非空。
(3)如果B∈L,并且A包含于B,则有A属于L,称为遗传性。
(4)如果A∈L,B∈L并且|B|>|A|,则有一定存在一个x∈B-A,使得集合A并上{x}之后形成的集合仍属于L,该性质称为交换性。

(1)显然
(2)显然
(3)显然
(4)怎么证?
我跑去问ds、Parabola、doyouloveme神犇(怎么ds网名这么多)
讨来了一份秀美的证明:
一个集合任意子集的异或和都不为0的子集为啥组成了一个拟阵 - vfleaking - vfleaking的博客

ds太神了!

双倍经验:
2460: [BeiJing2011]元素
3105: [cqoi2013]新Nim游戏
  评论这张
 
阅读(1010)| 评论(5)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017