您的位置: 首页 > IT文章 > 省选前的点分治抢救计划

省选前的点分治抢救计划

分类: IT文章 • 2024-10-06 20:15:49

例行的废话：

为什么有这么个东西？

因为沙茶博主没有好好学过点分治，NOIP前讲了几次都是看着题解瞎打了一气混过去的，NOIP之后就没有好好讲的也没有好好做了。

所以点分治水平基本为零，于是尝试在滚粗之前抢救一下，重学点分治(和动态点分治)。

注意是自我抢救，不是教程或者题目汇总，所以完全不建议看这个东西(不会的看了还不会，会了的看了发现都是水题，而且很可能错误百出)

(什么，边分治？那更没学啊)

废话结束

网上好多的点分治题解都是说：找到重心，处理经过重心的路径，继续递归处理各个子树

然后我NOIP前看这个：怎么处理啊？

于是就咕咕了，于是就没学，于是只能省选前一个月才学点分治

我佛了，这人怎么这么沙茶

废话结束

关于重心就不提了，说一说一般怎么“处理经过重心的路径”，点分治要说怎么写就是上面那几句，主要是你要写出来

先从重心开始DFS一遍，把到当前联通块内所有点的路径(一般都是距离好吧=。=)存起来

然后处理的话根据具体题目有两种方法，第一种是容斥子树

举个例子

洛谷 P4178 Tree

求树上长度不超过k的路径数

然后我们现在搞出来了重心到当前联通块里所有点的距离

显然我们排序后双指针卡一下统计答案就行了，复杂度$O(nlog^2 n)$

就行了......吗？

不对，可能我们把一个子树里的两条链给统计进去了。。。。。。

所以我们到每个子树再统计一遍，这时不走父边，但是要算父边的长度(因为你要容斥掉从父亲那里统计到的答案)，容斥掉这部分答案

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=40005;
int n,k,t1,t2,t3,pt,cnt,tot,cor,ans,maxs;
int p[N],noww[2*N],goal[2*N],val[2*N];
int vis[N],siz[N],dis[N],vec[N];
void Link(int f,int t,int v)
{
    noww[++cnt]=p[f],p[f]=cnt;
    goal[cnt]=t,val[cnt]=v;
    noww[++cnt]=p[t],p[t]=cnt;
    goal[cnt]=f,val[cnt]=v;
}
void Getcore(int nde,int fth)
{
    siz[nde]=1; int sizz=0;
    for(int i=p[nde];i;i=noww[i])
        if(goal[i]!=fth&&!vis[goal[i]])
        {
            Getcore(goal[i],nde);
            siz[nde]+=siz[goal[i]];
            sizz=max(sizz,siz[goal[i]]);
        }
    sizz=max(sizz,tot-siz[nde]);
    if(sizz<maxs) maxs=sizz,cor=nde;
}
void DFS(int nde,int fth)
{
    vec[++pt]=dis[nde];
    for(int i=p[nde];i;i=noww[i])
        if(goal[i]!=fth&&!vis[goal[i]])
            dis[goal[i]]=dis[nde]+val[i],DFS(goal[i],nde);
}
int Calc(int nde,int fir)
{
    int ret=0;
    pt=0,dis[nde]=fir,DFS(nde,0);
    sort(vec+1,vec+1+pt);
    int lpt=1,rpt=pt;
    while(lpt<rpt)
    {
        while(lpt<rpt&&vec[lpt]+vec[rpt]>k) rpt--;
        ret+=rpt-lpt,lpt++;
    }
    return ret;
}
void PDC(int nde)
{
    maxs=n,cor=nde,Getcore(nde,0);
    ans+=Calc(cor,0),vis[cor]=true;
    for(int i=p[cor];i;i=noww[i])
        if(!vis[goal[i]]) ans-=Calc(goal[i],val[i]);
    for(int i=p[cor];i;i=noww[i])
        if(!vis[goal[i]]) tot=siz[goal[i]],PDC(goal[i]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
        scanf("%d%d%d",&t1,&t2,&t3),Link(t1,t2,t3);
    scanf("%d",&k),tot=n,PDC(1);
    printf("%d",ans);
    return 0;
}

View Code

第二个种是逐个加入子树

举个例子

洛谷点分治模板 P3806

数次询问树上是否存在长度为$k$的路径

每次都用上面的做法做两次再一减！复杂度$O(nmlog^2 n)$ -> gg

可过的做法是开个桶，每次逐个加入子树里点到重心的距离同时用桶判断是否有对应的(注意当然是先判再加啦)

另外开桶这个操作很常用的说，但是注意零的问题(一般来说应该是让零一直在桶里，表示从重心戳下去的一条路径；但是如果有零边清桶的时候可能顺带就被清掉了，算了我感觉只有我会犯这种沙雕错误)

复杂度$O(nmlog n)$

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=20005,M=1e7+70,K=110;
 6 int n,m,k,t1,t2,t3,pt,cnt,cor,pts,tot,maxx,maxs;
 7 int p[N],noww[N],goal[N],val[N];
 8 int vis[N],siz[N],dis[N],vec[N];
 9 int qry[K],ans[K],pos[N],bkt[M];
10 void Maxi(int &x,int y)
11 {
12     if(x<y) x=y;
13 }
14 void Link(int f,int t,int v)
15 {
16     noww[++cnt]=p[f],p[f]=cnt;
17     goal[cnt]=t,val[cnt]=v;
18     noww[++cnt]=p[t],p[t]=cnt;
19     goal[cnt]=f,val[cnt]=v;
20 }
21 void Getcore(int nde,int fth)
22 {
23     siz[nde]=1; int sizz=0;
24     for(int i=p[nde];i;i=noww[i])
25         if(goal[i]!=fth&&!vis[goal[i]])
26         {
27             Getcore(goal[i],nde);
28             siz[nde]+=siz[goal[i]];
29             if(siz[goal[i]]>sizz)
30                 sizz=siz[goal[i]];
31         }
32     if(tot-siz[nde]>sizz)
33         sizz=tot-siz[nde];
34     if(sizz<maxs)
35         maxs=sizz,cor=nde;
36 }
37 void DFS(int nde,int fth)
38 {
39     vec[++pt]=dis[nde];
40     for(int i=p[nde];i;i=noww[i])
41         if(goal[i]!=fth&&!vis[goal[i]])
42             dis[goal[i]]=dis[nde]+val[i],DFS(goal[i],nde);
43 }
44 /*int Calc(int nde,int fir)
45 {
46     int ret=0;
47     dis[nde]=fir,pt=0;
48     ll=1e9,rr=0,DFS(nde,0);
49     while(ll<=rr)
50     {
51         while(bkt[ll]) 
52             bkt[vec[++pt]=ll]--;
53         ll++;
54     }
55     int lpt=1,rpt=pt;
56     while(lpt<rpt)
57     {
58         while(lpt<rpt&&vec[lpt]+vec[rpt]>k) rpt--;
59         ret+=rpt-lpt,lpt++;
60     }
61     return ret;
62 }*/
63 void PDC(int nde)
64 {
65     maxs=n,cor=nde,Getcore(nde,0);
66     vis[cor]=true,pts=0; //printf("%d ",cor);
67     for(int i=p[cor];i;i=noww[i])
68         if(!vis[goal[i]]) 
69         {
70             dis[goal[i]]=val[i];
71             pt=0,DFS(goal[i],nde);
72             for(int j=1;j<=pt;j++)
73                 for(int k=1;k<=m;k++)
74                     if(vec[j]<=qry[k])
75                         ans[k]|=bkt[qry[k]-vec[j]];
76             for(int j=1;j<=pt;j++)
77                 if(vec[j]<=maxx&&vec[j])
78                     bkt[vec[j]]++,pos[++pts]=vec[j];
79         }
80     for(int i=1;i<=pts;i++) bkt[pos[i]]=0; 
81     for(int i=p[cor];i;i=noww[i])
82         if(!vis[goal[i]]) tot=siz[goal[i]],PDC(goal[i]);
83 }
84 int main()
85 {
86     scanf("%d%d",&n,&m),bkt[0]=1;
87     for(int i=1;i<n;i++)
88         scanf("%d%d%d",&t1,&t2,&t3),Link(t1,t2,t3);
89     for(int i=1;i<=m;i++) 
90         scanf("%d",&qry[i]),Maxi(maxx,qry[i]); 
91     tot=n,PDC(1);
92     for(int i=1;i<=m;i++) ans[i]?puts("AYE"):puts("NAY");
93     return 0;
94 }

View Code

最后我们再想一想：如果第二种方法用在第一题上，我们就需要一个数(shu)据(zhuang)结(shu)构(zu)来查询前缀和，稍微麻烦一点；如果第一种方法用在第二题上，呃，你可能只能强行容斥然后被卡=。=感觉总体来说第二种方法更泛用一些

胡乱总结一下

第一种适用于批量统计/统计对象较大(同时能容斥，当然的)的情况，第二种适用于精确统计/统计对象较小的情况

最后，点分治一定要动手写！嘴巴的话谁都会那几句话，没用的=。=

其他的一些点分治题目

IOI 2011 Race

把洛谷板子题随便改改就行了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=400005,M=1e6+60,inf=0x3f3f3f3f;
 6 int n,k,t1,t2,t3,pt,cnt,cor,pts,tot,ans,maxx,maxs;
 7 int vis[N],siz[N],dis[N],pos[N],bkt[M];
 8 int p[N],noww[N],goal[N],val[N];
 9 pair<int,int> vec[N];
10 void Maxi(int &x,int y){if(x<y) x=y;}
11 void Mini(int &x,int y){if(x>y) x=y;}
12 void Link(int f,int t,int v)
13 {
14     noww[++cnt]=p[f],p[f]=cnt;
15     goal[cnt]=t,val[cnt]=v;
16     noww[++cnt]=p[t],p[t]=cnt;
17     goal[cnt]=f,val[cnt]=v;
18 }
19 void Getcore(int nde,int fth)
20 {
21     siz[nde]=1; int sizz=0;
22     for(int i=p[nde];i;i=noww[i])
23         if(goal[i]!=fth&&!vis[goal[i]])
24         {
25             Getcore(goal[i],nde);
26             siz[nde]+=siz[goal[i]];
27             if(siz[goal[i]]>sizz)
28                 sizz=siz[goal[i]];
29         }
30     if(tot-siz[nde]>sizz)
31         sizz=tot-siz[nde];
32     if(sizz<maxs)
33         maxs=sizz,cor=nde;
34 }
35 void DFS(int nde,int fth,int lth)
36 {
37     vec[++pt]=make_pair(dis[nde],lth);
38     for(int i=p[nde];i;i=noww[i])
39         if(goal[i]!=fth&&!vis[goal[i]])
40             dis[goal[i]]=dis[nde]+val[i],DFS(goal[i],nde,lth+1);
41 }
42 void PDC(int nde)
43 {
44     maxs=n,cor=nde,Getcore(nde,0);
45     vis[cor]=true,pts=0; 
46     for(int i=p[cor];i;i=noww[i])
47         if(!vis[goal[i]]) 
48         {
49             dis[goal[i]]=val[i];
50             pt=0,DFS(goal[i],cor,1);
51             for(int j=1,t;j<=pt;j++)
52                 if((t=vec[j].first)<=k)
53                     ans=min(ans,bkt[k-t]+vec[j].second);
54             for(int j=1;j<=pt;j++)
55             {
56                 int len=vec[j].first;
57                 if(len<M) Mini(bkt[len],vec[j].second),pos[++pts]=len;
58             }
59         }
60     for(int i=1;i<=pts;i++) bkt[pos[i]]=inf; 
61     for(int i=p[cor];i;i=noww[i])
62         if(!vis[goal[i]]) tot=siz[goal[i]],PDC(goal[i]);
63 }
64 int main()
65 {
66     scanf("%d%d",&n,&k),ans=inf;
67     memset(bkt,inf,sizeof bkt),bkt[0]=0;
68     for(int i=1;i<n;i++)
69     {
70         scanf("%d%d%d",&t1,&t2,&t3);
71         Link(t1+1,t2+1,t3),Maxi(maxx,t3);
72     }
73     Mini(maxx,k),tot=n,PDC(1);
74     ans==inf?printf("-1"):printf("%d",ans);
75     return 0;
76 }

View Code

省选前的点分治抢救计划

相关推荐