【2022NOI模拟赛7T1】锁 做题记录

房子一共住了 $n$ 个人，这 $n$ 个人每个人有一个重要程度。

房门上可以装有若干把锁，每把锁有一种唯一的钥匙与之对应。

每一种钥匙可以复制若干份，并且可以发给任意多个居民。每个人都可以持有若干钥匙，也可以不持有钥匙。

如果若干名居民钥匙的并集是全集，他们都在场时就能打开房门，否则不能打开房门。

现在规定，一组居民都在场时能打开房门当且仅当他们的重要度之和大于等于为 $m$。

问至少需要给房门装多少把锁。即，求最小的 $k$，使得存在一种分配钥匙的方案，满足任意一组重要度之和小于 $m$ 的居民持有的钥匙的并集不能打开所有房门且任意一组重要度之和大于等于 $m$ 的居民持有的钥匙的并集能打开所有房门。

$1\le n\le20$，$1\le m\le 10^9$，$1 \le a_i \le m$。

一道神奇的结论题。

首先摆出结论：答案即为不同的非空集合 $S$ 个数 $x$，满足 $S$ 里面的人的重要度之和小于 $m$，但是 $S$ 任意再加上一个人的重要度之和就大于等于 $m$。

证明：

1. 证明锁的个数小于 $x$ 都不可行：考虑反证，设 $l<x$ 且有 $l$ 个锁的情况是可行的，那么由于一共有 $x$ 个满足条件的 $S$ 且 $x>l$，所以必定有两个满足条件的集合 $X$ 和 $Y$ 缺同一把钥匙。那么 $X$ 和 $Y$ 并起来也还是缺那一把钥匙，而此时的重要度之和肯定要大于等于 $m$，却开不了门，不合法。
2. 证明锁的个数等于 $x$ 可行：有这样的一种构造方法，每个人持有所有代表的集合不包含他的锁的钥匙。

最后记得特判 $\sum a_i<m$ 的情况，这时只需要一个任何人都没有钥匙的锁即可。