题解

这场被打爆了，写一下F的题解吧

• 大家好像都用的状压或者背包去做的，我贡献一个比较简单的做法。
• 表示当前i状态最少需要多少个数位与形成。
• 不难发现，重复的点对于答案的贡献为0，我们可以排序去重后线性dp一遍就行(这么做的话值域范围完全可以放到1000，这个题的值域范围比较小，也可以不去重排序直接做一遍就行)

#include <bits/stdc++.h>

#define x first
#define y second
#define pb push_back

using namespace std;

const int N = 2e5 + 10;
const int P = 1e9 + 7, INF = 0x3f3f3f3f;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef long long LL;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> f(201, INF); //选择尽可能少的位与为0

    for(int i = 0; i < n; i ++ ) 
        cin >> a[i];
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end()) - a.begin();

    for(int i = 0; i < a.size(); i ++ ) {
        f[a[i]] = 1;
        for(int j = 0; j <= 200; j ++ )
            f[j & a[i]] = min(f[j & a[i]], f[j] + 1);
    }
    if(f[0] == INF) cout << "-1\n";
    else cout << n - f[0] << '\n';

}

int main() {
    //cout << log(200) / log(2) << '\n';
    int T = 1;
    cin >> T;
    while(T -- ) {
        solve();
    }
    return 0;
}