NC14732 锁
NC14732 鎖
題意：
n個(gè)居民，門上有k把鎖，每個(gè)居民有若干鑰匙，為1到k的一個(gè)子集，如果幾名居民的鑰匙的并集是1到k，即他們擁有全部鎖的對應(yīng)鑰匙。
求最小的k，使得可以適當(dāng)?shù)亟o居民們每人若干鑰匙(即一個(gè)1到k的子集)，使得任意重要度之和小于m的居民集合持有的鑰匙的并集不是1到k，而任意重要度之和大于等于m的居民集合持有的鑰匙的并集是1到k
題解：
思路很妙
很明顯是狀壓
我的思路一開始都跑偏了，我想的是枚舉每個(gè)人擁有的鑰匙狀態(tài)，但是鑰匙的數(shù)量是未知的
我們這樣想：
重要度不足m的不能開門，大于m的一定能開門，對于一個(gè)狀態(tài)i，i表示包含一些人但是重要度不足m的狀態(tài)，當(dāng)再加入任意一個(gè)人x后，就會超過m，說明x含有的鑰匙是狀態(tài)i沒有的，所以問題就是求有多少個(gè)這樣的狀態(tài)i
對于當(dāng)前狀態(tài)(小于m)，判斷是否對于每個(gè)人而言加上他都是可以大于m，如果可以就算一個(gè)答案，只要存在一個(gè)人加上他也不滿足，那此狀態(tài)作廢
這個(gè)講得透徹
代碼：
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll a[30]; ll ans=0; ll n,m;int main () {scanf("%lld%lld",&n,&m);for(int i=0;i<n;i++) scanf("%lld",&a[i]);for(int i=0;i<(1<<n);i++){ll lo=0;for(int j=0;j<n;j++) if(i&(1<<j)) lo+=a[j];if(lo>=m) continue;bool flag=true;for(int j=0;j<n;j++) if(!(i&(1<<j)))//當(dāng)前狀態(tài)沒有第j個(gè)人 if(lo+a[j]<m) flag=false;if(flag) ans++;}printf("%lld\n",ans); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎總結(jié)
