CF1710E

Rainbow_qwq · 2022-07-25 21:35:07 · 题解

首先显然地二分答案，\le x 的为 Alice 的胜点，>x 的为 Bob 的胜点，连边会发现是个二分图，于是就是二分图博弈。

二分图博弈是每个点只能经过一次，题目有个 1000 次，但我们猜它就等于一次的情况。

为了分析方便把 a,b 都排成升序，这样 01 矩阵会变成一条折线，左上方都是 0 右下方都是 1 这样子。

现在要判断 (x,y) 是哪方胜，根据二分图博弈结论就是判断去掉这个点最大匹配是否减少。

最大匹配感觉不太好做..转成最大独立集？这样就变成了每行、每列只能选 0 或只能选 1。

手玩一下，瞎调整来感受怎样选点最优。显然是上面的若干行列选 0，下面的若干行列选 1。于是方案就是选一个点 (x,y)，选上所有 (\le x,\le y) 的白点和 (>x,>y) 的黑点。

这个 y 根据 x 单调，于是双指针即可。

去掉一个点大概也是这样选点。其实应该把抠掉的那一行/列移到边界上，但是不移的话也能过，大概是因为判断的结果没有区别吧。

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

int n,m,a[maxn],b[maxn],pa,pb;

int ca[maxn],sa[maxn],posa[maxn],posb[maxn],cb[maxn],sb[maxn],mid;
int F(int x,int y,int o){
    int res=0,p;
    if(ca[x]>=y)res+=x*y;
    else p=posa[y],res+=p*y+sa[x]-sa[p];
    if(cb[y+1]>=n-x)res+=(n-x)*(m-y);
    else p=posb[n-x],res+=(n-x)*(m-p+1)+sb[y+1]-sb[p];
    res-=o*(pa<=x&&pb<=y&&a[pa]+b[pb]<=mid);
    res-=o*(pa>x&&pb>y&&a[pa]+b[pb]>mid);
    return res;
}
bool chk()
{
    int j=m;
    For(i,1,n){
        while(j&&a[i]+b[j]>mid)posa[j]=i-1,--j;
        ca[i]=j,sa[i]=sa[i-1]+ca[i];
    }
    while(j)posa[j]=n,--j;

    j=1;
    cb[m+1]=n+1;
    posb[n+1]=m+1;
    Rep(i,m,1){
        while(j<=n&&b[i]+a[j]<=mid)posb[n-j+1]=i+1,++j;
        cb[i]=n-j+1,sb[i]=sb[i+1]+cb[i];
    }
    while(j<=n)posb[n-j+1]=1,++j;

    j=1;
    int res1=sb[1],res2=sb[1]-(a[pa]+b[pb]>mid);
    For(i,1,n){
        while(j<m&&F(i,j,0)<=F(i,j+1,0))++j;
        res1=max(res1,F(i,j,0));
    }
    j=1;
    For(i,1,n){
        while(j<m&&F(i,j,1)<=F(i,j+1,1))++j;
        res2=max(res2,F(i,j,1));
    }
    return res1==res2;
}

signed main()
{
    n=read(),m=read();
    For(i,1,n)a[i]=read();
    For(i,1,m)b[i]=read();
    int a1=a[1],b1=b[1];
    sort(a+1,a+n+1),sort(b+1,b+m+1);
    pa=lower_bound(a+1,a+n+1,a1)-a,pb=lower_bound(b+1,b+m+1,b1)-b;
    int l=0,r=a[pa]+b[pb],res=r;
    while(l<=r){
        mid=l+r>>1;
        if(chk())res=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<res;
    return 0;
}