[二分答案 2-SAT验证 前缀后缀优化建图 线段树优化建图] Codeforces gym 100159 Facebook Hacker Cup 2012 I. Unfriending

二分答案 我们需要解决 对于一个点选了 一段不能选
这个裸建图肯定不行 那么我们用前后缀和线段树 优化建图
具体看代码 或 [二分答案 2-SAT验证 前后缀优化建图] Codeforces 587D #326 (Div. 1) D. Duff in Mafia

有一个细节 当冲突的个数超过一定大的值时是不可能有解的 这里dls教我说$1.2*10^6$ 所以其实不用线段树也问题不大？

这个题只有两个点 一个还是样例 时限确实100s 但让我卡常数卡的
后来实在不行 只能援力爆发 参考了杜老师的代码 因为随机数据答案很小 所以杜老师的二分是这么写的

 while (l+1<r) {
   int md=(l+r)>>1;
   if (l<10&&r>10) md=10;
   if (check(md)) l=md; else r=md;
 }

上自己的代码吧

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> abcd;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}
inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

const int N=5000005;
const int M=100005;

struct edge{
  int u,v,next;
}G[15000005];
int head[N],inum;
int _head[M],tmp;
inline void add(int u,int v){
  int p=++inum; G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p;
}
int pre[N],low[N],clk;
int scc[N],cnt; int Stack[N],pnt;
#define V G[p].v
inline void dfs(int u){
  pre[u]=low[u]=++clk; Stack[++pnt]=u;
  for (int p=head[u];p;p=G[p].next)
    if (!pre[V])
      dfs(V),low[u]=min(low[u],low[V]);
    else if (!scc[V])
      low[u]=min(low[u],pre[V]);
  if (low[u]==pre[u]){
    ++cnt;
    while (Stack[pnt]!=u) scc[Stack[pnt--]]=cnt; scc[Stack[pnt--]]=cnt; 
  }
}

int n,m,Tot;
int x[M],y[M],size[M],sum[M];
inline int pf(int idx,int t,int x){ return (n<<1)+(sum[idx-1]<<1)+x-1; }
inline int sf(int idx,int t,int x){ return (n<<1)+(sum[idx-1]<<1)+size[idx]+x-1; }

abcd ls[N];

inline bool Tarjan(){
  for (int i=0;i<Tot;i++) pre[i]=low[i]=scc[i]=0; pnt=cnt=clk=0;
  for (int i=0;i<Tot;i++)
    if (!pre[i])
      dfs(i);
  for (int i=0;i<2*n;i+=2)
    if (scc[i]==scc[i^1])
      return 0;
  return 1;
}

int rt[N];
inline void Build(int x,int l,int r){
  if (l==r){
    rt[x]=ls[l].second<<1|1; return;
  }
  rt[x]=Tot++; int mid=(l+r)>>1;
  Build(x<<1,l,mid); Build(x<<1|1,mid+1,r);
  add(rt[x],rt[x<<1]); add(rt[x],rt[x<<1|1]);
}
int ql,qr,qp;
inline void Link(int x,int l,int r){
  if (ql<=l && r<=qr){
    add(qp,rt[x]); return;
  }
  int mid=(l+r)>>1;
  if (ql<=mid) Link(x<<1,l,mid);
  if (qr>mid) Link(x<<1|1,mid+1,r);
}

int Cnt=0;
int pos1[N],pos2[N];

ll TOTOT;
int CNTNT;
inline bool check(int x){
  TOTOT+=inum; CNTNT++;
  int cot=0,lim=1.2e6;
  for (int i=1;i<=n;i++){
    pos1[i]=lower_bound(ls+1,ls+i,abcd(ls[i].first-x+1,0))-ls;
    pos2[i]=lower_bound(ls+i,ls+n+1,abcd(ls[i].first+x,0))-ls-1;
    cot+=i-pos1[i]; 
  }
  if (cot>lim) return Cnt++,0;
  for (int i=1;i<=n;i++){
    ql=pos1[i]; qr=i-1; qp=ls[i].second<<1;
    if (ql<=qr) Link(1,1,n);
    ql=i+1; qr=pos2[i]; qp=ls[i].second<<1;
    if (ql<=qr) Link(1,1,n);
  }
  return Tarjan();
}

int vst[N];

int main(){
  int T,Case=0,a,b,p;
  freopen("t.in","r",stdin);
  freopen("t2.out","w",stdout);
  read(T);
  while (T--){
    printf("Case #%d: ",++Case);
    read(n); read(m);
    read(x[0]); read(a),read(b),read(p);
    for (int i=1;i<n;i++) x[i]=((ll)x[i-1]*a+b)%p;
    for (int i=0;i<n;i++) vst[i]=0;
    for (int i=1;i<=m;i++){
      read(size[i]),read(y[1]),read(a),read(b); vst[y[1]]=1;
      for (int j=2;j<=size[i];j++) y[j]=((ll)y[j-1]*a+b)%n,vst[y[j]]=1;
      sort(y+1,y+size[i]+1); size[i]=unique(y+1,y+size[i]+1)-y-1;
      for (int j=1;j<=size[i];j++){
    if (j-1) add(pf(i,0,j),pf(i,0,j-1));
    add(pf(i,0,j),y[j]<<1);
    if (j+1<=size[i]) add(sf(i,0,j),sf(i,0,j+1));
    add(sf(i,0,j),y[j]<<1);
      }
      for (int j=1;j<=size[i];j++){
    if (j-1) add(y[j]<<1|1,pf(i,0,j-1));
    if (j+1<=size[i]) add(y[j]<<1|1,sf(i,0,j+1));
      }
      sum[i]=sum[i-1]+size[i];
    }
    Tot=(n<<1)+(sum[m]<<1);
    for (int i=0;i<n;i++) if (!vst[i]) add(i<<1|1,i<<1); 
    for (int i=0;i<n;i++) ls[i+1]=abcd(x[i],i);
    sort(ls+1,ls+n+1);
    Build(1,1,n);
    int L=0,R=ls[n].first+1,MID;
    for (int i=0;i<2*n;i++) _head[i]=head[i]; tmp=inum;
    while (L+1<R){
      MID=(L+R)>>1;
      if (L<10 && R>10) MID=10;
      if (check(MID))
    L=MID;
      else
    R=MID;
      for (int i=0;i<2*n;i++) head[i]=_head[i]; inum=tmp;
    }
    printf("%dn",L);
    for (int i=0;i<Tot;i++) head[i]=0; inum=0;
  }
  //printf("%lld %dn",TOTOT,CNTNT);
  return 0;
}

最后

以上就是光亮眼神为你收集整理的[二分答案 2-SAT验证 前缀后缀优化建图 线段树优化建图] Codeforces gym 100159 Facebook Hacker Cup 2012 I. Unfriending的全部内容，希望文章能够帮你解决[二分答案 2-SAT验证 前缀后缀优化建图 线段树优化建图] Codeforces gym 100159 Facebook Hacker Cup 2012 I. Unfriending所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。