关于此题CF2061E_Kevin and And的一些总结

传送门
题目大意：给定\(n\)个数\(a[1...n]\)和\(m\)个数\(b[1...m]\)，并且给定整数k，求让任意\(i,j\)使\(a[i]&b[j]\)来替代\(a[i]\)后这\(n\)个数总和最小。

• 首先我们看到题目给的m范围非常小，最大只有10，然后又问我们k次操作之后总和的最小值，第一反应是不是可以直接先求出每个\(a[i]\)分别执行\(1...k\)次操作后的最小，然后再用DP来做。然而我们发现，让一个数与上另一个数，得到的结果一定是小于等于当前这个数的（&的运算规则），那也就是说一个数每次和另一个数&操作得到的结果和它本身相比都伴随着减少或者不变，于是乎发现分本用不着DP，只需要直接贪心地每次操作都找减少的最多的那一个就可以了。时间复杂度\(O(n * 2^{m})\)
• 这里我们先用状压预处理出\(b\)数组中任几个&操作的结果。再往后枚举每个\(a[i]\)，对于当前\(a[i]\)，我们都求出其最小的&上\(1...m\)个\(b\)中的数的结果装到一个数组中，最后排序取最大的前\(k\)个即可

#include<bits/stdc++.h>
    
using namespace std;

long long t;
const long long N = 2e5 + 10;
long long n,m,k,ans;
long long a[N],b[N];
    
void solve() {
    ans = 0;
    cin >> n >> m >> k;
    for(long long i = 1;i <= n;i++) cin >> a[i],ans += a[i];
    for(long long i = 0;i < m;i++) cin >> b[i];
    vector<long long> f(1100);
    f[0] = (1ll << 30) - 1;
    for(long long i = 1;i < (1 << m);i++) {
        long long u = __builtin_ctz(i);
        f[i] = f[i ^ (1 << u)] & b[u];
    }
    vector<long long> h;
    for(long long i = 1;i <= n;i++) {
        vector<long long> g(m + 1);
        for(long long j = 0;j < (1 << m);j++) {
            long long c = __builtin_popcount(j);
            g[c] = max(g[c],a[i] - (a[i] & f[j]));
        }
        for(long long j = 1;j <= m;j++)
            h.emplace_back(g[j] - g[j - 1]);
    }
    
    sort(h.begin(),h.end(),greater<int>());
    for(long long i = 0;i < k;i++) ans -= h[i];
    cout << ans << '\n';
}
    
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> t;
    while(t--) solve();
    
    return 0;
}

• 这里又两个函数__builtin_ctz()和__builtin_popcount()，分别求的是最后一个1后有多少个0和整个数有多少个1，类似的还有__builtin_clz()等函数，不仅方便而且性能也很优秀