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

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

#include<bits/stdc++.h>
using namespace std;
int ansi,ansj,limit;
const int N=1e3+3;
const int M=3e5+5;
int a[M][10],pos[N],p[10];
int n,m;
bool check(int x){
    for(int i=0;i<=limit;i++)
        pos[i]=0;
    for(int i=1;i<=n;i++){
        int now=0;
        for(int j=1;j<=m;j++)
            if(a[i][j]>=x)
                now|=p[j];
        pos[now]=i;///状态now由第i个序列得来 
    }
    for(int i=0;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=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    limit=(1<<m)-1;
    for(int i=1;i<=m;i++){
        p[i]=1<<(i-1);
    }
    int l=0,r=1e9;
    while(l<=r){
        int midd=(l+r)>>1;
        if(check(midd))
            l=midd+1;
        else
            r=midd-1;
    }
    printf("%d %d
",ansi,ansj);
    return 0;
}

View Code

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+6;
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=0;
    while(x)
        ans+=tr[x],x-=(x&-x);
    return ans;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        pos[i]=m+1+i;
        minn[i]=maxx[i]=i;
        add(pos[i],1);
    }
    int nowpos=m+1;
    while(m--){
        int x;
        scanf("%d",&x);
        minn[x]=1;
        int num=Sum(pos[x]);
        maxx[x]=max(maxx[x],num);
        add(pos[x],-1);///消除这个位置的标记 
        pos[x]=nowpos--;
        add(pos[x],1);
    }
    for(int i=1;i<=n;i++){
        int num=Sum(pos[i]);
        maxx[i]=max(maxx[i],num);
    }
    for(int i=1;i<=n;i++)
        printf("%d %d
",minn[i],maxx[i]);
    return 0;
}

View Code