题解：P11475 [COCI 2024/2025 #3] 红蓝牌 / Karte

xiaoshumiao · 2025-02-17 22:31:47 · 题解

注意到数据范围很小，因此考虑暴力枚举选哪些红牌。

令 w_i 代表选了第 i 张蓝牌的话，会有哪些红牌和他产生贡献。为了方便，可以转化成二进制数存储。显然这个东西可以预处理出来。

设当前选的红牌集合为 i（也是一个二进制数），可以枚举所有蓝牌。对于第 j 张蓝牌，如果该蓝牌的贡献 i \cap w_j（实现时可以使用按位与运算）比 y 大，那么表示选第 j 张蓝牌是赚的。将其贡献累加到计数器上，最后减去 x \times \operatorname{popcount}(i) 就是答案。

时间复杂度 O(2^NM)，代码实现如下：

#include<bits/stdc++.h>
using namespace std;
const int N=30; char s[N][N]; int w[N];
int main() {
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int n,m,x,y,ans=0; cin>>n>>m>>x>>y;
    for(int i=1;i<=n;i++) cin>>(s[i]+1);
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(s[j][i]-'0') w[i]|=(1<<(j-1));
    for(int i=0;i<(1<<n);i++) {
        int sum=-x*__builtin_popcount(i);
        for(int j=1;j<=m;j++) sum+=max(__builtin_popcount(i&w[j])-y,0);
        ans=max(ans,sum);
    }
    cout<<ans;
    return 0;
}