@dxbdly 2021-03-03T14:47:05.000000Z 字数 6729 阅读 211

G2020 19寒假集训Day1

信息学——19寒假集训

G2020 19寒假集训Day1

今天是G2020寒假集训Day1,只学了两东西。

主要内容：分治，左偏树

注：本文引用清华大学艾雨青的讲课PPT

一.分治

1.思想

1、将问题分解成若干更小的子问题
2、使用子问题的结果求出原问题的结果
即分解问题——>解决子问题——>合并子问题得到全局解

2. 最近点对问题

注：引用博客

题面

问题分析:

$1^o$ 暴力:

时间复杂度 $O(n^2)$

伪代码：

minDist = infinity
for i = 1 to length(P) - 1
 for j = i + 1 to length(P)
  let p = P[i], q = P[j]
  if dist(p, q) < minDist:
   minDist = dist(p, q)
   closestPair = (p, q)
return closestPair

$2^o$ 分治法:

观察题目，不难看出本题具有最优子结构性质

所以可用分治法解决

第一步：分解

对所有点按x坐标从小到大排序，并根据下标分割为两个集合

第二步：解决子问题

递归寻找两个集合中的最近点对。

第三步：合并子问题的解，得到全局解

取 $dis=min(dis_{left},dis_{right})$

BUT

这样显然会有问题：


    在合并时最近距离不一定存在于两个集合中，
    可能一个点在集合A，一个点在集合B，而这两点间距离小于dis。

所以说，关键就在如何合并，我们可以取中点横坐标 $mid$
取出区间 $[mid-dis , mid+dis]$ ,则易得，如果存在最小距离点对，一定在此区间内。

那么如何确定此区间中有没有解呢？

$1'$ 暴力：

根据左边区域 $[mid-dis , mid]$ 的点,遍历右边区域 $[mid,mid+dis]$ 的点，即可找到是否存在小于 $dis$ 距离的点对。

时间复杂度最坏 $O(n^2)$

$2'$ 枚举六个点

若 $(p,q)$ 是 $q$ 的最近点对， $p$ 在带域左半部分，则 $q$ 点必在下图所示的 $δ*2δ$ 长方形上，而在该长方形上，最多只能由右边点集的6个点。每个点对之间的距离不小于 $δ$ 。

下面给出证明：

将 $δ*2δ$ 分成6个 $\frac{2δ}{3}*\frac{δ}{2}$ 的长方形

用反证法来证明:

假设存在大于6个点，则必有一个或多个小长方形存在两个及以上点

而小长方形的最长距离是为对角线长度，为： $\sqrt{\frac{2δ}{3}*\frac{2δ}{3}+ \frac{δ}{2} * \frac{δ}{2}}=\frac{5δ}{6}<δ$ 。

最长距离都小于 $δ$ ，与之前的条件不符合，故最多有6个点。

时间复杂度 $O(nlogn)$

AC代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    bool f=0;
    char c=getchar();
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
struct node{
    double x,y;
}point[200005],cnt[200005];
int len;
inline double get_dis(node a,node b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline bool cmp1(node a,node b)
{
    return a.x<b.x;
}
inline bool cmp2(node a,node b)
{
    return a.y<b.y;
}
inline double calc(int l,int r)
{
    if (r-l+1==2)
       return get_dis(point[l],point[r]);
    if (r-l+1==3)
       return min(get_dis(point[l],point[l+1]),get_dis(point[l+1],point[r]));
    int mid=(l+r)>>1;
    double dis=fmin(calc(l,mid),calc(mid+1,r));
    len=0;
    for (register int i=l;i<=r;++i)
        if (fabs(point[mid].x-point[i].x)<dis)
           cnt[++len]=point[i];
    stable_sort(cnt+1,cnt+len+1,cmp2);
    for (register int i=1;i<=len;++i)
        for (register int j=i+1;j<i+3&&j<=len;++j)
            dis=fmin(dis,get_dis(cnt[i],cnt[j]));
    return dis;
}
int main(){
    n=read();
    for (register int i=1;i<=n;++i)
        scanf("%lf%lf",&point[i].x,&point[i].y);
    stable_sort(point+1,point+n+1,cmp1);
    printf("%0.4lf",calc(1,n));
    return 0;
}

二.左偏树

题面

我们会发现，此题中不仅需要维护很多堆，而且需要支持合并操作，这时普通堆解决不了，我们就要使用——左偏树。

他长这个样子：

1.左偏树定义及性质

定义：

左偏树是一种可并堆
它除了支持优先队列的三个基本操作（插入，删除，取最小节点）
还支持一个很特殊的操作——合并操作。

性质：

左偏树满足堆性质，既任意节点都比它的后代小。
除此之外，左偏树还满足左偏性质。
定义一棵左偏树中的外节点为左子树或右子树为空的节点。
定义节点 i 的距离dist(i) 为节点 i 到它的后代中，最近的外节点所经过的边数。
任意节点的左子节点的距离不小于右子节点的距离（左偏性质）。

由此性质可得推论：

由左偏性质可知
1.一个节点的距离等于以该节点为根的子树最右路径的长度。
2.若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。 
3.若一棵左偏树的距离为k，则这棵左偏树至少有2k+1-1个节点。
4.一棵N个节点的左偏树距离最多为log(N+1)-1。

2.左偏树基本操作

$1^o$ 合并(merge)

对于两颗左偏树： $T1$ 与 $T2$ (以小根堆为例)，根分别为 $x$ , $y$ ，我们递归进行合并操作

如果 $val_x<val_y$ 先将 $T1$ 的右儿子与 $T2$ 合并，若合并后
$dist_{lchild}$ < $dist_{rchild}$ 将左右子树交换。

如果 $val_x>val_y$ 将两树交换，使其变成 $val_x<val_y$

示例图：

$2^o$ 添加(add)

将新加入的节点与原树合并即可。

$3^o$ 删除根节点(delete)

将左右儿子合并成新树，将根节点直接删除即可。

$4^o$ 注意

左偏树的添加，删除操作常与并查集连用(寻找某节点所在树的树根)，再做完操作后记得对应更新并查集的值。

AC代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,m;
struct node{
    int id,w;
}point[100005];
int father[100005],lc[100005],rc[100005],dist[100005];
bool b[100005];
inline int Find(int x)
{
    if (father[x]!=x) 
       return father[x]=Find(father[x]);
    return father[x];
}
inline bool check(node a,node b)
{
    return a.w!=b.w?a.w<b.w:a.id<b.id;
}
inline int merge(int x,int y)
{
    if (!x||!y)
       return x+y;
    if (check(point[y],point[x])) 
       swap(x,y);
    rc[x]=merge(rc[x],y);
    if (dist[lc[x]]<=dist[rc[x]])
       swap(lc[x],rc[x]);
    dist[x]=dist[rc[x]]+1;
    return x;
}
inline void update(int x,int y)
{
    if (b[x]||b[y])
       return ;
    x=Find(x),y=Find(y);
    if (x!=y) 
       father[x]=father[y]=merge(x,y);
}
inline void query(int x)
{
    if (b[x])
       {
       printf("-1\n");
       return ;
       }
    x=Find(x),b[x]=1;
    printf("%d\n",point[x].w);
    father[x]=father[lc[x]]=father[rc[x]]=merge(lc[x],rc[x]);
    lc[x]=rc[x]=dist[x]=0;
}
int main(){
    n=read(),m=read();
    dist[0]=-1;
    for (register int i=1;i<=n;++i)
        father[i]=point[i].id=i,point[i].w=read();
    for (register int i=1;i<=m;++i)
        {
        int op=read(),x,y;
        if (op==1)
           x=read(),y=read(),update(x,y);
        else
           x=read(),query(x);
        }
    return 0;
}

三.例题：

1. P2713 罗马游戏

题面

分析一下就可以看出这题是一个裸的左偏树，没什么好讲的

AC代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,m;
struct node{
    int id,w;
}point[1000005];
bool b[1000005];
int father[10000005],lc[1000005],rc[1000005],dist[1000005];
inline int Find(int x)
{
    if (father[x]!=x)
       return father[x]=Find(father[x]);
    return father[x];
}
inline bool check(node x,node y)
{
    return x.w!=y.w?x.w<y.w:x.id<y.id;
}
inline int merge(int x,int y)
{
    if (!x||!y) 
       return x+y;
    if (check(point[y],point[x]))
       swap(x,y);
    rc[x]=merge(rc[x],y);
    if (dist[lc[x]]<=dist[rc[x]])
       swap(lc[x],rc[x]);
    dist[x]=dist[rc[x]]+1;
    return x;
}
inline void update(int x,int y)
{
    if (b[x]||b[y])
       return ;
    x=Find(x),y=Find(y);
    if (x!=y)
       father[x]=father[y]=merge(x,y);
}
inline void query(int x)
{
    if (b[x])
       {
       printf("0\n");
       return ;
       }
    x=Find(x),b[x]=1;
    printf("%d\n",point[x].w);
    father[x]=father[lc[x]]=father[rc[x]]=merge(lc[x],rc[x]);
    lc[x]=rc[x]=dist[x]=0;
}
int main(){
    char op;
    dist[0]=-1;
    n=read();
    for (register int i=1;i<=n;++i)
        point[i].id=father[i]=i,point[i].w=read();
    m=read();
    for (register int i=1;i<=m;++i)
        {
        while (!isalpha(op=getchar()));
        int x,y;
        if (op=='M')
           x=read(),y=read(),update(x,y);
        else
           x=read(),query(x);
        }
    return 0;
}

2. P1456 Monkey King

题面

解法：

此题要求我们在将两颗左偏树修改根节点的权值并合并，然后输出新根节点的权值。

由于两颗左偏树的根节点被修改，性质可能被破坏，所以我们可以先将修改后的左偏树维护好，在做合并操作即可。

那么如何修改(update）：

    实际上修改一颗左偏树根节点的权值，就相当于先将做删除(delet)操作，将根节点删除，然后将修改权值后的根节点插入(add)

剩下的就是左偏树基本操作啦！

AC代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,m;
int val[100005],father[100005],lc[100005],rc[100005],dist[100005];
inline int Find(int x)
{
    if (father[x]!=x)
       return father[x]=Find(father[x]);
    return father[x];
}
inline int merge(int x,int y)
{
    if (!x||!y)
       return x+y;
    if (val[x]<val[y])
       swap(x,y);
    rc[x]=merge(rc[x],y);
    if (dist[lc[x]]<dist[rc[x]])
       swap(lc[x],rc[x]);
    dist[x]=dist[rc[x]]+1;
    return x;
}
inline int update(int x)
{
    val[x]>>=1;
    int root=father[lc[x]]=father[rc[x]]=merge(lc[x],rc[x]);
    lc[x]=rc[x]=dist[x]=0;
    return father[x]=father[root]=merge(x,root);
}
inline void query(int x,int y)
{   
    x=Find(x),y=Find(y);
    if (x==y)
       {
       printf("-1\n");
       return ;
       }
    x=update(x),y=update(y);
    int root=father[x]=father[y]=merge(x,y);
    printf("%d\n",val[root]);
}
inline void clear()
{
    memset(father,0,sizeof(father));
    memset(dist,0,sizeof(dist)),memset(val,0,sizeof(val));
    memset(lc,0,sizeof(lc)),memset(rc,0,sizeof(rc));
}
int main(){
    while (scanf("%d",&n)!=EOF)
          {
          clear();
          dist[0]=-1;
          for (register int i=1;i<=n;++i)
              father[i]=i,val[i]=read();
          m=read();
          for (register int i=1;i<=m;++i)
              {
              int x=read(),y=read();
              query(x,y);
              }
          }
    return 0;
}

G2020 19寒假集训Day1

一.分治

1.思想

2. 最近点对问题

二.左偏树

1.左偏树定义及性质

2.左偏树基本操作

1^o 合并(merge)

2^o 添加(add)

3^o 删除根节点(delete)

4^o 注意

三.例题：

1. P2713 罗马游戏

2. P1456 Monkey King

内容目录

选择主题

$1^o$ 合并(merge)

$2^o$ 添加(add)

$3^o$ 删除根节点(delete)

$4^o$ 注意