锁¶
题意¶
房子内一共有 n 位居民，房门上有 k 种锁，每种锁都对应一种钥匙。每种钥匙都有足够多，你可以将它们任意分配给居民。一个居民既可以没有钥匙，也可以得到多把钥匙。
一个村民的集合能够开锁，当且仅当这个集合中的村民掌握了 k 种钥匙中的每一种。
每个居民有一个重要度 a_i，一个村民的集合是重要的，当且仅当其中所有村民的重要度之和大于等于 m。请你求出 k 的最小值，使得存在一种分配钥匙的方案，满足任何一个重要的村民集合能够开锁，任何一个不重要的村民集合不能开锁。
解析¶
自然地，我们可以为每一个“不重要”的集合都新增一种钥匙，将其分发给这个“不重要”集合的补集。这样一定可以保证所有“不重要”的集合都无法打开房门；由于任何“重要”集合一定不含于任何一个“不重要”集合，则其也一定含有所有钥匙。
除此之外，如果一个“不重要”集合是另一个“不重要”集合的子集，则没必要为其新增一种钥匙，因为它的钥匙不是全集的限制已经由它的超集满足了。
这种构造方法显然是合法的，但是否是最优的？这里给出一个比较玄学的证明：
证明
设按照以上方法需要 x 种钥匙，也就是说极大不重要集合的数量为 x。若存在一种更优的方法使用少于 x 种钥匙，根据抽屉原理，必然存在两个极大不重要集合都不含同一种钥匙，它们的并集不能开门。故不存在使用少于 x 种钥匙的分配方案。
实现¶
#include <bits/stdc++.h>
int n, m, a[20];
long long int sum[1 << 20];
bool vist[1 << 20];
int main(){
std::scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i) std::scanf("%d", a + i);
for(int s = 1; s < (1 << n); ++s){
for(int i = 0; i < n; ++i)
if(s & (1 << i)){
sum[s] = sum[s ^ (1 << i)] + a[i];
break;
}
if(sum[s] < m)
for(int i = 0; i < n; ++i)
if(s & (1 << i))
vist[s ^ (1 << i)] = true;
}
int ans = 0;
for(int s = 1; s < (1 << n); ++s)//s=0? whether emptyset is taken into consideration is not defined.
if(sum[s] < m && !vist[s])
++ans;
std::printf("%d\n", ans);
return 0;
}