CF1288D Minimax Problem 题解

yyrwlj · 2024-11-07 18:35:59 · 题解

最小值最大，一眼二分。

如果第 i 行第 j 个数不满足要求，就让 v_i 的二进制第 j 位为 1。

然后可以转化题意：给定 n 个数，找到两个数使他们的二进制等于 0。

考虑 SOSdp，f_i 表示状态 i 的子集内的任意一个数，然后按照 SOSdp 正常从子集转移即可。

然后枚举 v_i，设 w_i 为 v_i 与 2^m-1 进行位异或运算的结果，那么所选的另一个 v_i 必须处于 w_i 的子集内，看 f_{w_i} 对应是否有数即可。

#define x first
#define y second
typedef pair<int, int> PII;
const int N = 300005;
int a[N][10], v[N], w[N], f[1 << 10], n, m;
PII check(int mid)
{
    memset(f, -1, sizeof f);
    for (int i=1;i<=n;i++)
    {
        v[i] = w[i] = 0;
        for (int j=0;j<m;j++)
            if (a[i][j] < mid)
                v[i] |= 1 << j;
            else
                w[i] |= 1 << j;
        f[v[i]] = i;
    }
    for (int i=0;i<m;i++)
        for (int j=0;j<(1<<m);j++)
            if ((j >> i & 1) && ~f[j ^ (1 << i)])
                f[j] = f[j ^ (1 << i)];
    for (int i=1;i<=n;i++)
        if (~f[w[i]])
            return {i, f[w[i]]};
    return {0, 0};
}
void work()
{
    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;
    PII ans;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        PII res = check(mid);
        if (res.x)
            ans = res, l = mid + 1;
        else
            r = mid - 1;
    }
    cout << ans.x << ' ' << ans.y;
}