Hall定理小记
前言
Hall定理：一张二分图有完美匹配(即最大匹配为 \(\min\{|X|,|Y|\}\) )
当且仅当任意一个点集 \(X'\) 与所有能直接到达 \(X'\) 的点集 \(Y'\)，
也就是 \(X'\) 与邻域 \(N(X')\) 所组成的导出子图有完美匹配
也就是 \(\forall X',|X'|\leq |N(X')|\)
推论：一张二分图的最大匹配为 \(\min\{|X|-\max\{|X'|-|Y'|\},|Y|\}\)
HDU 6667 Roundgod and Milk Tea
题目
有 \(n\) 个班级(\(n\leq 2\times 10^5\))，每个班级有 \(a_i\) 名学生，该班共生产 \(b_i\) 杯奶茶，
每个学生只能购买其它班级的奶茶，问最多有多少个学生能够喝到奶茶
分析
可以发现直接建图就是一个二分图求最大匹配，但肯定会超时。
根据推论，考虑让 \(|X'|-|Y'|\) 尽量大。
分类讨论一下，只有 \(X'\) 仅为一个班级时，这个值最大。
那么直接 \(O(n)\) 求 \(\max\{a_i-(s-b_i)\}\) 即可
代码
#include
#include
using namespace std;
const int N=200011;
typedef long long lll;
int n,a[N],b[N]; lll stu,tea,ans;
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
void print(lll ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
lll min(lll a,lll b){return ab?a:b;}
int main(){
for (int T=iut();T;--T){
n=iut(),ans=stu=tea=0;
for (int i=1;i<=n;++i){
a[i]=iut(),b[i]=iut();
stu+=a[i],tea+=b[i];
}
for (int i=1;i<=n;++i)
ans=max(ans,a[i]-(tea-b[i]));
print(min(stu-ans,tea)),putchar(10);
}
return 0;
}
AT2645 [ARC076D] Exhausted?
题目
有 \(n\) 个人，\(m\) 把椅子，每个人只愿意坐在第 \(l_i\) 把或其前面或者第 \(r_i\) 把或其后面，
问至少添加多少张椅子才能使所有人就坐。\(n,m\leq 2*10^5\)
分析（反悔贪心）
可以发现答案就是 \(n-\) 最大匹配，但是由于条件的特殊性可以用反悔贪心实现。
按 \(r_i\) 降序，再 \(l_i\) 升序的顺序排序，用一个双指针从后往前扫描可用的椅子。
如果后面的椅子不够用，那么抽出其中 \(l_i\) 最大的一个人的椅子给当前人使用，可以用大根堆实现。
然后没有椅子的人再从前往后扫描可用的椅子，没有椅子就只能添加椅子。
代码（反悔贪心）
#include
#include
#include
#include
using namespace std;
const int N=200011;
struct rec{int l,r;}a[N];
int n,m,tot,ans,b[N],L,R;
priority_queueq;
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
bool cmp(rec x,rec y){
if (x.r!=y.r) return x.r>y.r;
return x.l=a[i].r&&L<=R) --R;
else b[++tot]=q.top(),q.pop();
}
sort(b+1,b+1+tot);
for (int i=1;i<=tot;++i)
if (L<=b[i]&&L<=R) ++L; else ++ans;
return !printf("%d",ans);
}
分析（Hall定理）
根据推论，答案为 \(\max\{|X'|-|Y'|,|X|-|Y|\}\)
后面单独写出来主要是对 \(n-m\) 取最大值。
观察到这个邻域就是区间的并，比较难求，将其补集转化为区间的交。
那也就是令 \(R-L-1+|X'|-m\) 最大，其中 \(X'\) 中的任意区间满足 \(l_i\leq L 且 R\leq r_i\)
那么按照 \(l_i\) 升序排序，然后枚举左端点，用线段树维护最大值 \(R+|X'|\) 即可。
代码（Hall定理）
#include
#include
#include
using namespace std;
const int N=200011;
struct rec{int l,r;}a[N];
int w[N<<2],lazy[N<<2],n,m,ans;
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
int max(int a,int b){return a>b?a:b;}
bool cmp(rec x,rec y){
if (x.l!=y.l) return x.ly.r;
}
void build(int k,int l,int r){
w[k]=r;
if (l==r) return;
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
void update(int k,int l,int r,int x,int y){
if (l==x&&r==y) {++w[k],++lazy[k]; return;}
int mid=(l+r)>>1;
if (lazy[k]){
lazy[k<<1]+=lazy[k],lazy[k<<1|1]+=lazy[k];
w[k<<1]+=lazy[k],w[k<<1|1]+=lazy[k],lazy[k]=0;
}
if (y<=mid) update(k<<1,l,mid,x,y);
else if (x>mid) update(k<<1|1,mid+1,r,x,y);
else update(k<<1,l,mid,x,mid),update(k<<1|1,mid+1,r,mid+1,y);
w[k]=max(w[k<<1],w[k<<1|1]);
}
int query(int k,int l,int r,int x,int y){
if (l==x&&r==y) return w[k];
int mid=(l+r)>>1;
if (lazy[k]){
lazy[k<<1]+=lazy[k],lazy[k<<1|1]+=lazy[k];
w[k<<1]+=lazy[k],w[k<<1|1]+=lazy[k],lazy[k]=0;
}
if (y<=mid) return query(k<<1,l,mid,x,y);
else if (x>mid) return query(k<<1|1,mid+1,r,x,y);
else return max(query(k<<1,l,mid,x,mid),query(k<<1|1,mid+1,r,mid+1,y));
}
int main(){
n=iut(),m=iut();
for (int i=1;i<=n;++i) a[i]=(rec){iut(),iut()};
sort(a+1,a+1+n,cmp);
build(1,1,m+1);
for (int i=1;i<=n;++i){
update(1,1,m+1,a[i].l+1,a[i].r);
ans=max(ans,query(1,1,m+1,a[i].l+1,a[i].r)-a[i].l-1-m);
}
return !printf("%d",max(ans,n-m));
}
CF981F Round Marriage
题目
\(n\) 个新郎和 \(n\) 个新娘围成一个环，长度为 \(L\)，第 \(i\) 个新郎位置为 \(a_i\),
第 \(i\) 个新娘位置为 \(b_i\),需要将他们两两配对，最小化新郎和新娘距离的最大值。
分析
二分答案转为判定是否为最大匹配，直接用 \(Hall\) 定理就是要保证 \(|X'|\leq |Y'|\)
在本题即转化为 \(j-i+1\leq r-l+1\)，也就是要保证 \(r-j\geq \max\{l-i\}\)
将环断为链，然后用双指针维护即可
由于两个都是环，所以让新郎复制一份，新娘先复制一份，在头尾各复制一份
代码
#include
#include
#include
using namespace std;
const int N=200011; typedef long long lll;
lll a[N<<1],b[N<<2]; int n,len;
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
int max(int a,int b){return a>b?a:b;}
bool check(int mid){
int head=1,tail=1,mx=0xcfcfcfcf;
for (int i=1;i<=2*n;++i){
while (head<=4*n&&b[head]>1;
while (l>1;
if (check(mid)) r=mid;
else l=mid+1;
}
return !printf("%d",l);
}
洛谷 3488 [POI2009]LYZ-Ice Skates
题目
有 \(n\) 种尺码的鞋子，\(m\) 次操作，每种鞋子有 \(k\) 双，这 \(n\) 种尺码的队员分别有 \(a_i\) 个，初始为0。
对于一个尺码为 \(x\) 的队员可以穿的鞋子尺码范围为 \([x,x+d]\)
每次操作加入或者删除同一尺码的若干名队员，问在场的队员是否都能穿上鞋子。
\(n,m,d\leq 5*10^5,k\leq 10^9\)
分析
根据Hall定理，也就是任意队员的子集都能穿上鞋子，
考虑连续尺码一定比不连续尺码的差值 \((|X'|-|Y'|)\) 更大
\(\forall 1\leq l\leq r\leq n,\sum_{i=l}^r{a_i}\leq (r-l+1+d)*k\)
也就是 \(\sum_{i=l}^r(a_i-k)\leq k*d\)
那也就是最大子段和不超过 \(k*d\)
当 \(r+d>n\) 时，也就是当 \(r=n\) 时左边才可能最大，
那么 \(\sum_{i=l}^n{a_i}+l*k\leq (n+1)*k\)
维护前面这一坨的最大值即可
代码
#include
#include
using namespace std;
const int N=500011; typedef long long lll; int n,m,d;
lll A,w[N<<2],s[N<<2],lazy[N<<2],_w[N<<2],lmx[N<<2],rmx[N<<2];
int iut(){
int ans=0,f=1; char c=getchar();
while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans*f;
}
void build(int k,int l,int r){
w[k]=s[k]=-(r-l+1)*A,_w[k]=r*A;
if (l==r) return;
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
lll max(lll a,lll b){return a>b?a:b;}
void update(int k,int l,int r,int x,int y){
if (l==r){
s[k]+=y,w[k]+=y;
if (s[k]>0) lmx[k]=rmx[k]=s[k];
else lmx[k]=rmx[k]=0;
return;
}
int mid=(l+r)>>1;
if (x<=mid) update(k<<1,l,mid,x,y);
else update(k<<1|1,mid+1,r,x,y);
rmx[k]=max(rmx[k<<1|1],s[k<<1|1]+rmx[k<<1]);
lmx[k]=max(lmx[k<<1],s[k<<1]+lmx[k<<1|1]),s[k]=s[k<<1]+s[k<<1|1];
w[k]=max(max(w[k<<1],w[k<<1|1]),rmx[k<<1]+lmx[k<<1|1]);
}
void upd(int k,int l,int r,int x,int y,int z){
if (l==x&&r==y) {_w[k]+=z,lazy[k]+=z; return;}
int mid=(l+r)>>1;
if (lazy[k]){
lazy[k<<1]+=lazy[k],lazy[k<<1|1]+=lazy[k];
_w[k<<1]+=lazy[k],_w[k<<1|1]+=lazy[k],lazy[k]=0;
}
if (y<=mid) upd(k<<1,l,mid,x,y,z);
else if (x>mid) upd(k<<1|1,mid+1,r,x,y,z);
else upd(k<<1,l,mid,x,mid,z),upd(k<<1|1,mid+1,r,mid+1,y,z);
_w[k]=max(_w[k<<1],_w[k<<1|1]);
}
int main(){
n=iut(),m=iut(),A=iut(),d=iut();
build(1,1,n);
for (int i=1;i<=m;++i){
int x=iut(),y=iut();
update(1,1,n,x,y),upd(1,1,n,1,x,y);
if (w[1]<=A*d&&_w[1]<=(n+1ll)*A) puts("TAK");
else puts("NIE");
}
return 0;
}
未完待续