D. Minimax Problem
题意 && 思路
题意:
给出 n 个长度为 m 的序列(1 ≤ n ≤ 3*1e5, 1≤ m ≤8 ), 对于序列中的每一个元素 a,(0≤a≤1e9)
现在你要求出, 对于所有任意两行序列为一组 (或则自己本身成为一组), 进行(两个序列的同一个位置取最大值放到新序列中) 操作形成新的序列, 再从新的序列中选取最小值作为 ans, 最后要对所有可能组成的 ans 中输出最大的 ans.
思路:
说实话没有想到用二分加二进制压缩表示来求解. 二分倒是可以想到, 毕竟正向 把两两所有枚举都是 O( n^2 )了, 所以就容易想着反向去求解答案.
题解给的是: 二分去选取一个数 (作为假设的最终答案), 把 序列中比这个数小的 记为 0, 大于等于这个数记为 1. 最后就可以得到一个(0~2^m-1) 范围类的二进制数.
也就是说本来我们需要 O( n^2 )去匹配的, 现在状态压缩用二进制去等同表示后只需要 O( m^2 )去验证, 而 m 的范围为 1≤ m ≤8, 所以就大大降低了复杂度.
而验证该数 X 是答案的规则即是, 是否存在两个二进制数, 最后 或 的结果为 全 1 .(因为由于取得是最大序列的最小值, 如果两个序列或为 1, 那么这两个序列中必然能够选出一个大于等于 X 的序列)
例如: 下面两个序列红色表示对应位置的值更大(假设选取的 x 能作为答案).
- a b c d e -> 1 0 1 0 1
- A B C D E -> 0 1 1 1 0
- View Code
- code :
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- const int inf=0x3f3f3f3f;
- const int MAXN=3e5+10;
- int n,m,a[MAXN][10],mark[300],pos1,pos2,ans1,ans2;
- //bitmasks
- bool check(int x){
- pos1 = 0,pos2 = 0;
- memset(mark,0,sizeof(mark));
- for(int i=1;i<=n;i++){
- int tot = 0;
- for(int j=0;j<m;j++){
- if(x<=a[i][j]) tot += (1<<j);
- }
- mark[tot] = i;
- }
- for(int i=1;i<= (1<<m)-1;i++){
- for(int j=i; j<= (1<<m)-1;j++){
- if((i|j)== (1<<m)-1&&mark[i]&&mark[j]) {
- pos1 = mark[i];
- pos2 = mark[j];
- }
- }
- }
- return pos1&&pos2;
- }
- //binary search
- int BS(int l,int r){
- int mid;
- while(l<=r){
- mid = (l+r)>>1;
- if(check(mid)) l = mid+1,ans1 = pos1,ans2 = pos2;
- else r = mid-1;
- }
- return l;
- }
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)
- for(int j=0;j<m;j++)
- scanf("%d",&a[i][j]);
- int l=0,r=1e9;
- l = BS(l,r);
- printf("%d %d\n",ans1,ans2);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3395827.html