20186gdoi13

树

Posted on Edited on In Valine:
Symbols count in article: 11k Reading time ≈ 10 mins.
Thematic004

堆排序

例题：LuoguP3378

手打堆排序模板

从小到大（小根堆）

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
#include <bits/stdc++.h>
using namespace std;

int n,x,heap[10005],size;

void up(int p)
  {
  while (p>1)
    {
    if (heap[p]<heap[p/2])
      {
      swap(heap[p],heap[p/2]);
      p/=2;
      }
    else break;
    }
  }

void insert(int val)
  {
  heap[++size]=val;
  up(size);
  }

void down(int p)
  {
  int s=p*2;
  while (s<=size)
    {
    if (s<size&&heap[s+1]<heap[s]) s++;
    if (heap[s]<heap[p])
      {
      swap(heap[s],heap[p]);
      p=s;
      s=p*2;
      }
    else break;
    }
  }
  
void extract()
  {
  heap[1]=heap[size--];
  down(1);
  }
  
inline int gettop()
  {
  return heap[1];
  }

int main()
  {
  scanf("%d",&n);
  while (n--)
    {
    scanf("%d",&x);
    insert(x);
    }
  long long ans=0;
  while (size>=1)
    {
    int top=gettop();
    extract();
    printf("%d ",top);
    }
  return 0;
  }

从大到小（大根堆）

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
#include <bits/stdc++.h>
using namespace std;

int n,x,heap[10005],size;

void up(int p)
  {
  while (p>1)
    {
    if (heap[p]>heap[p/2])
      {
      swap(heap[p],heap[p/2]);
      p/=2;
      }
    else break;
    }
  }

void insert(int val)
  {
  heap[++size]=val;
  up(size);
  }

void down(int p)
  {
  int s=p*2;
  while (s<=size)
    {
    if (s<size&&heap[s+1]<heap[s]) s++;
    if (heap[s]>heap[p])
      {
      swap(heap[s],heap[p]);
      p=s;
      s=p*2;
      }
    else break;
    }
  }
  
void extract()
  {
  heap[1]=heap[size--];
  down(1);
  }
  
inline int gettop()
  {
  return heap[1];
  }

int main()
  {
  scanf("%d",&n);
  while (n--)
    {
    scanf("%d",&x);
    insert(x);
    }
  long long ans=0;
  while (size>=1)
    {
    int top=gettop();
    extract();
    printf("%d ",top);
    }
  return 0;
  }

STL堆排序模板

从小到大（小根堆）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int n,x;
priority_queue <int,vector<int>,greater<int> > Q;

int main()
  {
    scanf("%d",&n);
    while (n--)
      {
        scanf("%d",&x);
        Q.push(x);
    }
  while (!Q.empty())
    {
      printf("%d ",Q.top());
      Q.pop();
    }
  return 0;
  }

从大到小（大根堆）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int n,x;
priority_queue <int> Q;
// Or "priority_queue <int,vector<int>,less<int> > Q;"

int main()
  {
    scanf("%d",&n);
    while (n--)
      {
        scanf("%d",&x);
        Q.push(x);
    }
  while (!Q.empty())
    {
      printf("%d ",Q.top());
      Q.pop();
    }
  return 0;
  }

最小生成树

例题：LuoguP3366

Kruskal

数组版

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
#include<bits/stdc++.h>
using namespace std;

struct Edge
  {
    int start,to,cost;
  }edge[200005];
int f[5005],n,m,ans,fx,fy,cnt;

bool cmp(Edge a,Edge b)
  {
    return a.cost<b.cost;
  }

int find(int x)
  {
    if (x==f[x]) return x;
    return f[x]=find(f[x]);
  }

int Kruskal(void)
  {
    sort(edge+1,edge+1+m,cmp);
    for (int i=1;i<=m;i++)
      {
        fx=find(edge[i].start), fy=find(edge[i].to);
        if (fx==fy) continue;
        ans+=edge[i].cost;
        f[fy]=fx;
        if (++cnt==n-1) break;
      }
  }

int main()
  {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) f[i]=i;
    for (int i=1;i<=m;i++) scanf("%d%d%d",&edge[i].start,&edge[i].to,&edge[i].cost);
    printf("%d",Kruskal());
    return 0;
  }

优先队列版

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
#include<bits/stdc++.h>
using namespace std;
 
struct Edge
  {
    int start,to,cost;
    bool operator < (const Edge &a) const
      {
        return a.cost<cost;
      }
  };
int f[5005],n,m,start,to,cost,fx,fy,fz;
priority_queue <Edge> Q;
 
int find(int x)
  {
    if (x==f[x]) return x;
    return f[x]=find(f[x]);
  }

int Kruskal(void)
  {
    int cnt=0,ans=0;
  while (!Q.empty())
      {
        fx=find(Q.top().start), fy=find(Q.top().to);
        fz=Q.top().cost;
        Q.pop();
        if (fx==fy) continue;
        ans+=fz;
        f[fy]=fx;
        if (++cnt==n-1) return ans;
      }
  }

int main()
  {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) f[i]=i;
    for (int i=1;i<=m;i++)
      {
        scanf("%d%d%d",&start,&to,&cost);
        Q.push((Edge){start,to,cost});
      }
    printf("%d",Kruskal());
    return 0;
  }

Prim

邻接矩阵版（咕咕ing）

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
#include <bits/stdc++.h>
using namespace std;

bool vis[105];
int n,ans,minn[105],a[105][105];

int Prim(void)
  {
    for(int i=1;i<=n;i++)
      {
        int k=0;
        for(int j=1;j<=n;j++) if(!vis[j]&&minn[j]<minn[k]) k=j;
        vis[k]=true;
        for(int j=1;j<=n;j++) if(!vis[j]&&a[k][j]<minn[j]) minn[j]=a[k][j];
      }
    for (int i=1;i<=n;i++) ans+=minn[i];
    return ans;
  }

int main()
  {
    memset(minn,0x7f,sizeof(minn));
    scanf("%d",&n);
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&a[i][j]);
    printf("%d",Prim());
    return 0;
  }

最近公共祖先（LCA）

例题：LuoguP3379

倍增

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
#include <bits/stdc++.h>
using namespace std;

struct Edge
  {
  int t,next;
  }Edge[2*500001];
int depth[500001],f[500001][22],log1[500001],head[500001];
int tot,n,m,s;

inline void addedge(int x,int y)
  {
    Edge[++tot].t=y;
  Edge[tot].next=head[x];
  head[x]=tot;
  Edge[++tot].t=x;
  Edge[tot].next=head[y];
  head[y]=tot;
  }

void dfs(int now,int last)
  {
    depth[now]=depth[last]+1;
    f[now][0]=last;
    for (int i=1;(1<<i)<=depth[now];i++) f[now][i]=f[f[now][i-1]][i-1];
  for (int i=head[now]; i; i=Edge[i].next) if (Edge[i].t!=last) dfs(Edge[i].t,now);
  } 

int LCA(int x,int y)
  {
    if (depth[x]<depth[y]) swap(x,y);
    while (depth[x]>depth[y]) x=f[x][log1[depth[x]-depth[y]]-1];
    if (x==y) return x;
    for (int i=log1[depth[x]]-1;i>=0;i--) if (f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];
  return f[x][0];
  }

int main()
  {
    int x,y;
  scanf("%d%d",&n,&s);
    for (int i=1;i<n;i++)
      {
        scanf("%d%d",&x,&y);
        addedge(x,y);
    }
  dfs(s,0);
  for (int i=1;i<=n;i++) log1[i]=log1[i-1]+(1<<log1[i-1]==i);
    scanf("%d%d",&x,&y);
    printf("%d\n",LCA(x,y));
  return 0;
  }

二叉树遍历

给出前序遍历与中序遍历，求出后序遍历

例题：LuoguP1827

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

void Map(char s1[],char s2[],char s[],int n)
  {
  if (n<=0) return;
  int k=strchr(s2,s1[0])-s2;
  Map(s1+1,s2,s,k);
  Map(s1+k+1,s2+k+1,s+k,n-k-1);
  s[n-1]=s1[0];
  }
  
int main()
  {
  char s[30],s1[30],s2[30];
  scanf("%s%s",s1,s2);
  int len=strlen(s1);
  Map(s1,s2,s,len);
  s[len]=0;
  puts(s);
  return 0;
  }

给出中序遍历与后序遍历，求出前序遍历

例题：LuoguP1030

代码

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
#include <bits/stdc++.h>
using namespace std;

string a,b;

void build(string k1,string k2)
  {
  if (k1.size()>0)
    {
    cout<<k2[k2.size()-1];
    int k=k1.find(k2[k2.size()-1]);
    build(k1.substr(0,k),k2.substr(0,k));
    build(k1.substr(k+1),k2.substr(k,k1.size()-k-1));
    }
  }
  
int main()
  {
  ios::sync_with_stdio(0);
  cin.tie(0);
  string a,b;
  cin>>a>>b;
  build(a,b);
  return 0;
  }

树状数组

一维树状数组

单点修改，区间查询

例题1：LuoguP3374

例题2：LOJ#130

代码

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
#include <bits/stdc++.h>
using namespace std;

int oper,a,b,k,n,m,tree[2000005];

inline int lowbit(int num)
  {
    return num&-num;
  }

void add(int num,int x)
  {
    while (num<=n)
      {
        tree[num]+=x;
        num+=lowbit(num);
    }
  }

int sum(int num)
  {
    int ans=0;
    while (num!=0)
      {
        ans+=tree[num];
        num-=lowbit(num);
    }
  return ans;
  }

int main()
  {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
      {
        scanf("%d",&k);
        add(i,k);
    }
  while (m--)
    {
      scanf("%d%d%d",&oper,&a,&b);
      if (oper==1) add(a,b);
      else if (oper==2) printf("%d\n",sum(b)-sum(a-1));
    }
  return 0;
  }

区间修改，单点查询

例题1：LuoguP3368

例题2：LOJ#131

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
#include <bits/stdc++.h>
using namespace std;

long long oper,a,b,k,last,n,m,tree[1000005];

inline long long lowbit(long long num)
  {
    return num&-num;
  }

void add(long long num,long long x)
  {
    while (num<=n)
      {
        tree[num]+=x;
        num+=lowbit(num);
    }
  }

long long sum(long long num)
  {
    long long ans=0;
    while (num!=0)
      {
        ans+=tree[num];
        num-=lowbit(num);
    }
  return ans;
  }

int main()
  {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
      {
        cin>>a;
        add(i,a-last);
        last=a;
    }
  while (m--)
    {
      cin>>oper;
      if (oper==1)
        {
          cin>>a>>b>>k;
          add(a,k);
          add(b+1,-k);
      }
    else
      {
        cin>>a;
        cout<<sum(a)<<"\n";
      }
    }
  return 0;
  }

离散化

例题：LuoguP1908

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
#include <bits/stdc++.h>
using namespace std;

struct Data
  {
    int c,id;
  }a[500005];

long long ans;
int n,tree[500005],rank[500005];

bool cmp(Data x,Data y)
  {
    if (x.c!=y.c) return x.c<y.c;
    return x.id<y.id;
  }

inline int lowbit(int num)
  {
  return num&-num;
  }

int sum(int num)
  {
  int s=0;
  while(num>0)
    {
    s+=tree[num];
    num-=lowbit(num);
    }
  return s;
  }

void add(int num,int x)
  {
  while(num<=n)
    {
    tree[num]+=x;
    num+=lowbit(num);
    }
  }

int main()
  {
  scanf("%d",&n);
  for (int i=1;i<=n;i++) scanf("%d",&a[i].c),a[i].id=i;
  sort(a+1,a+1+n,cmp);
  for (int i=1;i<=n;i++) rank[a[i].id]=i;
  for (int i=1;i<=n;i++)
    {
    add(rank[i],1);
    ans+=i-sum(rank[i]);
    }
  printf("%lld",ans);
  return 0;
  }

二维树状数组

单点修改，区间查询

例题：LOJ#133

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
#include <bits/stdc++.h>
using namespace std;

long long oper,x,y,k,xa,xb,ya,yb,n,m,tree[5005][5005];

inline long long lowbit(long long p)
  {
    return p&-p;
  }

void add(long long num1,long long num2,long long k)
  {
    for (long long i=num1;i<=n;i+=lowbit(i))
             for (long long j=num2;j<=m;j+=lowbit(j))
                 tree[i][j]+=k;
  }

long long sum(long long num1,long long num2)
  {
    long long ans=0;
    for (long long i=num1;i>0;i-=lowbit(i))
             for (long long j=num2;j>0;j-=lowbit(j))
                 ans+=tree[i][j];
  return ans;
  }

int main()
  {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
  while (cin>>oper)
    {
      if (oper==1)
        {
          cin>>x>>y>>k;
          add(x,y,k);
      }
      else if (oper==2)
        {
          cin>>xa>>ya>>xb>>yb;
                        int ans=sum(xb,yb)+sum(xa-1,ya-1)-sum(xa-1,yb)-sum(xb,ya-1);
          cout<<ans<<"\n";
      }
    }
  return 0;
  }

并查集

例题：LuoguP3367

初始化

1
2
3
4
void inti(int n)
  {
    for (int i=1;i<=n;i++) f[i]=i;
  }

寻找父亲

1
2
3
4
5
int find(int x)
  {
    if (x==f[x]) return x;
    return f[x]=find(f[x]);
  }

合并

1
2
3
4
5
void merge(int x,int y)
  {
    int fx=find(x),fy=find(y);
    f[fy]=fx;
  }

判断父亲是否相同

1
2
3
4
5
bool check(int x,int y)
  {
    int fx=find(x),fy=find(y);
    return fx==fy;
  }

例题代码

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
#include <bits/stdc++.h>
using namespace std;

int n,T,oper,a,b,f[10005];

void inti(int n);
int find(int x);
void merge(int x,int y);
bool check(int x,int y);

void inti(int n)
  {
    for (int i=1;i<=n;i++) f[i]=i;
  }

int find(int x)
  {
    if (x==f[x]) return x;
    return f[x]=find(f[x]);
  }

void merge(int x,int y)
  {
    int fx=find(x),fy=find(y);
    f[fy]=fx;
  }

bool check(int x,int y)
  {
    int fx=find(x),fy=find(y);
    return fx==fy;
  }

int main()
  {
    scanf("%d%d",&n,&T);
    inti(n);
    while (T--)
      {
        scanf("%d%d%d",&oper,&a,&b);
        if (oper==1) merge(a,b);
        else
          {
            if (check(a,b)) printf("Y\n");
            else printf("N\n");
      }
    }
  return 0;
  }