求一个集合的一个子集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网名这么多)
讨来了一份秀美的证明:
ds太神了!
双倍经验:
2460: [BeiJing2011]元素
3105: [cqoi2013]新Nim游戏
评论