Educational Codeforces Round 80 (Rated for Div. 2)D E

D枚举子集

题：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）

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

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

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

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

#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+;

int a[];

int maxx[M],maxid[M];

int main(){

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++)

            scanf("%d",&a[j]);

        for(int j=;j<(<<m);j++){

            int minn=inf;

            for(int k=;k<m;k++){

                if(j&(<<k))

                    minn=min(minn,a[k+]);

            }

            if(minn>=maxx[j]){

                maxx[j]=minn;

                maxid[j]=i;

            }

        }

    }

    int ans=-,x,y;

    for(int i=;i<(<<m);i++){

        if(ans<min(maxx[i],maxx[(<<m)--i])){

            ans=min(maxx[i],maxx[(<<m)--i]);

            x=maxid[i];

            y=maxid[(<<m)--i];

        }

    }

    printf("%d %d",x,y);

    return ;

}

分析2：二分答案，将满足条件的位置用状压记录下来更新即可。

#include<bits/stdc++.h>

using namespace std;

int ansi,ansj,limit;

const int N=1e3+;

const int M=3e5+;

int a[M][],pos[N],p[];

int n,m;

bool check(int x){

    for(int i=;i<=limit;i++)

        pos[i]=;

    for(int i=;i<=n;i++){

        int now=;

        for(int j=;j<=m;j++)

            if(a[i][j]>=x)

                now|=p[j];

        pos[now]=i;///状态now由第i个序列得来

    }

    for(int i=;i<=limit;i++)

        for(int j=i;j<=limit;j++){

            if((i|j)==limit&&pos[i]&&pos[j]){

                return ansi=pos[i],ansj=pos[j],true;

            }

        }

    return false;

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

            scanf("%d",&a[i][j]);

    limit=(<<m)-;

    for(int i=;i<=m;i++){

        p[i]=<<(i-);

    }

    int l=,r=1e9;

    while(l<=r){

        int midd=(l+r)>>;

        if(check(midd))

            l=midd+;

        else

            r=midd-;

    }

    printf("%d %d\n",ansi,ansj);

    return ;

}

E BIT

题：https://codeforces.com/contest/1288/problem/E

题意：对于从1~n的一个序列，给定m个操作，每个操作给定一个数x，含义为将x提到序列的第一个位置，问每个数可能的最小最大位置是多少

分析：最小位置俩种可能，有被操作过答案就是1，否则就是本身数值，至于最大值，我们考虑事先考虑将n个数挪后m+1个位置（因为最多m个操作），目的是留出m个位置给要提出来的数；

　　　然后我每次提出来一个数就统计一下这个数前面有多少个数，取max之后BIT更新一下，一直重复m步操作。

#include<bits/stdc++.h>

using namespace std;

const int M=1e6+;

int pos[M],minn[M],maxx[M],tr[M];

void add(int x,int c){

    while(x<M)

        tr[x]+=c,x+=(x&-x);

}

int Sum(int x){

    int ans=;

    while(x)

        ans+=tr[x],x-=(x&-x);

    return ans;

}

int main(){

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++){

        pos[i]=m++i;

        minn[i]=maxx[i]=i;

        add(pos[i],);

    }

    int nowpos=m+;

    while(m--){

        int x;

        scanf("%d",&x);

        minn[x]=;

        int num=Sum(pos[x]);

        maxx[x]=max(maxx[x],num);

        add(pos[x],-);///消除这个位置的标记

        pos[x]=nowpos--;

        add(pos[x],);

    }

    for(int i=;i<=n;i++){

        int num=Sum(pos[i]);

        maxx[i]=max(maxx[i],num);

    }

    for(int i=;i<=n;i++)

        printf("%d %d\n",minn[i],maxx[i]);

    return ;

}

巴特西

Educational Codeforces Round 80 (Rated for Div. 2)D E

最新文章

热门文章