你最愿意做的哪件事，才是你的天赋所在

0%

发表于 Valine：

异或最小生成树

异或最小生成树就是每个点都有一个权值，而两个点之间连接的边的权值是两个点的异或值，求这个点集合的最小生成树

CF888G

思路

我们会用到Boruvka算法，用上了分治的思想来求最小生成树，但是异或最小生成树呢，则还需要一颗trie树，因为它能够log的查询异或的最小值。

简单解释一下异或最小生成树的步骤

阅读全文 »

发表于 更新于 Valine：

题目

E

题意

就是给长度为1e5的大小为[0,$2^{18}$)的一个序列，要你求任意1~n个数异或的最大值，首先很容易发现当i=18的时候肯定已经是最大了，就是任意18个数异或已经是最大了，因为范围是[0,2^18)很显然，我1~18个数肯定会异或出尽量多的1，然后之后就是$a[i+2]=a[i]$即可，但是前18个我们怎么求呢，我们可以用卷积，只不过这里是异或卷积。暴力求卷积的话复杂度是$O(n^2logn)$的，所以用FWT快速沃尔什变换来写，与FFT的思想是差不多的，都是分治。不过重新定义了运算，这样就能$O(nlog^2n)$的复杂度解决了，总复杂度就是$O(n+wlog^2w)$

阅读全文 »

发表于 Valine：

I

题意

题目给出了一个图，然后还有n个点，还有每个点的度，求判断图中是否存在一个子图满足每个点的度等于给出的度，度为[1,2]。

思路

首先，如果每个点的度都为1，那么很显然，直接求这个图是否存在完全匹配就可以了。但是度数的范围是[1,2]，于是我们就想到拆点，如果是简单的把度为2的点直接拆成两个点的话，就会有下面这种情况

阅读全文 »

发表于 更新于 Valine：

题目链接

CodeChef-PRIMEDST

思路

采用点分治统计所有的路径，但是如果是朴素的路径相乘复杂度是O(n^2)，所以采用FFT加速多项式乘法达到(nlogn)的复杂度，总体复杂度就是(nlognlogn)的复杂度。
做题步骤:

  1. 点分治处理
  2. 统计当前子树的路径
  3. 进行FFT
  4. 累加路径，放进桶里
  5. 重复重心的所有子树重复2，3，4步骤
  6. 清空桶，继续点分治
  7. 统计答案

    代码实现

    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
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define pi acos(-1)
    const int N = 1e5+10;
    int head[N],tot;
    ll sum,rt,dis[N],tmp[N<<4],maxp[N],siz[N],len,d[N],up,dn;
    int f[N<<2],g[N<<2];
    int prime[N];
    bool isprime[N],pcnt;
    ll ans[N];
    int cnt,n;
    bool vis[N];
    int r[N];
    void init(){
        isprime[0]=isprime[1]=1;
        for(int i=2;i<N;i++){
            if(!isprime[i]){
                for(int j=i+i;j<N;j+=i){
                    isprime[j]=1;
                }
            }
        }
    }
    struct cp
    {
        double r,i;
        cp(double _r = 0,double _i = 0)
        {
            r = _r; i = _i;
        }
        cp operator +(const cp &b)
        {
            return cp(r+b.r,i+b.i);
        }
        cp operator -(const cp &b)
        {
            return cp(r-b.r,i-b.i);
        }
        cp operator *(const cp &b)
        {
            return cp(r*b.r-i*b.i,r*b.i+i*b.r);
        }
    }F[N<<2],G[N<<2],H[N<<2];
    void FFT(cp *s,int n,int inv){
        int bit=0;
        while ((1<<bit)<n)bit++;
        for(int i=0;i<n;i++)r[i]=i;
        for(int i=0;i<n;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(bit-1));
        for(int i=0;i<n;i++){
            if(i<r[i])swap(s[i],s[r[i]]);
        }
        for(int len=2;len<=n;len*=2){
            cp wn = cp(cos(pi*2.0/len),inv*sin(pi*2.0/len));
            for(int st=0;st<n;st+=len){
                cp w = cp(1.0,0.0);
                for(int i=st;i<st+len/2;i++,w=w*wn){
                    cp x=s[i];//偶次幂
                    cp y=w*s[i+len/2];//奇次幂
                    s[i]=x+y;
                    s[i+len/2]=x-y;
                }
            }
        }
    }
    struct edge{
        int v,w,nex;
        edge() {}
        edge(int v, int w, int nex) : v(v), w(w), nex(nex) {}
    }edges[N<<1];
    void add(int u,int v,int w){
        edges[tot]=edge(v,w,head[u]);
        head[u]=tot++;
    }
    void getrt(int u,int fa){
        maxp[u]=0,siz[u]=1;
        for(int i=head[u];~i;i=edges[i].nex){
            int v = edges[i].v;
            if(vis[v]||v==fa)continue;
            getrt(v,u);
            siz[u]+=siz[v];
            if(maxp[u]<siz[v])maxp[u]=siz[v];
        }
        maxp[u]=max(maxp[u],sum-siz[u]);
        if(maxp[u]<maxp[rt])rt=u;
    }
    void getdis(int u,int fa){
        tmp[cnt++]=dis[u];
        for(int i=head[u];~i;i=edges[i].nex){
            int v =edges[i].v;
            if(vis[v]||v==fa)continue;
            dis[v]=dis[u]+edges[i].w;
            getdis(v,u);
        }
    }
    void getdeep(int u,int fa,int deep,int &mx){
        mx = max(mx,deep);
        for(int i=head[u];~i;i=edges[i].nex){
            int v = edges[i].v;
            if(vis[v]||v==fa)continue;
            getdeep(v,u,deep+1,mx);
        }
    }
    void solve(int u){
        int mx = -1;
        getdeep(u,0,0,mx);
        len = 1;
        while(len<=2*mx)len<<=1;
        for(int i=head[u];~i;i=edges[i].nex){
            int v = edges[i].v;
            if(vis[v])continue;
            dis[v]=edges[i].w;
            cnt = 0;
            getdis(v,u);
            for(int j=0;j<cnt;j++){
                g[tmp[j]]++;
                if(!isprime[tmp[j]])up++;
            }

            int bit=0;
            while ((1<<bit)<len)bit++;
            for(int j=0;j<len;j++){
                G[j].r=g[j],G[j].i=0;
                F[j].r=f[j],F[j].i=0;
            }
            FFT(F,len,1);
            FFT(G,len,1);
            for(int j=0;j<len;j++)H[j]=F[j]*G[j];
            FFT(H,len,-1);
            for(int j=0;j<len;j++){
                if(!isprime[j])
                    up+=(ll)(H[j].r/len+0.5);
            }
            for(int j=0;j<cnt;j++)f[tmp[j]]++,g[tmp[j]]=0;
        }
        for(int i=0;i<=n;i++)f[i]=0;
    }
    void divide(int u){
        vis[u]=1;
        solve(u);
        for(int i=head[u];~i;i=edges[i].nex){
            int v = edges[i].v;
            if(vis[v])continue;
            maxp[rt=0]=sum=siz[v];
            getrt(v,0);
            getrt(rt,0);
            divide(rt);
        }
    }
    int main(){
        init();
        memset(head,-1,sizeof(head));
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            int u,v;
            scanf("%d %d",&u,&v);
            add(u,v,1);
            add(v,u,1);
        }
        maxp[0]=sum=n;
        getrt(1,0);
        getrt(rt,0);
        divide(rt);
        dn = 1ll*n*(n-1)/2;
        printf("%.6lf\n",(double)up/(double)dn);
    }

发表于 Valine：

题目链接

CF161D-luogu

思路

套用点分治的思想

  1. 先处理出每个节点的距离
  2. 记录桶中的个数
  3. 更新答案
  4. 更新桶
  5. 下一轮分治清空桶

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int  N = 5e4+10;
int head[N],tot;
int maxp[N],siz[N],rt,sum,dis[N],cnt;
int tmp[N],rec[N],ans,n,k;
bool judge[N];
bool vis[N];
struct edge{
    int v,w,next;
    edge(){}
    edge(int v, int w, int next) : v(v), w(w), next(next) {}
}edges[N<<1];
void add(int u,int v,int w){
    edges[tot]=edge(v,w,head[u]);
    head[u]=tot++;
}
void getrt(int u,int fa){
    maxp[u]=0,siz[u]=1;
    for(int i=head[u];~i;i=edges[i].next){
        int v = edges[i].v;
        if(vis[v]||v==fa)continue;
        getrt(v,u);
        siz[u]+=siz[v];
        if(maxp[u]<siz[v])maxp[u]=siz[v];
    }
    maxp[u]=max(maxp[u],sum-siz[u]);
    if(maxp[rt]>maxp[u])rt=u;
}
void getdis(int u,int fa){
    tmp[cnt++]=dis[u];
    for(int i=head[u];~i;i=edges[i].next){
        int v = edges[i].v;
        if(vis[v]||v==fa)continue;
        dis[v]=dis[u]+edges[i].w;
        getdis(v,u);

    }
}
void solve(int u){
    queue<int>que;
    rec[0]=1;
    for(int i=head[u];~i;i=edges[i].next){
        int v = edges[i].v;
        if(vis[v])continue;
        cnt = 0;
        dis[v]=edges[i].w;
        getdis(v,u);
        for(int j=0;j<cnt;j++){
            if(k-tmp[j]>=0)ans+=rec[k-tmp[j]];
        }
        for(int j=0;j<cnt;j++)rec[tmp[j]]++,que.push(tmp[j]);
    }
    while(!que.empty()){
        rec[que.front()]=0;
        que.pop();
    }
}
void divide(int u){
    vis[u]=1;
    solve(u);
    for(int i=head[u];~i;i=edges[i].next){
        int v = edges[i].v;
        if(vis[v])continue;
        maxp[rt=0]=sum=siz[v];
        getrt(v,0);
        getrt(rt,0);
        divide(rt);
    }
}
int main(){
    memset(head,-1,sizeof(head));
  scanf("%d %d",&n,&k);
  for(int i=1;i<n;i++){
      int u,v,w;
      scanf("%d %d",&u,&v);
      add(u,v,1);
      add(v,u,1);
  }
  maxp[0]=sum=n;
  getrt(1,0);
  getrt(rt,0);
  divide(rt);
  printf("%d\n",ans);
}

发表于 Valine：

题目链接

luogu4149

思路

点分治的裸题，每次计算距离的时候带入一个深度，开一个judge数组开记录距离为k的最小步数时多少，每次更新即可，具体看代码。

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+10;
int head[N],tot;
int maxp[N],siz[N],tmp[N*10],cnt,d[N];
int sum,rt;
bool vis[N];
int judge[N*10];
int dis[N];
int n,k,ans=INT_MAX;
struct edge{
    int v,w,nex;
    edge(){}
    edge(int v, int w, int nex) : v(v), w(w), nex(nex) {}
}edges[N<<1];
void add(int u,int v,int w){
    edges[tot]=edge(v,w,head[u]);
    head[u]=tot++;
}
void getrt(int u,int fa){
    maxp[u]=0,siz[u]=1;
    for(int i=head[u];~i;i=edges[i].nex){
        int v=edges[i].v;
        if(vis[v]||v==fa)continue;
        getrt(v,u);
        siz[u]+=siz[v];
        if(maxp[u]<siz[v])maxp[u]=siz[v];
    }
    maxp[u]=max(maxp[u],sum-siz[u]);
    if(maxp[u]<maxp[rt])rt=u;
}
void getdis(int u,int fa,int deep){
    if(dis[u]>k)return ;
    tmp[cnt]=dis[u];
    d[cnt++]=deep;
    for(int i=head[u];~i;i=edges[i].nex){
        int v = edges[i].v;
        if(v==fa||vis[v])continue;
        dis[v]=dis[u]+edges[i].w;
        getdis(v,u,deep+1);
    }
}
void solve(int u){
    judge[0]=0;
    queue<int>que;
    for(int i=head[u];~i;i=edges[i].nex){
        int v = edges[i].v;
        if(vis[v])continue;
        cnt = 0;
        dis[v]=edges[i].w;
        getdis(v,u,1);
        for(int j=0;j<cnt;j++)ans=min(ans,judge[k-tmp[j]]+d[j]);
        for(int j=0;j<cnt;j++)judge[tmp[j]]=min(judge[tmp[j]],d[j]),que.push(tmp[j]);
    }
    while(!que.empty()){
        judge[que.front()]=1e9+10;
        que.pop();
    }
}
void divide(int u){
    vis[u]=1;
    solve(u);
    for(int i=head[u];~i;i=edges[i].nex){
        int v = edges[i].v;
        if(vis[v])continue;
        maxp[rt=0]=sum=siz[v];
        getrt(v,0);
        getrt(rt,0);
        divide(rt);
    }
}
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d %d",&n,&k);
    for(int i=1;i<n;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        u++;v++;
        add(u,v,w);
        add(v,u,w);
    }
    maxp[0]=sum=n;
    memset(judge,0x3f,sizeof(judge));
    getrt(1,0);
    getrt(rt,0);
    divide(rt);
    printf("%d\n",ans>=n?-1:ans);
}

发表于 Valine：

思路

这题是个很好的点分治题目。
首先明确我们的目的，既然使用了点分治，那么就需要O(n)的时间内处理出重心rt以及“rt的儿子”的答案。
考虑重心的一个子树的根节点，如果这个点v的颜色是第一次出现，那么它对其他不在该子树的点的答案的贡献(包括rt)就是size[v]
然后我们再考虑这个子树，注意刚刚我们考虑的是子树的根节点，现在考虑的是整个子树对其他“rt儿子”的贡献。假设该子树的根节点是v，从v~rt上有num种颜色，那么对其他节点的贡献就是num*(size[rt]-size[v])
整体的步骤：

阅读全文 »

发表于 Valine：

题目链接

luogu3806

思路

这题是点分治的模板题目，点分治就是一棵树上的分治。
详细的教程上B站看AgOH的直播，很感谢大佬的分享
点分治教程-作者:AgOH

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e4+10;
const int NN = 1e7+10;
struct edge{
    int v,dis,nex;
}edges[N<<1];
int head[N<<1],edgenum,sum,rt,n,m,cnt;
int maxp[N],siz[N],dis[N],q[N/10],tmp[N<<1];
bool ans[NN],judge[NN],vis[N];
void add(int u,int v,int dis){
    edges[edgenum].nex=head[u];
    edges[edgenum].v=v;
    edges[edgenum].dis=dis;
    head[u]=edgenum++;
}
void getrt(int u,int fa){
    siz[u]=1,maxp[u]=0;
    for(int i=head[u];~i;i=edges[i].nex){
        int v = edges[i].v;
        if(vis[v]||v==fa)continue;
        getrt(v,u);
        siz[u]+=siz[v];
        if(maxp[u]<siz[v])maxp[u]=siz[v];
    }
    maxp[u]=max(maxp[u],sum-siz[u]);
    if(maxp[u]<maxp[rt])rt=u;
}
void getdis(int u,int f){
    tmp[cnt++]=dis[u];
    for(int i=head[u];~i;i=edges[i].nex){
        int v = edges[i].v;
        if(v==f||vis[v])continue;
        dis[v]=dis[u]+edges[i].dis;
        getdis(v,u);
    }
}
void solve(int u){
    queue<int>que;
    for(int i=head[u];~i;i=edges[i].nex){
        int v = edges[i].v;
        if(vis[v])continue;
        cnt = 0;
        dis[v]=edges[i].dis;
        getdis(v,u);
        for(int j=0;j<cnt;j++){
            for(int k=0;k<m;k++){
                if(q[k]>=tmp[j]){
                    ans[k]|=judge[q[k]-tmp[j]];
                }
            }
        }
        for(int j=0;j<cnt;j++){
            que.push(tmp[j]);
            judge[tmp[j]]=1;
        }
    }
    while (!que.empty()){
        judge[que.front()]=false;
        que.pop();
    }
}
void divide(int u){
    vis[u]=judge[0]=1;
    solve(u);//计算经过根节点的路径
    for(int i=head[u];~i;i=edges[i].nex){
        int v = edges[i].v;
        if(vis[v])continue;
        maxp[rt=0]=sum=siz[v];
        getrt(v,0);
//        这里第二次做获重心是为了得到正确的size数组，防止下次操作的时候错误
        getrt(rt,0);
        divide(rt);
    }
}
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d %d",&n,&m);
    for(int i=0;i<n-1;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=0;i<m;i++)scanf("%d",&q[i]);
    maxp[0]=sum=n;
    getrt(1,0);
    getrt(rt,0);
    divide(rt);
    for(int i=0;i<m;i++){
        if(ans[i])printf("AYE\n");
        else printf("NAY\n");
    }
    return 0;
}

发表于 Valine：

题目链接

luogu2634

思路

经典的点分治算法，点分治是logn层，考虑O(n)处理路径问题，
核心代码是下面这部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int calc(int u,int v){
    dis[u]=v%3;
    tmp[0]=tmp[1]=tmp[2]=0;
    getdis(u,0);
    return tmp[1]*tmp[2]*2+tmp[0]*tmp[0];
}
void divide(int u){
    //先统计所有答案
    ans+=calc(u,0);
    vis[u]=1;
    for(int i=head[u];~i;i=edges[i].nex){
        //对每个子树删除多于的答案
        // 实际删除那些不经过根节点的路径的边
        int v = edges[i].v;
        if(vis[v])continue;
        ans-=calc(v,edges[i].w);
        maxp[rt=0]=sum=siz[v];
        getrt(v,0);
        getrt(rt,0);
        divide(rt);
    }
}

阅读全文 »

发表于 更新于 Valine：

题目链接

落谷P1880

思路

dp[i][j]表示第i~j个石子合并的最小花费得到转移方程

因为i~j需要从i~(j-1)的所有状态推出，所以先枚举i，在枚举j,最后枚举k，保证所有状态都转移到，然后成环就让数列*2就好了

阅读全文 »