ZigZagK的博客
[霍尔定理+线段树]LOJ6062(2017 山东一轮集训 Day2)【Pair】题解
2018年6月1日 14:11
LOJ
查看标签

题目概述

两个数 $x,y​$ 可以匹配定义为 $x+y\ge H​$ 。现在给出 $\{a_n\}​$ 和 $\{b_m\}​$ ,问 $\{a_n\}​$ 有多少个连续子序列满足:存在一种方法使得连续子序列与 $\{b_m\}​$ 两两匹配。

解题报告

我怎么霍尔定理都不会啊,考前临时抱佛脚。

霍尔定理:若二分图 $X,Y$ 存在完美匹配,则对于 $X$ 的任意子集 $S$ ,定义 $M(S)$ 表示 $S$ 连向的点的集合,均满足 $|S|\le |M(S)|$ 。yy一下还是挺显然的,反正我不会证明。


知道霍尔定理就可做了。题目显然就是要我们验证 $\{a_n\}$ 的 $n-m$ 个连续子序列是否与 $\{b_m\}$ 有完美匹配。我们可以先求出 $num_i=|\{a_i+b_j\ge H\}|$ ,然后利用霍尔定理验证。

但是我们不可能指数级枚举子集验证,所以观察下性质可以发现:如果 $a_i\ge a_j$ ,则 $M(i)>M(j)$ 。也就是说对于一个集合,决定这个集合的 $M$ 集合的点是 $a_{max}$ 。

这就很Easy了,对于一个排序之后的连续子序列 $\{c_m\}$ ,我们要验证 $\forall num_i\ge i$ ,也就是说 $min\{num_i-i\}\ge 0$ ,用线段树维护最小值即可。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=150000;

int n,m,H,a[maxn+5],b[maxn+5],ID[maxn+5],rk[maxn+5],ans;
int num[maxn+5],INF,MIN[(maxn<<2)+5],tag[(maxn<<2)+5];

inline bool cmp (const int &A,const int &B) {return a[A]<a[B];}
#define Addtag(k,p) (MIN[p]+=(k),tag[p]+=(k))
#define Pushdown(p) (tag[p]?(Addtag(tag[p],(p)<<1),Addtag(tag[p],(p)<<1|1),tag[p]=0):0)
inline void Insert(int L,int R,int k,int l=1,int r=n,int p=1){
    if (R<l||r<L) return;if (L<=l&&r<=R) {Addtag(k,p);return;}Pushdown(p);int mid=l+(r-l>>1);
    Insert(L,R,k,l,mid,p<<1);Insert(L,R,k,mid+1,r,p<<1|1);MIN[p]=min(MIN[p<<1],MIN[p<<1|1]);
}
inline int Find(int x,int L=1,int R=m) {
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        b[mid]>=x?R=mid-1:L=mid+1;return L;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&m,&H);memset(MIN,63,sizeof(MIN));INF=MIN[0];
    for (int i=1;i<=m;i++) scanf("%d",&b[i]);
    for (int i=1;i<=n;i++) scanf("%d",&a[ID[i]=i]);
    sort(ID+1,ID+1+n,cmp);sort(b+1,b+1+m);
    for (int i=1;i<=n;i++) rk[ID[i]]=i,num[i]=m-Find(H-a[i])+1;
    for (int i=1;i<=m;i++) Insert(rk[i],rk[i],num[i]-1-INF),Insert(rk[i]+1,n,-1);ans+=MIN[1]>=0;
    for (int i=m+1;i<=n;i++){
        Insert(rk[i-m],rk[i-m],INF-num[i-m]+1);Insert(rk[i-m]+1,n,1);
        Insert(rk[i],rk[i],num[i]-1-INF);Insert(rk[i]+1,n,-1);ans+=MIN[1]>=0;
    }
    return printf("%d\n",ans),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!