ZONe Energy Programming Contest C - MAD TEAM (二分 + 状压) (好题)

传送门

第一眼就想到了二分但不会写check…

我们要保证选出的三个人中，每项能力至少有一个人 >= mid，我卡在了这里不知道怎么枚举…

我们可以将每个人每项能力的状态压缩, >= mid 的 就为1，否则为0。现在问题转换为是否能找到3个人，使他们的状态 | 起来为(1 << 5) - 1，这样就满足了 每项能力至少有一个人 >= mid。

可直接暴力，复杂度为2 ^ 15。也可以用dp保存中间状态，复杂度为 5*2 ^ 10。

暴力版本

#include<bits/stdc++.h>
using namespace std;
 
#define de(x) cout << #x << " == " << x << endl
 
typedef long long LL;         
typedef pair<int, int> P;
 
const int maxn = 3000 + 10;        
const int M_MAX = 50000 + 10;
const int mod = 1e9;
const int INF = 0x3f3f3f3f;    
const double eps = 1e-6;      
 
int n;
int a[maxn][5];
int S[1 << 5];
 
bool check(int x) {
    memset(S, 0, sizeof S);
    for(int i = 1; i <= n; i++) {
        int s = 0;
        for(int j = 0; j < 5; j++) {
            if(a[i][j] >= x) {
                s |= 1 << j;
            }
        }
        S[s] = 1;
    }
    for(int i = 0; i < 1 << 5; i++) {
        for(int j = 0; j < 1 << 5; j++) {
            for(int k = 0; k < 1 << 5; k++) {
                if(S[i] && S[j] && S[k]) {
                    if((i | j | k) == (1 << 5) - 1)
                        return true;
                }
            }
        }
    }
    return false;
}
 
void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 5; j++) {
            cin >> a[i][j];
        }
    }
    int l = 1, r = 1e9;
    while(l < r) {
        int mid = (l + r + 1) / 2;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
}
 
int main() {
    //ios::sync_with_stdio(false);
    //srand(time(NULL));    //更新种子
    solve();
    return 0;
}  

dp版本

#include<bits/stdc++.h>
using namespace std;
 
#define de(x) cout << #x << " == " << x << endl
 
typedef long long LL;         
typedef pair<int, int> P;
 
const int maxn = 3000 + 10;        
const int M_MAX = 50000 + 10;
const int mod = 1e9;
const int INF = 0x3f3f3f3f;    
const double eps = 1e-6;      

int n;
int a[maxn][5];
int dp[4][1<<5];

bool check(int x) {
    memset(dp, 0, sizeof dp);
    for(int i = 1; i <= n; i++) {
        int S = 0;
        for(int j = 0; j < 5; j++) {
            if(a[i][j] >= x) S |= (1 << j);
        }
        dp[1][S] = 1;
    }
    dp[1][0] = dp[2][0] = 1;
    for(int i = 1; i <= 2; i++) {
        for(int j = 0; j < 1 << 5; j++) {
            for(int k = 0; k < 1 << 5; k++) {
                dp[i+1][j | k] |= (dp[i][j] & dp[1][k]); 
            }
        }
    }
    return dp[3][(1<<5)-1];
}

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 5; j++) {
            cin >> a[i][j];
        }
    }
    int l = 1, r = 1e9;
    while(l < r) {
        int mid = (l + r + 1) / 2;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
}
 
int main() {
    ios::sync_with_stdio(false);
    //srand(time(NULL));    //更新种子
    solve();
    return 0;
}  

以后不会枚举了，就去想想怎么状压吧！感觉状压真的是思路又清晰又好写。