Educational Codeforces Round 80 (Rated for Div. 2)思维状压

题:https://codeforces.com/contest/1288/problem/D
题意:给定n个序列,每个序列m个数,求第i个和第j个序列组成b序列,b序列=max(a[i][k],a[j][k]),使得b序列最小值最大化,求达成条件的 i 和 j (i可等于j)

分析:因为m<=8,所以我们考虑对每个序列的m个数进行状压。

   这题的状压是,“1”状态,表示取max取到了这个位置,“0”就表示max没取到这个位置。

   因为题目要求很明确,要b序列最小值最大化,所以我们不用考虑取max后哪个数覆盖哪个数,只需考虑最小值应该是第几个序列即可

   然后就对应俩个序列进行最大化匹配即可

Educational Codeforces Round 80 (Rated for Div. 2)思维状压
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int M=1e3+5;
int a[10];
int maxx[M],maxid[M];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            scanf("%d",&a[j]);
        for(int j=0;j<(1<<m);j++){
            int minn=inf;
            for(int k=0;k<m;k++){
                if(j&(1<<k))
                    minn=min(minn,a[k+1]);
            }
            if(minn>=maxx[j]){
                maxx[j]=minn;
                maxid[j]=i;
            }
        }
    }
    int ans=-1,x,y;
    for(int i=0;i<(1<<m);i++){
        if(ans<min(maxx[i],maxx[(1<<m)-1-i])){
            ans=min(maxx[i],maxx[(1<<m)-1-i]);
            x=maxid[i];
            y=maxid[(1<<m)-1-i];
        }
    }
    printf("%d %d",x,y);
    return 0;
}
View Code
上一篇:AGC40.Two Contests


下一篇:[violet]蒲公英题解