【题解】 bzoj3693: 圆桌会议 （线段树+霍尔定理）

2023-08-08 17:17:22

bzoj3693

Solution:

  • 显然我们可以把人和位置抽象成点，就成了一个二分图，然后就可以用霍尔定理判断是否能有解
  • 一开始我随便YY了一个\(check\)的方法：就是每次向后一组，我们就把那一组可以位置标记为\(true\)，用线段树存储，比如我们处理到了第\(i\)组，线段树里面就是前面\(i\)组可以放在那一些位置上，\(check\)总共可以放的位置数目不小于前\(i\)组总人数就继续，否则输出\(No\)，这样显然是错的，很容易举出反例，于是我进行了一下的神奇操作。
  • 我们先按照原小组顺序\(check\)一遍，然后把每组的可放位置数目从小到大排序（第一关键字）且把每组人数从小到大排序（第二关键字）做一遍\(check\)，最后每组的可放位置数目从小到大排序（第一关键字）且把每组人数从大到小排序（第二关键字）做一遍\(check\)，三次都没输出\(No\)，输出\(Yes\)。结果\(A\)掉了qwq。

（以上为胡言乱语，假做法，如果有大佬能解释其中正确原理将不胜感激），下面我们来讲正常做法

  • 首先抽象成二分图是很显然的，然后我们就是要允许的时间范围内\(check\)

    以下，座位的左右我们用\(L,R\)表示，小组可以方的位置左右我们用\(l,r\)表示

假设所有\(l<r\)，也就是没有跨过环的断点那个位置的情况，显然可以拉成一条链

  • 我们考虑\(L \rightarrow R\)区间，如果这个区间左右都是空的（没有小组站位置），显然是不用考虑的，所以我们就只用考虑\(L,R\)为某个小组的左边(\(l\))和右边(\(r\))
  • 这个区间的位置个数是\(R-L+1\)，我们令\(S\)为\(l,r\)均在\(L,R\)范围内的小组的人数和，那么如果\(S>R-L+1\)，显然里面的小组无法满足安排位置的，这时我们就可以输出\(No\)。
  • 上面的式子我们可以变一下形式\(\rightarrow S+L>R+1\)，这样我们可以将操作按照\(R\)从小到大排序，\(L\)从小到大排序（第二关键字）
  • 所以我们就可以不断向后推进小组，得到新的\(R\)(也就是这个小组的\(r\))，我们每到一个\(R\)，先更新线段树里面的值，然后\(Check\)
  • 所有的\(L\)（这个\(L\)一定会是小于等于这个小组的\(l\)，这个很显然，因为只与在\(R\)前面的\(l\)有关）进行\(check\)，但这样就很浪费时间，我们就只用找出前面的最大值判断就可以了。

然后就是跨越了环的情况

  • 我们可以把它拉成链，在多加一倍就可以了，如果还是满足\(l<r\)的情况，就拆成两个操作\(l,r\)和\(l+m,r+m\)
  • 这个还要注意，以为实际上这个环长度只有\(m\)，所以要确保找出来的前面的最大值到\(R\)的距离小于等于\(m\)。
  • 还有一个地方就是，我们要提前判断他的人数总数是不是大于了\(m\)，和小组的人数是不是大于位置个数了，不满足就直接输出\(No\)

原因如下：存在反例，如：m=5，两个条件：[1,3]，a1=2；[3,2]，a2=4，上述方法会判定为能满足。。

因为在查询[3,7]时，[1,3]和[6,8]均不包含于[3,7]，事实上是包含的([3,3]∪[6,7])。。

这种情况是把原区间从中间断开分到了两端。。

此时查询区间总长一定为m(两端能接成一个区间)，故事先特判总区间(所有ai之和<=m)即可

简单来说：有可能在询问[Li,Ri+m] (且Ri=Li-1)一类的区间时，[Li,Ri]、[Li+m,Ri+m]的这种区间被断在了首尾两端，不过这种询问区间长度都是m，开始时直接特判ai总和是否小于m即可

摘自leolyun\(、\)cdsszjj

  • By the way,这个题的\(m\)过大，我们还需要一个\(Hash\)
  • 就是这样了啦，喵～

Code:

正解\(AC\):

//It is coded by ning_mew on 7.14

#include<bits/stdc++.h>

#define ls(x) node[x].ls

#define rs(x) node[x].rs

#define l(x) opt[x].l

#define r(x) opt[x].r

#define ad(x) opt[x].ad

using namespace std;

const int N=1e5+7,maxm=1e9+7;

int n,m,T,cnt=1,tot=0,dfn=0,ont=1;

int rehash[N*8],box[N*8];

struct Opt{int l,r,ad;}opt[N*2];

struct Node{

  int ls,rs,maxx,lazy;

  void clear(){ls=0;rs=0;maxx=0;lazy=0;}

}node[N*8];

bool cmp(const Opt &x,const Opt &y){

  if(x.r!=y.r)return x.r<y.r;return x.l<y.l;

}

bool cmp2(const int &x,const int &y){return x<y;}

void Clear(){

  for(int i=1;i<=cnt;i++)node[i].clear();

  tot=0;dfn=0;ont=0;cnt=1;return;

}

void update(int num){node[num].maxx=max(node[ls(num)].maxx,node[rs(num)].maxx);return;}

void Build(int num,int nl,int nr){

  if(nl==nr){node[num].maxx=rehash[nl];return;}

  int mid=(nl+nr)/2;

  ls(num)=++cnt;Build(ls(num),nl,mid);

  rs(num)=++cnt;Build(rs(num),mid+1,nr);

  update(num);

}

void pushdown(int num,int nl,int nr){

  int mid=(nl+nr)/2,lz=node[num].lazy;node[num].lazy=0;

  node[ls(num)].maxx+=lz,node[ls(num)].lazy+=lz;

  node[rs(num)].maxx+=lz;node[rs(num)].lazy+=lz;

  update(num);return;

}

void add(int num,int nl,int nr,int ql,int qr,int ad){

  if(ql<=nl&&nr<=qr){node[num].maxx+=ad;node[num].lazy+=ad;return;}

  if(nr<ql||qr<nl)return;

  int mid=(nl+nr)/2;pushdown(num,nl,nr);

  add(ls(num),nl,mid,ql,qr,ad);

  add(rs(num),mid+1,nr,ql,qr,ad);

  update(num);

}

int quary(int num,int nl,int nr,int ql,int qr){

  if(ql<=nl&&nr<=qr)return node[num].maxx;

  if(nr<ql||qr<nl)return -maxm;

  int mid=(nl+nr)/2;pushdown(num,nl,nr);

  return max(quary(ls(num),nl,mid,ql,qr),quary(rs(num),mid+1,nr,ql,qr));

}

int Hash(int x){

  int l=1,r=dfn,mid,ans=maxm,TT=0;

  while(l<=r){

    if(l==r)TT++;if(TT==2)break;

    mid=(l+r)>>1;

    if(rehash[mid]>=x)ans=min(ans,mid),r=mid-1;

    else l=mid+1;

  }return ans;

}

void work(){

  Clear();

  scanf("%d%d",&n,&m);int S=0;

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

    int l,r,ad; scanf("%d%d%d",&l,&r,&ad);S+=ad;

    if(l<=r){

      box[++tot]=l;box[++tot]=r;box[++tot]=l+m;box[++tot]=r+m;

      opt[++ont].l=l;opt[ont].r=r;opt[ont].ad=ad;l+=m;r+=m;

      opt[++ont].l=l;opt[ont].r=r;opt[ont].ad=ad;

    }else{

      r+=m;box[++tot]=r;box[++tot]=l;

      opt[++ont].l=l;opt[ont].r=r;opt[ont].ad=ad;

    }

  }

  if(S>m){printf("No\n");return;}

  sort(box+1,box+tot+1,cmp2);box[0]=-maxm;

  sort(opt+1,opt+ont+1,cmp);

  for(int i=1;i<=tot;i++)if(box[i]!=box[i-1]){rehash[++dfn]=box[i];}

  Build(1,1,dfn);

  int front=1;

  /////////front!!!!!

  for(int i=1;i<=ont;i++){

    if(r(i)-l(i)+1<ad(i)){printf("No\n");return;}

    while(1){if(r(i)-rehash[front]+1<=m)break;else front++;}

    add(1,1,dfn,1,Hash(l(i)),ad(i));

    if(quary(1,1,dfn,front,Hash(l(i)))>r(i)+1){printf("No\n");return;}

  }printf("Yes\n");return;

}

int main(){

  scanf("%d",&T);

  for(int i=1;i<=T;i++)work();

  return 0;

}

假做法\(AC\):

//It is coded by ning_mew on 7.14

#include<bits/stdc++.h>

#define ls(x) node[x].ls

#define rs(x) node[x].rs

using namespace std;

const int maxn=1e9+7,_=1e5+7;

int T,n,m,cnt=1;

struct Opt{int l,r,ad;}opt[_];

struct Node{

  int ls,rs,sum;bool lazy;

  Node(){ls=rs=sum=0;lazy=false;}

  void clear(){ls=rs=sum=0;lazy=false;}

}node[maxn/100];

void clear(){

  for(int i=1;i<=cnt;i++){node[i].clear();}return;

}

void pushdown(int num,int nl,int nr){

  if(!node[num].lazy)return;

  int mid=(nl+nr)/2; node[num].lazy=false;

  if(ls(num))node[ls(num)].lazy=true,node[ls(num)].sum=(mid-nl+1);

  else ls(num)=++cnt,node[ls(num)].lazy=true,node[ls(num)].sum=(mid-nl+1);

  if(rs(num))node[rs(num)].lazy=true,node[rs(num)].sum=(nr-mid);

  else rs(num)=++cnt,node[rs(num)].lazy=true,node[rs(num)].sum=(nr-mid);

}

void update(int num){

  node[num].sum=0;

  if(ls(num))node[num].sum+=node[ls(num)].sum;

  if(rs(num))node[num].sum+=node[rs(num)].sum;

  return;

}

void add(int num,int nl,int nr,int ql,int qr){

  //cout<<num<<' '<<nl<<' '<<nl<<' '<<nr<<endl;

  if(ql<=nl&&nr<=qr){node[num].sum=nr-nl+1;node[num].lazy=true;return;}

  if(nr<ql||qr<nl)return;

  int mid=(nl+nr)>>1;

  pushdown(num,nl,nr);

  if(ls(num))add(ls(num),nl,mid,ql,qr);

  else ls(num)=++cnt,add(ls(num),nl,mid,ql,qr);

  if(rs(num))add(rs(num),mid+1,nr,ql,qr);

  else rs(num)=++cnt,add(rs(num),mid+1,nr,ql,qr);

  update(num);return;

}

int quary(int num,int nl,int nr,int ql,int qr){

  if(nr<ql||qr<nl)return 0;

  if(ql<=nl&&nr<=qr)return node[num].sum;

  int mid=(nl+nr)/2,ans=0;

  pushdown(num,nl,nr);

  if(ls(num))ans+=quary(ls(num),nl,mid,ql,qr);

  if(rs(num))ans+=quary(rs(num),mid+1,nr,ql,qr);

  return ans;

}

bool cmp1(const Opt &x,const Opt &y){

  int xx=(x.r-x.l+1+m)%m,yy=(y.r-y.l+1+m)%m;

  if(xx!=yy)return xx<yy;return x.ad>y.ad;

}

bool cmp2(const Opt &x,const Opt &y){

  int xx=(x.r-x.l+1+m)%m,yy=(y.r-y.l+1+m)%m;

  if(xx!=yy)return xx<yy;return x.ad<y.ad;

}

void work(){

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

  for(int i=1;i<=n;i++){scanf("%d%d%d",&opt[i].l,&opt[i].r,&opt[i].ad);}

  clear();

  int l,r,ad,SS=0;cnt=1;

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

    l=opt[i].l;r=opt[i].r;ad=opt[i].ad; SS+=ad;

    if(ad>(r-l+1+m)%m){printf("No\n");return;}

    if(l<=r)add(1,0,m-1,l,r);

    else add(1,0,m-1,l,m-1),add(1,0,m-1,0,r);

    if(node[1].sum<SS){printf("No\n");return;}

  }

  clear();sort(opt+1,opt+n+1,cmp1); SS=0;cnt=1;

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

    l=opt[i].l;r=opt[i].r;ad=opt[i].ad;

    SS+=ad;

    if(ad>(r-l+1+m)%m){printf("No\n");return;}

    if(l<=r)add(1,0,m-1,l,r);

    else add(1,0,m-1,l,m-1),add(1,0,m-1,0,r);

    if(node[1].sum<SS){printf("No\n");return;}

  }

  clear();sort(opt+1,opt+n+1,cmp2);SS=0;cnt=1;

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

    l=opt[i].l;r=opt[i].r;ad=opt[i].ad; SS+=ad;

    if(ad>(r-l+1+m)%m){printf("No\n");return;}

    if(l<=r)add(1,0,m-1,l,r);

    else add(1,0,m-1,l,m-1),add(1,0,m-1,0,r);

    if(node[1].sum<SS){printf("No\n");return;}

  }printf("Yes\n");return;

}

int main(){

  scanf("%d",&T);

  for(int i=1;i<=T;i++)work();

  return 0;

}

我知道这个是权限题，但我们穷孩子就只能用\(bzoj\)发下来的数据辣悄悄的啊

博主蒟蒻，随意转载。但必须附上原文链接：http://www.cnblogs.com/Ning-Mew/，否则你会终生找不到妹子！！！

上一篇：Swift 2.x -> Swift 3.0


下一篇：Linux操作系统原理