CF1288D Minimax Problem
题目链接
看到题目中有很多 \(\min,\max\)，一眼二分答案。
考虑一个常见的套路：假设我们二分的值是 \(mid\)，那么我们在判断合法性时把数字矩阵变成 \(01\) 矩阵：假若 \(a_{i,j}\geq mid\)，则赋值为 \(1\)；否则为 \(0\)。
用了这个套路后，我们可以把一行中最小值是否 \(\geq mid\) 这个判断给替换成：\(b_i\) 是否每个都为 \(1\)。所以现在要求解的是：找到两行使得或起来每个位置都为 \(1\)。由于 \(m\leq 8\)，直接把一行给压成一个状态。
接下来有一种暴力的思路：直接对于每一行的状态都枚举补集的超集，看看是否存在。但是行数太多，外面还要套个二分答案，太慢了。考虑 \(01\) 状态最多只有 \(2^m\) 个，而 \(2^m\) 最多只有 \(256\) 个，也就是说，现在的状态序列中存在大量的重复。所以现在就只要对于合法的状态去枚举它补集的超集就行了。
当 \(m\) 较大的时候可以用高维前缀和优化枚举超集的过程。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 3e5 + 10, M = 1 << 8;
int n, m, U, a[N][10], s[N], id[M];
pair<int, int> p = make_pair(1, 1);
int check(int x){
fill(id, id + U + 1, 0);
FL(i, 1, n){
s[i] = 0;
FL(j, 1, m) s[i] |= (a[i][j] >= x) << j - 1;
id[s[i]] = i;
}
FL(i, 0, U) if(id[i]){
int t = U ^ i;
FL(j, i, U) if(id[j] && (j & t) == t){
p = make_pair(id[i], id[j]); return 1;
}
}
return 0;
}
int main(){
scanf("%d%d", &n, &m), U = (1 << m) - 1;
FL(i, 1, n) FL(j, 1, m) scanf("%d", &a[i][j]);
int l = 0, r = 1e9, ans;
while(l <= r){
int mid = l + r >> 1;
if(check(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
printf("%d %d\n", p.first, p.second);
return 0;
}