题面大意:
- 给出N个数,
- 找出最大的子集size 使得
- 子集中, 任意2个数的 二进制下, 每一位, 至少有2位不同
思路:
- N 只有5000, 可以直接暴力建边, 转化位图论
- 2种建边方式: 一种是 能在一个集合的2个数, 建一条边, (没有办法去处理这个问题)
- 一种是 不能在一个集合的就建一条边, 发现性质: 会形成一个二分图
- 贪心: a-b b -c -> a-c 一定会有2个位是不同的!!!! 所以a-c 一定不会有边
- 既然是二分图, 那么这个题就是 求 二分图的 最大独立集
- 二分图的最大独立集 = n- 最大匹配数(最小点覆盖(选出最小点的数量去覆盖所有边))
关键:
- 如何去从题面信息挖掘想出那个性质来发现二分图,
- 因为没有算法可以去解决现在这个问题,那么就一定要通过题目性质去优化
- 而题目的关键信息就哪一个