[CF1288D] Minimax Problem - 状态压缩,高维前缀和

给定一个 \(n\leq 3\times 10^5\) 行 \(m \leq 8\) 列的数字矩阵 \(a\)，找出两行 \(x,y\)，使得 \(\min_{j=1}^m \max(a_{x,j},a_{y,j})\) 最大

Solution

二分答案，考虑检验 \(mid\)，将每一行大于等于 \(mid\) 的数设为 \(1\)，反之设为 \(0\)，压位后扔进桶，往 \(1\) 方向做一下高维前缀和，然后扫一遍桶即可

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

#define int long long
const int N = 300005;

int n,m,a[N][9],b[256],c[256],p,y;

int check(int x) {
    memset(b,0,sizeof b);
    for(int i=1;i<=n;i++) {
        int t=0;
        for(int j=0;j<m;j++) {
            if(a[i][j]>=x) t|=1<<j;
        }
        b[t]=1;
        c[t]=i;
    }
    for(int i=(1<<m)-1;i>=0;--i) {
        for(int j=0;j<m;j++) {
            b[i&(~(1<<j))]|=b[i];
            if(b[i]) c[i&(~(1<<j))]=c[i];
        }
    }
    for(int i=1;i<=n;i++) {
        int t=0;
        for(int j=0;j<m;j++) {
            if(a[i][j]>=x) t|=1<<j;
        }
        if(b[(1<<m)-t-1]) {
            p=i;
            y=c[(1<<m)-t-1];
            return 1;
        }
    }
    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<m;j++) {
            cin>>a[i][j];
        }
    }
    int l=0,r=1e9+1;
    while(l<r) {
        int mid=(l+r)/2;
        if(check(mid)) l=mid+1;
        else r=mid;
    }
    check(l-1);
    cout<<p<<" "<<y<<endl;
}

[CF1288D] Minimax Problem - 状态压缩,高维前缀和

原文：https://www.cnblogs.com/mollnn/p/12592300.html