[BZOJ 2653]middle

前几天想用Github+org-mode替代这个博客,后来想了想,还是算了吧。毕竟博客对大家更方便。

这个题真不愧是陈老师的题啊……exciting!

首先我们看到左端点在[tex][a,b][/tex],右端点在[tex][c,d][/tex],一股GSS5的气味扑来?

为了方便,我们先将序列离散化。然后我们将序列中大于等于x的值变为1,小于x的值变为-1,则某段区间的区间和若大于等于0,则该区间的中位数大于等于x,反之则其中位数小于x(注意,此题的中位数定义比较奇怪)。

然后我们可以对每个x建一棵树,然后二分答案,对于每个答案在对应的树上跑一遍GSS5即可(不过这题[tex]a<b<c<d[/tex],所以不需要复杂的分类讨论)。

但是如果每个x都建一棵树,肯定会MLE吧?这个时候就要用主席树了= =

代码:

/**************************************************************
    Problem: 2653
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2220 ms
    Memory:1956 kb
****************************************************************/
 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=20005;
struct Node{
  Node *lc,*rc;
  int maxPSum,maxSSum,sum;
  Node(int x){
    lc=rc=NULL;
    maxPSum=maxSSum=sum=x;
  }
  Node(Node *l,Node *r){
    lc=l;rc=r;
  }
  void maintain(){
    maxPSum=max(lc->maxPSum,lc->sum+rc->maxPSum);
    maxSSum=max(rc->maxSSum,rc->sum+lc->maxSSum);
    sum=lc->sum+rc->sum;
  }
};
Node* build_tree(int L,int R){
  if(L==R){
    return new Node(1);
  }
  int M=L+(R-L)/2;
  Node *ans=new Node(build_tree(L,M),build_tree(M+1,R));
  ans->maintain();
  return ans;
}
int p,v;
Node* insert(Node *o,int L,int R){
  if(L==R){
    return new Node(v);
  }else{
    Node *ans=new Node(o->lc,o->rc);
    int M=L+(R-L)/2;
    if(p<=M){
      ans->lc=insert(ans->lc,L,M);
    }else{
      ans->rc=insert(ans->rc,M+1,R);
    }
    ans->maintain();
    return ans;
  }
}
int ql,qr;
Node queryPSum(Node *o,int L,int R){
  if(ql<=L && R<=qr){
    return *o;
  }else{
    int M=L+(R-L)/2;
    if(qr<=M){
      return queryPSum(o->lc,L,M);
    }else{
      if(ql<=M){
        Node l=queryPSum(o->lc,L,M);
        Node r=queryPSum(o->rc,M+1,R);
        Node ans(l.sum+r.sum);
        ans.maxPSum=max(l.maxPSum,l.sum+r.maxPSum);
        return ans;
      }else{
        return queryPSum(o->rc,M+1,R);
      }
    }
  }
}
Node querySSum(Node *o,int L,int R){
  if(ql<=L && R<=qr){
    return *o;
  }else{
    int M=L+(R-L)/2;
    if(qr<=M){
      return querySSum(o->lc,L,M);
    }else{
      if(ql<=M){
        Node l=querySSum(o->lc,L,M);
        Node r=querySSum(o->rc,M+1,R);
        Node ans(l.sum+r.sum);
        ans.maxSSum=max(r.maxSSum,r.sum+l.maxSSum);
        return ans;
      }else{
        return querySSum(o->rc,M+1,R);
      }
    }
  }
}
int querySum(Node *o,int L,int R){
  if(ql<=L && R<=qr){
    return o->sum;
  }else{
    int M=L+(R-L)/2;
    int ans=0;
    if(ql<=M){
      ans+=querySum(o->lc,L,M);
    }
    if(qr>M){
      ans+=querySum(o->rc,M+1,R);
    }
    return ans;
  }
}
Node *root[maxn];
 
int n;
int A[maxn],A2[maxn];
vector<int> V[maxn];
int lsh_siz;
inline void lsh(){
  sort(A2+1,A2+1+n);
  lsh_siz=unique(A2+1,A2+1+n)-A2-1;
  for(register int i=1;i<=n;i++){
    A[i]=lower_bound(A2+1,A2+1+lsh_siz,A[i])-A2;
    V[A[i]].push_back(i);
  }
}
int q[4];
inline bool Check(int M){
  register int l,m,r;
  if(q[1]+1<=q[2]-1){
    ql=q[1]+1;
    qr=q[2]-1;
    m=querySum(root[M],1,lsh_siz);
  }else{
    m=0;
  }
  ql=q[0];qr=q[1];
  l=querySSum(root[M],1,lsh_siz).maxSSum;
  ql=q[2];qr=q[3];
  r=queryPSum(root[M],1,lsh_siz).maxPSum;
#ifdef DEBUG
  printf("Case %d: %d %d %d\n",M,l,m,r);
#endif
  return l+m+r>=0;
}
int main(){
  register int i,j,L,M,R,ans=0;
  int t;
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&A[i]);
    A2[i]=A[i];
  }
  lsh();
  root[1]=build_tree(1,n);
  for(i=2;i<=lsh_siz;i++){
    root[i]=root[i-1];
    for(j=0;j<V[i-1].size();j++){
      p=V[i-1][j];
      v=-1;
      root[i]=insert(root[i],1,lsh_siz);
    }
  }
  scanf("%d",&t);
  while(t--){
    for(i=0;i<4;i++){
      scanf("%d",&q[i]);
      q[i]=(q[i]+ans)%n;
    }
    sort(q,q+4);
    for(i=0;i<4;i++){
      q[i]++;
      #ifdef DEBUG
      printf("%d ",q[i]);
      if(i==3){
        puts("");
      }
      #endif
    }
    L=1;R=lsh_siz;
    while(true){
      if(R-L<=3){
        for(i=R;i>=L;i--){
          if(Check(i)){
            ans=A2[i];
            break;
          }
        }
        break;
      }
      M=L+(R-L)/2;
      if(Check(M)){
        L=M;
      }else{
        R=M;
      }
    }
    printf("%d\n",ans);
  }
  return 0;
}

[CodeVS 1217]借教室

很容易想到线段树水过。

很可惜,这样估计也就70分。

然后这个问题是符合单调性的……可以二分答案哒。不过怎么判定?

不知道诸位还记得差分序列?记得就好,用差分序列的方法维护即可。

等等,我怎么感觉你这个做法是[tex]O(nlogn)[/tex]的,能过?

推荐一个行之有效的优化:注意一下每一次修改都是在之前的基础上反悔或前进几次,所以就可以直接在原基础上修改差分序列辣~这样效率是很高滴~

代码:

#include <cstdio>
const int maxn=1e6+5;
typedef long long ll;
ll A[maxn];
int l[maxn],r[maxn];
ll d[maxn];
ll C[maxn];
int n,m,last=0;
bool Check(int x){
    register int i,cnt=0;
    if(x>last)
        for(i=last+1;i<=x;i++){
            C[l[i]]+=d[i];
            C[r[i]+1]-=d[i];
        }
    if(x<last)
        for(i=x+1;i<=last;i++){
            C[l[i]]-=d[i];
            C[r[i]+1]+=d[i];
        }
    last=x;
    for(i=1;i<=n;i++){
        cnt+=C[i];
        if(cnt>A[i])
            return false;
    }
    return true;
}

int main(){
    register int i,L,M,R;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
    }
    for(i=1;i<=m;i++){
        scanf("%lld%d%d",&d[i],&l[i],&r[i]);
    }
    L=1;
    R=m+1;
    while(L<R){
        M=L+(R-L)/2;
        if(Check(M)){
            L=M+1;
        }else{
            R=M;
        }
    }
    if(L==m+1)
        puts("0");
    else
        printf("-1\n%d\n",L);
    return 0;
}

[POJ 2455]Secret Milking Machine

这个题要求最大边最小,很明显要二分答案。

考虑验证谓词[tex]C(x)[/tex]。我们可以将所有边权小于等于[tex]x[/tex]的边加入图,然后判断是否有[tex]T[/tex]条从1到N的不重复路径。

不过这个怎么做呢?我们可以把边加入(注意我们要加入的边都是无向边),并把容量设为1,从1到N跑一遍最大流,就是不重复路径条数。

为什么可以这样呢?每个边容量只有1,最多只能让一条路径使用并“推送”到终点,所以从1到N的最大流就是不重复路径条数辣。

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=205,maxp=40005;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))

namespace Dinic{
	struct Edge{
		int u,v,cap,flow;
	};
    vector<Edge> edges;
    vector<int> G[maxn];
    int m;
    inline void AddEdge(int u,int v,int cap){
        edges.push_back((Edge){u,v,cap,0});
        edges.push_back((Edge){v,u,0,0});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
	inline void ClearGraph(){
		register int i;
		edges.clear();
		m=0;
		REP(i,maxn){
			G[i].clear();
		}
	}
    bool vis[maxn];
    int d[maxn],cur[maxn];
    int s,t;
    inline bool BFS(){
        register int i,u;
        queue<int> Q;
        CL_ARR(vis,0);
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            REP(i,G[u].size()){
                Edge& e=edges[G[u][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    vis[e.v]=1;
                    d[e.v]=d[u]+1;
                    Q.push(e.v);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x,int a){
        if(x==t || a==0)
            return a;
        int flow=0,temp;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(d[e.v]==d[x]+1){
                temp=DFS(e.v,min(a,e.cap-e.flow));
                if(temp>0){
                    e.flow+=temp;
                    edges[G[x][i]^1].flow-=temp;
                    flow+=temp;
                    a-=temp;
                    if(a==0)
                        break;
                }
            }
        }
        return flow;
    }
    inline int Maxflow(int S,int T){
        s=S;
        t=T;
        register int ans=0;
        while(BFS()){
            CL_ARR(cur,0);
            ans+=DFS(s,0x7f7f7f7f);
        }
        return ans;
    }
};

struct Edge{
	int u,v,d;
	bool operator <(const Edge& x) const{
		return d<x.d;
	}
};
Edge EdgePool[maxp];
int n,p,t;
inline bool Check(int x){
	register int i;
	Dinic::ClearGraph();
	REP_B(i,p){
		if(EdgePool[i].d>x)
			break;
		Dinic::AddEdge(EdgePool[i].u,EdgePool[i].v,1);
		Dinic::AddEdge(EdgePool[i].v,EdgePool[i].u,1);
	}
	if((Dinic::Maxflow(1,n))<t)
		return false;
	else
		return true;
}
int main(){
	register int i,L=0,M,R=0;
	scanf("%d%d%d",&n,&p,&t);
	REP_B(i,p){
		scanf("%d%d%d",&EdgePool[i].u,&EdgePool[i].v,&EdgePool[i].d);
		R=max(R,EdgePool[i].d+1);
	}
	sort(EdgePool+1,EdgePool+1+p);
	while(L<R){
		M=L+(R-L)/2;
		if(Check(M))
			R=M;
		else
			L=M+1;
	}
	printf("%d\n",L);
	return 0;
}

[BZOJ 1196]公路修建问题

挺简单的二分答案题……然而到现在才A

思路很明显,直接二分最终答案。那么判定如何做呢?

假设判定谓词为[tex]C(x)[/tex],那么我们首先考虑选白边。贪心加入边权小于[tex]x[/tex]的边(当然是否有必要就要用并查集判定了。并且这样就算加的超过了[tex]k[/tex]条也不会对答案造成影响)。然后白边加的不够[tex]k[/tex]谓词就是假了。

然后再考虑黑边,接下来的事情就很简单了。

代码:

/**************************************************************
    Problem: 1196
    User: danihao123
    Language: C++
    Result: Accepted
    Time:672 ms
    Memory:1212 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define RAP(i,n) for(i=1;i<=(n);i++)
const int maxn=10001,maxm=20001;
 
struct Edge{
    int u,v,d1,d2;
};
bool cmp1(const Edge& x,const Edge& y){
    return x.d1<y.d1;
}
bool cmp2(const Edge& x,const Edge& y){
    return x.d2<y.d2;
}
 
int n;
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
inline void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(){
    register int i;
    for(i=1;i<=n;i++)
        p[i]=i;
    memset(rank,0,sizeof(rank));
}
 
int k,m;
Edge E[maxm];
inline bool check(int x){
    register int i,first_cnt=0,cnt=0;
    init_set();
    sort(E,E+m,cmp1);
    REP(i,m){
        if(E[i].d1>x){
            break;
        }else{
            if(!is_same(E[i].u,E[i].v)){
                first_cnt++;
                cnt++;
                union_set(E[i].u,E[i].v);
            }
        }
        if(cnt==n-1){
            return true;
        }
    }
    if(first_cnt<k)
        return false;
    sort(E,E+m,cmp2);
    REP(i,m){
        if(E[i].d2>x){
            break;
        }else{
            if(!is_same(E[i].u,E[i].v)){
                cnt++;
                union_set(E[i].u,E[i].v);
            }
        }
        if(cnt==n-1)
            return true;
    }
    return false;
}
int main(){
    register int i,L=1,M,R=0;
    scanf("%d%d%d",&n,&k,&m);
    m--;
    REP(i,m){
        scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].d1,&E[i].d2);
        R=max(R,E[i].d1);
    }
    R++;
    while(L<R){
        M=L+(R-L)/2;
        if(check(M))
            R=M;
        else
            L=M+1;
    }
    printf("%d\n",L);
    return 0;
}

 

[BZOJ 4326]运输计划

很容易想到树剖直接搞一发的玩法。估计复杂度是[tex]O(nlog^2n)[/tex]的,有点吃不消,再加上会被卡常,咔嚓掉。

考虑二分答案。我们可以直接二分最终答案,那么如何验证?

假设验证谓词为[tex]C(t)[/tex],表示通过把一条边清零可以使得用时为[tex]t[/tex]。那么所有用时大于[tex]t[/tex]的计划都要被清掉一条边。可见我们需要清零的边是所有用时大于[tex]t[/tex]的计划的边的交集中的最大边。

那么如何求交集呢?可以考虑树上差分,对于每次计划[tex](u,v)[/tex],我们求出其最近公共祖先[tex]L[/tex],然后对[tex]d[u][/tex]和[tex]d[v][/tex]分别加一,对[tex]d[L][/tex]则减二。随后将d上标记上推,可以求出每个点连向父亲的边被几个计划经过。易求交集。

至此方向已明确:二分答案,树上差分验证,同时我们还要用到LCA。LCA建议使用总计[tex]O(n)[/tex]的TarjanLCA离线算法,倍增也可。

代码:

/**************************************************************
    Problem: 4326
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4756 ms
    Memory:62188 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=300001,maxm=300001*2;
const int BUFSIZE=10000001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
 
int n;
namespace FastIO{
    char buf[BUFSIZE];
    int IO_tot=0;
    inline void InitFastIO(){
        fread(buf,sizeof(char),BUFSIZE-1,stdin);
    }
    inline char GetC(){
        return buf[IO_tot++];
    }
    inline int readint(){
        register int x=0;
        register char c=GetC();
        while(!isdigit(c))
            c=GetC();
        while(isdigit(c)){
            x=10*x+c-'0';
            c=GetC();
        }
        return x;
    }
    int bf[10];
    inline void putint(int x){
        register int siz=0,i;
        if(!x){
            bf[siz++]=0;
        }else{
            while(x){
                bf[siz++]=x%10;
                x/=10;
            }
        }
        for(i=siz-1;i>=0;i--)
            putchar(bf[i]+'0');
        putchar('\n');
    }
};
namespace Tree{
    int first[maxn];
    int next[maxm],to[maxm],dist[maxm];
    int tot=0;
    inline void Add_Edge(int u,int v,int d){
        tot++;
        next[tot]=first[u];
        first[u]=tot;
        to[tot]=v;
        dist[tot]=d;
    }
    int d[maxn],father[maxn];
    vector<int> hx;
    void dfs_1(int x,int fa,int dis){
        d[x]=dis;
        father[x]=fa;
        int i;
        GRAPH_REP(i,x){
            if(to[i]!=fa)
                dfs_1(to[i],x,dis+dist[i]);
        }
        hx.push_back(x);
    }
    int lazy[maxn];
    inline void ClearLazy(){
        memset(lazy,0,sizeof(lazy));
    }
    inline int DealCheck(int x){
        register int i,v,ans=0;
        REP_B(i,n){
            v=hx[i-1];
            lazy[father[v]]+=lazy[v];
        }
        REP_B(i,n){
            if(lazy[i]==x){
                ans=max(ans,d[i]-d[father[i]]);
            }
        }
        return ans;
    }
     
    // Djoin Set
    int p[maxn];
    int find_set(int x){
        if(p[x]==x)
            return x;
        else
            return p[x]=find_set(p[x]);
    }
    inline void union_set(int x,int y){
        p[find_set(y)]=find_set(x);
    }
    inline void make_set(int x){
        p[x]=x;
    }
     
    // LCA
    struct Query{
        int u,v,b;
    };
    bool vis[maxn];
    vector<Query> qs;
    vector<int> querys[maxn];
    inline void Add_Query(int x,int y,int b){
        querys[x].push_back(qs.size());
        qs.push_back((Query){x,y,b});
    }
    int res[maxn][3];
    int n;
    void LCA(int u){
        make_set(u);
        vis[u]=true;
        int i,temp;
        REP(i,querys[u].size()){
            Query& tep=qs[querys[u][i]];
            if(vis[tep.v])
                res[tep.b][2]=find_set(tep.v);
        }
        for(i=first[u];i;i=next[i]){
            temp=to[i];
            if(!vis[temp]){
                LCA(temp);
                union_set(u,temp);
            }
        }
    }
};
 
using namespace FastIO;
struct Deal{
    int u,v,lca,d;
    bool operator <(const Deal& x) const{
        return d<x.d;
    }
};
vector<Deal> V;
int m;
inline bool Check(int x){
    register int i,ideal=0,yh=V[m-1].d;
    Tree::ClearLazy();
    for(i=m-1;i>=0;i--){
        int& u=V[i].u,v=V[i].v,lca=V[i].lca,d=V[i].d;
        if(d>x){
            ideal++;
            Tree::lazy[u]++;
            Tree::lazy[v]++;
            Tree::lazy[lca]-=2;
        }else{
            break;
        }
    }
    yh-=Tree::DealCheck(ideal);
    return yh<=x;
}
int main(){
    register int i,u,v,lca,d;
    FastIO::InitFastIO();
    n=readint();
    m=readint();
    REP(i,n-1){
        u=readint();
        v=readint();
        d=readint();
        Tree::Add_Edge(u,v,d);
        Tree::Add_Edge(v,u,d);
    }
    REP(i,m){
        u=readint();
        v=readint();
        Tree::Add_Query(u,v,i);
        Tree::Add_Query(v,u,i);
        Tree::res[i][0]=u;
        Tree::res[i][1]=v;
    }
    Tree::dfs_1(1,0,0);
    Tree::LCA(1);
    REP(i,m){
        u=Tree::res[i][0];
        v=Tree::res[i][1];
        lca=Tree::res[i][2];
        d=Tree::d[u]+Tree::d[v]-2*Tree::d[lca];
        V.push_back((Deal){u,v,lca,d});
    }
    sort(V.begin(),V.end());
    u=0;
    v=V[m-1].d+1;
    while(u<v){
        d=u+(v-u)/2;
        if(Check(d))
            v=d;
        else
            u=d+1;
    }
    putint(u);
    return 0;
}