常州DAY10

附:T4随机化代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define drp(i,j,k) for(int i=(j);i>=(k);--i)
using namespace std;
inline int read(){
    int x=0,f=0;char ch;
    while(!isdigit(ch=getchar())) f|=ch=='-';
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return f?-x:x;

}
inline int max3(int x,int y,int z){return max(max(x,y),z);}
inline int min3(int x,int y,int z){return min(min(x,y),z);}
inline int jc3(int x,int y,int z){return max3(x,y,z)-min3(x,y,z);}
//------------------------------------------------------//
const int N=2e5+5;
int n,ans=N;
int fir[N],nex[N<<1],to[N<<1],pos;
void add(int x,int y){
    to[++pos]=y;nex[pos]=fir[x];fir[x]=pos;
    std::swap(x,y);
    to[++pos]=y;nex[pos]=fir[x];fir[x]=pos;
}

int siz[N],dep[N],fa[N][21];
int leaf[N],cnt;
void dfs1(int u,int f){
    dep[u]=dep[fa[u][0]=f]+1;siz[u]=1;
    for(int i=fir[u];i;i=nex[i]){
        int v=to[i];
        if(v==f) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
    }
    if(siz[u]==1) leaf[++cnt]=u;
}
int lca(int x,int y){
    if(dep[x]<dep[y]) std::swap(x,y);
    drp(i,17,0) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    drp(i,17,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return x==y?x:fa[x][0];
}
int w(int x,int y){
    int z=lca(x,y);
    if(x==z||y==z){
        if(dep[x]<dep[y]) std::swap(x,y);
        return jc3(siz[x],siz[z]-siz[x],n-siz[z]);
    }
    else return jc3(siz[x],siz[y],n-siz[x]-siz[y]);
}


void find(int root,int k){
    if(ans!=N&&n<=2000) return ;
    dfs1(root,0);
    rep(i,1,17) rep(u,1,n)
      fa[u][i]=fa[fa[u][i-1]][i-1];
    if(n<=2000){
        if(ans!=N) return;
        rep(i,1,n) rep(j,1,n)
          ans=std::min(ans,w(i,j));
        return ;
    }

    int tim=40;
    while(tim--){
        int x,y;
        if(tim&1) {
            x=leaf[rand()%cnt+1];
            y=leaf[rand()%cnt+1];
        }
        else {
            x=rand()%n+1;
            y=rand()%n+1;
        }  
        bool con=true;
        int now=w(x,y);
        while(con) {
            con=false;
            drp(i,k,0) if(fa[x][i]) {
                int ne=w(fa[x][i],y);
                if(ne>now) continue;
                x=fa[x][i]; now=ne;
                con=true;
            }
            if(!con) {
                std::swap(x,y);
                drp(i,0,0) if(fa[x][i]) {
                    int ne=w(fa[x][i],y);
                    if(ne>now) continue;
                    x=fa[x][i]; now=ne;
                    con=true;
                }
            }
            if(rand()&1)std::swap(x,y);
        }
        ans=std::min(ans,now);
    }
}

signed main(){
    srand(time(0));
    freopen("papricice.in","r",stdin);
    freopen("papricice.out","w",stdout);
    n=read();
    rep(i,1,n-1) add(read(),read());
    rep(i,1,5) find(rand()%n+1,i),cnt=0;
    printf("%lld\n",ans);
}

BZOJ1483 [HNOI2009] 梦幻布丁

BZOJ

洛谷

链表+启发式合并

懒得写链表

std::set代替链表

首先算出初始状态答案

然后对于每个修改操作,启发式合并两种颜色。

启发式合并:在合并两个集合(或两棵树)时,暴力将较小集合的元素(或结点更少的树的所有节点)合并(或插入)到另一较大集合(或结点更多的树)中。

简单来说就是弱肉强食。

而且启发式合并的时间复杂度可以证明是O(logn)的

对于本题,枚举较小的集合的每个元素,处理答案并且加入较大的集合,同时更改颜色。

对于查询操作,由于每次修改同时都计算出答案,直接输出即可。

继续阅读“BZOJ1483 [HNOI2009] 梦幻布丁”