大二博客总结（第三周）

本周的学习内容： 1.学习了并查集，二叉树，做了配套的题目巩固 2.剩余时间在刷洛古的题目。每类题单都有刷几道（还没根据模块具体刷） 3.利用题目复习线性DP，贪心

并查集

模板题：n个人，m组朋友关系，能形成几个团体。 并查集的操作可分为： 1.初始化（也就是把每个点设置为独立的集，每个对象都是不想交的集合）

void init(int n)            //初始化
{
    for(int i=1;ih[y])
        a[y]=a[x];
    else
    {
        if(h[x]==h[y])
            h[y]+=1;   //要和h[x]小于h[y]的情况一起考虑
        a[x]=a[y];
    }
}

二叉树

深度优先遍历：（运用深搜） 先序遍历（父节点、左儿子、右儿子）

void preorder(node *root)  //求先序排列
{
    if(root!=NULL)
    {
        post[k++]=root->value;
        preorder(root->l);
        preorder(root->r);
    }
}

中序遍历（左儿子、父节点、右儿子）

void inorder(node *root)
{
    if(root!=NULL)
    {
        inorder(root->l);
        post[k++]=root->value;
        inorder(root->r);
    }
}

后续遍历（左儿子、右儿子、父节点）

void postorder(node *root)
{
    if(root!=NULL)
    {
        postorder(root->l);
        postorder(root->r);
        post[++k]=root->value;
    }
}

查找后序的建树方式： 由于先序的第一个值为根节点，利用中序便可划分为左孩子、后孩子。不断查找相等的值，再根据递归进行分类，便将树建成。而后序函数只是起到打印输出的作用。关键点：还是找到规律，然后建树

void buildtree(int l,int r,int &t,node* &root)
{
    int f=-1;
    for(int i=l;il) buildtree(l,f-1,t,root->l);
    if(fr);
}

洛古1090

合并果子，第一个想法是DP，与合并石子相似。由于果子合并会生成一个新堆，需要不断排序，但这样会超时。因此采用优先队列，每次取得两个值，然后放进去一个，不断累加体力值即可。 优先队列：（从小到大取出）

priority_queueq; // 从小到大
priority_queueq; //从大到小

洛古 P3817

把题目想复杂了。正解：先将每碓果子多余x的部分先拿走，然后从第二堆开始，加上前一堆的糖果，再拿走多余x的部分。我刚开始做法只关注偶数堆的糖果，保证这堆各自加上周围堆糖果数，不超过x；然后将堆数是偶数的情况中，保证最后一堆也满足条件。

P1106 删数问题

一开始就掉坑里了，以为删除字符串中最大的几个数，剩下的数组合自然最小。 eg： 1529 若是这个思路删除的是‘9’，变成152；但129才是最小的，应该删除5. 所以共要删除k的数，应该从字符串前面开始删除，如果前面的数字大于后面的，则删除他，后面数字向前移动一位。 此外还要考虑到前导0的情况，存在的一个小坑是： 值若是10000，则删除1，剩下的是个0，字符串长度也为4，所以删除的时候要加上g