BZOJ3632:外太空旅行 随机化算法
BZOJ3218:a + b Problem 网络流+线段树

BZOJ3772:精神污染 dfs序+可持久化线段树

shinbokuow posted @ Jan 25, 2015 11:42:12 PM in BZOJ with tags DFS序 可持久化线段树 , 1724 阅读

以后决定土豪题都粘一下题面吧.

【begin

Description

兵库县位于日本列岛的中央位置，北临日本海，南面濑户内海直通太平洋，中央部位是森林和山地，与拥有关西机场的大阪府比邻而居，是关西地区面积最大的县，是集经济和文化于一体的一大地区，是日本西部门户，海陆空交通设施发达。濑户内海沿岸气候温暖，多晴天，有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市，还有以疗养地而闻名的六甲山地等。
兵库县官方也大力发展旅游，为了方便，他们在县内的N个旅游景点上建立了n-1条观光道，构成了一棵图论中的树。同时他们推出了M条观光线路，每条线路由两个节点x和y指定，经过的旅游景点就是树上x到y的唯一路径上的点。保证一条路径只出现一次。
你和你的朋友打算前往兵库县旅游，但旅行社还没有告知你们最终选择的观光线路是哪一条（假设是线路A）。这时候你得到了一个消息：在兵库北有一群丧心病狂的香菜蜜，他们已经选定了一条观光线路（假设是线路B），对这条路线上的所有景点都释放了【精神污染】。这个计划还有可能影响其他的线路，比如有四个景点1-2-3-4，而【精神污染】的路径是1-4，那么1-3,2-4,1-2等路径也被视为被完全污染了。
现在你想知道的是，假设随便选择两条不同的路径A和B，存在一条路径使得如果这条路径被污染，另一条路径也被污染的概率。换句话说，一条路径被另一条路径包含的概率。
 

 

Input

第一行两个整数N,M
接下来N-1行，每行两个数a,b，表示A和B之间有一条观光道。
接下来M行，每行两个数x,y，表示一条旅游线路。
 

 

Output

所求的概率，以最简分数形式输出。
 

 

Sample Input

5 3
1 2
2 3
3 4
2 5
3 5
2 5
1 4

Sample Output

1/3
样例解释
可以选择的路径对有(1,2),(1,3),(2,3)，只有路径1完全覆盖路径2。

HINT

 

100%的数据满足：N,M<=100000

end】

思路:

分类讨论几种完全覆盖的情形,然后用离线+dfs序+可持久化线段树水过.时间复杂度\(O(mlogn)\).

真的想写的话自己看代码.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    inline bool digit(int x){return x>='0'&&x<='9';}
    template<typename T>inline void Get(T&x){
        int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
}
 
#define N 100010
int n,m;
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
 
int pa[N][17],dep[N],in[N],out[N],tclock;
void dfs(int x,int fa){
    in[x]=++tclock;
    for(int j=head[x];j;j=next[j])if(end[j]!=fa){pa[end[j]][0]=x,dep[end[j]]=dep[x]+1,dfs(end[j],x);}
    out[x]=tclock;
}
inline int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=16;i>=0;--i)if(dep[pa[x][i]]>=dep[y])x=pa[x][i];
    if(x==y)return x;
    for(int i=16;i>=0;--i)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];
    return pa[x][0];
}
 
#define M 100010
int x[M],y[M],Lca[M];
 
vector<int>v[N];
 
int root[N<<1];
struct SegmentTree{
    struct Node{
        int l,r,siz;
    }S[3000000];
    int cnt;
    inline void reset(){cnt=0;}
    inline int newnode(){int q=++cnt;S[q].l=S[q].r=S[q].siz=0;return q;}
    int Newversion(int Last,int tl,int tr,int ins){
        int q=newnode();S[q]=S[Last],++S[q].siz;if(tl==tr)return q;
        int mid=(tl+tr)>>1;
        if(ins<=mid)S[q].l=Newversion(S[Last].l,tl,mid,ins);else S[q].r=Newversion(S[Last].r,mid+1,tr,ins);
        return q;
    }
    inline int Query(int q,int tl,int tr,int dl,int dr){
        if(dl>dr)return 0;
        if(dl<=tl&&tr<=dr){return S[q].siz;}
        int mid=(tl+tr)>>1;
        if(dr<=mid)return Query(S[q].l,tl,mid,dl,dr);
        else if(dl>mid)return Query(S[q].r,mid+1,tr,dl,dr);
        else return Query(S[q].l,tl,mid,dl,mid)+Query(S[q].r,mid+1,tr,mid+1,dr);
    }
}Seg;
 
struct Path{
    int x,y;
    Path(){}
    Path(int _x,int _y):x(_x),y(_y){}
}sav[M<<1];
inline bool cmp1(const Path&A,const Path&B){return in[A.x]<in[B.x];}
inline bool cmp2(const Path&A,const Path&B){return in[A.y]<in[B.y];}
 
int seq[M<<1];
long long res;
 
void calcstep1(){
    register int i;int lans,rans,L,R,mid;
    for(int Root=1;Root<=n;++Root){
        int num=(int)v[Root].size();if(!num)continue;
        for(i=1;i<=num;++i){sav[i]=Path(x[v[Root][i-1]],y[v[Root][i-1]]);if(in[sav[i].x]>in[sav[i].y])swap(sav[i].x,sav[i].y);}
        sort(sav+1,sav+num+1,cmp1);
        Seg.reset();
        for(i=1;i<=num;++i)root[i]=Seg.Newversion(root[i-1],1,n,in[sav[i].y]);
        for(i=1;i<=num;++i)seq[i]=in[sav[i].x];
        for(i=1;i<=num;++i){
            if(in[sav[i].x]>seq[num]||out[sav[i].x]<seq[1])continue;
            for(L=1,R=num;L<R;){
                mid=(L+R)>>1;
                if(seq[mid]>=in[sav[i].x])R=mid;else L=mid+1;
            }lans=L;
            for(L=1,R=num;L<R;){
                mid=(L+R+1)>>1;
                if(seq[mid]>out[sav[i].x])R=mid-1;else L=mid;
            }rans=L;
            res+=Seg.Query(root[rans],1,n,in[sav[i].y],out[sav[i].y])-Seg.Query(root[lans-1],1,n,in[sav[i].y],out[sav[i].y])-1;
        }
    }
}
 
void calcstep2(){
    register int i;int lans,rans,L,R,mid,num=0;
    for(i=1;i<=m;++i){       
        if(x[i]==Lca[i]||y[i]==Lca[i]){sav[++num]=Path(x[i],y[i]);if(in[sav[num].x]>in[sav[num].y])swap(sav[num].x,sav[num].y);}
    }
    sort(sav+1,sav+num+1,cmp2);
    Seg.reset();
    for(i=1;i<=num;++i)root[i]=Seg.Newversion(root[i-1],1,n,in[sav[i].x]);
    for(i=1;i<=num;++i)seq[i]=in[sav[i].y];
    for(i=1;i<=num;++i){
        if(in[sav[i].y]>seq[num]||out[sav[i].y]<seq[1])continue;
        for(L=1,R=num;L<R;){
            mid=(L+R)>>1;
            if(seq[mid]>=in[sav[i].y])R=mid;else L=mid+1;
        }lans=L;
        for(L=1,R=num;L<R;){
            mid=(L+R+1)>>1;
            if(seq[mid]>out[sav[i].y])R=mid-1;else L=mid;
        }rans=L;
        res+=Seg.Query(root[rans],1,n,1,in[sav[i].x])+Seg.Query(root[rans],1,n,out[sav[i].x]+1,n);
        res-=Seg.Query(root[lans-1],1,n,1,in[sav[i].x])+Seg.Query(root[lans-1],1,n,out[sav[i].x]+1,n);
        res--;
    }
}
 
void calcstep3(){
    register int i;int lans,rans,L,R,mid,num=0;
    for(i=1;i<=m;++i)if(x[i]!=Lca[i]&&y[i]!=Lca[i])sav[++num]=Path(Lca[i],x[i]),sav[++num]=Path(Lca[i],y[i]);
    sort(sav+1,sav+num+1,cmp2);
    Seg.reset();
    for(i=1;i<=num;++i)root[i]=Seg.Newversion(root[i-1],1,n,in[sav[i].x]);
    for(i=1;i<=num;++i)seq[i]=in[sav[i].y];
    for(i=1;i<=m;++i){
        if(x[i]!=Lca[i]&&y[i]!=Lca[i])continue;
        if(in[x[i]]>in[y[i]])swap(x[i],y[i]);
        if(in[y[i]]>seq[num]||out[y[i]]<seq[1])continue;
        for(L=1,R=num;L<R;){
            mid=(L+R)>>1;
            if(seq[mid]>=in[y[i]])R=mid;else L=mid+1;
        }lans=L;
        for(L=1,R=num;L<R;){
            mid=(L+R+1)>>1;
            if(seq[mid]>out[y[i]])R=mid-1;else L=mid;
        }rans=L;
        res+=Seg.Query(root[rans],1,n,1,in[x[i]])+Seg.Query(root[rans],1,n,out[x[i]]+1,n);
        res-=Seg.Query(root[lans-1],1,n,1,in[x[i]])+Seg.Query(root[lans-1],1,n,out[x[i]]+1,n);
        if(x[i]==y[i])res-=(int)v[x[i]].size();
    }
}
 
long long gcd(long long a,long long b){return(!b)?a:gcd(b,a%b);}
 
int main(){ 
    Fio::Get(n),Fio::Get(m);register int i,j;int a,b;
    for(i=1;i<n;++i){
        Fio::Get(a),Fio::Get(b);make(a,b);
    }
    dep[1]=1,dfs(1,-1);for(j=1;j<=16;++j)for(i=1;i<=n;++i)pa[i][j]=pa[pa[i][j-1]][j-1];
     
    for(i=1;i<=m;++i){
        Fio::Get(x[i]),Fio::Get(y[i]),Lca[i]=lca(x[i],y[i]);
        if(Lca[i]!=x[i]&&Lca[i]!=y[i])v[Lca[i]].push_back(i);
    }
     
    calcstep1();
    calcstep2();
    calcstep3();
     
    if(res==0)puts("0/1");
    else{
        long long total=(long long)m*(m-1)/2;
        long long Gcd=gcd(res,total);res/=Gcd,total/=Gcd;
        printf("%lld/%lld",res,total);
    }
     
    return 0;
}
Small_feed 评论 (1)
1
[回复]
unf library hours 说:
Aug 26, 2022 10:53:06 AM

The Carpenter Library aspires to be the intellectual center of its community, to foster innovations that lead to the discovery of knowledge,unf library hours and to further 2021. The Carpenter Library aspires to be the intellectual center of its community, to foster innovations that lead to the discovery of knowledge, and to further 2021.The Carpenter Library aspires to be the intellectual center of its community, to foster innovations that lead to the discovery of knowledge.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter