今天复习了二叉树和并查集还有快排，看了这周写的题目的题解，把每题的思路都过了一遍，然后自己敲了几遍并查集的find和merge函数，敲了两遍快排的函数，敲了两遍二叉树根据前序遍历建树，以及二叉树的前序遍历，中序遍历和后序遍历。上周的答辩着实答得不太彳亍，问就是记不得，说就是说不出，敲就是不熟练。不过毕竟是第一次答辩，第二次多少就有点经验了。况且上周都没复习过，题目做完了就没管了，这周多少还是吸取教训了。

---------------------快排模板（开了O2优化）
#include <stdio.h>
 void fast(int left,int right);
int a[1000001];
int n;
int main()
{

    scanf("%d",&n);
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    fast(0,n-1);
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    return 0;
}

 void fast(int left,int right)
 {
     int t,l=left,j=right,m=a[left];
     if(l>j)
        return ;
     while(l<j)
     {
         while(l<j&&a[j]>=m)j--;
         while(l<j&&a[l]<=m)l++;
         if(l<j)
         {
             t=a[l],a[l]=a[j],a[j]=t;
         }
     }
     a[left]=a[l];
     a[l]=m;
     fast(left,l-1);
     fast(l+1,right);
 }
题解
传统快排，按照子龙学长教的敲的
一堆数字，先取出第一个
然后从第二个开始
一个从左往右搜
一个从右往左搜
当左边找到比第一个大的
右边找到比第一个小的
这两个数字就换位
当左右相遇时，相遇的这个数字就和第一个交换
然后递归调用排序函数
继续如此排序左边和右边的数字
但我第一遍提交代码时超时了
然后开了O2优化才过的
快排在最坏的情况下时间复杂度跟冒泡是一样的
以至于个别案例过不了
-----------------------并查集模板
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int find(int x);
void merge(int i,int j);
int fa[10001];
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int i,x,y,z;
    for(i=1;i<=n;i++)
        fa[i]=i;
    for(i=0;i<m;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        if(x==1)
        {
            merge(y,z);
        }
        if(x==2)
        {
            if(find(y)==find(z))
                printf("Y\n");
            else printf("N\n");
        }

    }
    return 0;
}

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

void merge(int i,int j)
{
    fa[find(i)]=find(j);
}
题解
是一道并查集的模板题
我们使用一个数组
由于数据范围有限，且并不是也别大
于是我把数组开到比数据范围大一点
把每个元素的根节点都初始化为它自己
然后写两个函数，一个find用来查找
一个merge用来合并
find就是查找这个元素的根节点
当找到根节点就是自己的元素时停止
这个元素就是所查找元素的根节点
否则就递归调用find函数
merge则是将两个元素的根节点变为同一个
然后主函数用循环实现输入与输出的操作
但是第一遍交的时候时间也超限了
也是开了O2优化才过的，看来算法有待改进

改进版本

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int find(int x);
void merge(int i,int j);
int fa[10001];
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int i,x,y,z;
    for(i=1;i<=n;i++)
        fa[i]=i;
    for(i=0;i<m;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        if(x==1)
        {
            merge(y,z);
        }
        if(x==2)
        {
            if(find(y)==find(z))
                printf("Y\n");
            else printf("N\n");
        }

    }
    return 0;
}

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

 void merge(int i,int j)
{
    fa[find(i)]=find(j);
}
只改动了find函数
每次递归调用前都将该元素的父节点更新为根节点
这样后面的数据如果又有这个元素
则查找这个元素的根节点时会快很多
避免了重复的计算
改动后没开O2优化也过了
并且用时缩短了很多

二度改进

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int find(int x);
void merge(int i,int j);
int fa[10001],rank[10001];
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int i,x,y,z;
    for(i=1;i<=n;i++){
        fa[i]=i;
        rank[i]=1;
    }
    for(i=0;i<m;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        if(x==1)
        {
            merge(y,z);
        }
        if(x==2)
        {
            if(find(y)==find(z))
                printf("Y\n");
            else printf("N\n");
        }

    }
    return 0;
}

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

 void merge(int i,int j)
{
    int x=find(i),y=find(j);
    if(rank[x]<=rank[y])
        fa[x]=y;
    else fa[y]=x;
    if(rank[x]==rank[y]&&x!=y)
        rank[y]++;
}

这次改进的是结构
尽量使树的深度最小
因此新增了一个rank函数来表示深度
合并时选择深度最小的方案
提交后比上一次又快了10ms左右
---------------------------亲戚
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int find(int x);
void merge(int i,int j);
int fa[5001];
int main()
{
    int n,m,p;
    scanf("%d %d %d",&n,&m,&p);
    int i,x,y;
    for(i=1;i<=n;i++)
        fa[i]=i;
    for(i=0;i<m;i++)
    {
        scanf("%d %d",&x,&y);
        merge(x,y);
    }
    for(i=0;i<p;i++)
    {
        scanf("%d %d",&x,&y);
        if(find(x)==find(y))
            printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

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

 void merge(int i,int j)
{
    fa[find(i)]=find(j);
}
题解
和并查集模板题差不多
套用模板改一下输入输出就彳亍了
-------------------------朋友
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int find(int x);
void merge(int i,int j);
int findf(int x);
void mergef(int i,int j);
int fa[10001];
int fafa[10001];
int main()
{
    int n,m,p,q;
    scanf("%d %d %d %d",&n,&m,&p,&q);
    int i,x,y;
    for(i=1;i<=n;i++){
        fa[i]=i;}

        for(i=1;i<=m;i++){
            fafa[i]=i;}

    for(i=0;i<p+q;i++)
    {
        scanf("%d %d",&x,&y);
        if(x>0)merge(x,y);
        else mergef(-x,-y);
    }
    int girl=0,boy=0;
    for(i=1;i<=n;i++)
    {
        if(find(i)==find(1))
            boy++;
    }
    for(i=1;i<=m;i++)
    {
        if(findf(i)==findf(1))
            girl++;
    }
    if(boy>girl)printf("%d",girl);
    else printf("%d",boy);
    return 0;
}

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

 void merge(int i,int j)
{

    fa[find(i)]=find(j);
}

void mergef(int i,int j)
{
    fafa[findf(i)]=findf(j);
}

int findf(int x)
{
    if(fafa[x]==x)
        return x;
    else
        {
            fafa[x]=findf(fafa[x]);
            return fafa[x];
        }
}
题解
套用并查集模板完事
这题分了俩公司，输入有正有负
但观察发现，想脱单，必须和小明或小红社交
所以直接分头行动即可
分别搞清两个公司的社交关系
然后看有多少人是小明or小红的朋友
然后比较他俩朋友的多少，输出少的数量（包括他俩）
-------------------------修复公路
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int find(int x);
void merge(int i,int j);
int fa[200000];
int n,m;
int road[200000][3];
void fast(int left,int right);

int main()
{
    scanf("%d %d",&n,&m);
    int i,nx=n,t;
    for(i=1;i<=m;i++){
        scanf("%d %d %d",&road[i][0],&road[i][1],&road[i][2]);
        fa[i]=i;
    }
    if(n-1>m)
        printf("-1");
    else {
    fast(1,m);
    for(i=1;i<=m;i++)
    {
        if( find(road[i][0])!=find(road[i][1]) )
        {
            merge(road[i][0],road[i][1]);
            nx--;
        }
        if(nx==1)
        {
            t=road[i][2];
            printf("%d",t);
            break;
        }
    }
    if(nx>1)printf("-1");
    }
    return 0;
}

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

void merge(int i,int j)
{
    fa[find(i)]=find(j);
}

void fast(int left,int right)
{
    int t,l=left,j=right,x=road[left][2];
    if(l>j)
        return ;
    while(l<j)
    {
        while(l<j&&road[j][2]>=x)j--;
        while(l<j&&road[l][2]<=x)l++;
        if(l<j)
        {
            t=road[l][2],road[l][2]=road[j][2],road[j][2]=t;
            t=road[l][1],road[l][1]=road[j][1],road[j][1]=t;
            t=road[l][0],road[l][0]=road[j][0],road[j][0]=t;
        }
    }
    x=road[left][2],road[left][2]=road[l][2],road[l][2]=x;
    x=road[left][1],road[left][1]=road[l][1],road[l][1]=x;
    x=road[left][0],road[left][0]=road[l][0],road[l][0]=x;
    fast(left,l-1);
    fast(l+1,right);

}
题解
有n个村子，刚开始就有n个集合
用nx储存n的值
每当两个以前没联通的村子联通
集合就减少一个，当集合数量为1时
所有村子就都联通了
要输出最短时间，先将修路的时间排序
然后用并查集联通村子关系
当所有村子联通时，输出最后一条路的时间
所有路都修完还没全部联通，就输出-1
修路的时间与联通的村子用二维数组road储存
排序敲一个函数fast（传统快排）并调用即可
再敲并查集模板find查找和merge合并
主函数排序完后遍历所有路
先用find判断两村子是否联通，没联通则调用merge
然后集合总数nx--
nx值为1时，输出最后一条路的时间
遍历完后若nx>1，输出-1
-------------------------------搭配购买
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int n,m,q;
int v[20000],w[20000],f[20000];
int fa[20000];
int find(int x);
void merge(int i,int j);
int max(int x,int y);

int main()
{
    scanf("%d %d %d",&n,&m,&q);
    int i,j;
    for(i=1;i<=n;i++)
    {
        scanf("%d %d",&v[i],&w[i]);
        fa[i]=i;
    }
    int x,y;
    for(i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        v[find(y)]=v[find(y)]+v[find(x)];
        w[find(y)]=w[find(y)]+w[find(x)];
        v[find(x)]=0;w[find(x)]=0;
        merge(x,y);
    }
    for(i=1;i<=n;i++)
    {
        for(j=q;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    printf("%d",f[q]);
    return 0;
}

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

void merge(int i,int j)
{
    fa[find(i)]=find(j);
}

int max(int x,int y)
{
    if(x>y)return x;
    else return y;
}

题解
这题似乎要用01背包，于是去学了一下01背包
学懂了吗，那大概是没学懂的，会做了吗
可能可以做了，因为这个背包似乎只要套公式就行了
于是开始做题了
首先，要用这个公式，得创造使用条件
利用并查集，把必须一起买的云变成一朵大云
也就是把他们的价值与价钱合并
然后就成了典型的01背包，套公式即可
具体怎么变大云呢，这里我想了一会的
循环，利用find将两朵云的根找出来
将一个根的价值和价钱加到另一个跟
然后这个根的价值和价格清零
然后用merge函数合并两朵云
----------------------------求先序排列
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void dfs(int st,int fn,int ss,int nn);
char zhong[10];
char hou[10];
int n;
int kk=0;

int main()
{
    scanf("%s",zhong);
    scanf("%s",hou);
    n=strlen(hou);

    dfs(0,n-1,0,n-1);
    return 0;
}

void dfs(int st,int fn,int ss,int nn)
{
    if(st>fn)return ;
     printf("%c",hou[fn]);
     int p=ss;
     while(zhong[p]!=hou[fn])
        p++;
     dfs(st,p-ss+st-1,ss,p-1);
     dfs(p-ss+st,fn-1,p+1,nn);
}

题解
中序是左父右，后序是左右父
根据后序可以找到根节点
找到根节点后可以在中序里找到左右子树
先序遍历是父左右，因此只要找父节点并输出即可
建立dfs函数，参数为中序和后序的遍历范围
在后序中找到根节点并输出
在中序中找到根节点并纪录位置
计算左子树的节点个数
更新遍历范围
递归调用dfs，先找左子树的根节点，再找右子树
--------------------------刻录光盘
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
int main()
{
    int n;
    scanf("%d",&n);
    int fa[300];
    int vis[300][300]={0};
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&k);
        while(k!=0)
        {
            vis[i][k]=1;
            scanf("%d",&k);
        }
        fa[i]=i;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        for(k=1;k<=n;k++)
        if(vis[i][k]==1&&vis[k][j]==1)
        vis[i][j]=1;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(vis[i][j]==1)
            {
                fa[j]=fa[i];
            }
        }
    }
    int sum=0;
    for(i=1;i<=n;i++)
    {
        if(fa[i]==i)
            sum++;
    }
    printf("%d",sum);
    return 0;
}
题解
一维数组fa储存每个人的根
二维数组vis储存每个人的信息
每个人的根初始化为自己
输入每个人的信息到vis中
然后嵌套循环，枚举每个人的情况
如果一号愿意给二号或者一号愿意给二号且二号愿意给三号
那么一号就是二号和三号的根，用vis标记
然后根据vis中标记的情况替换每个人的根
然后遍历每个人，每出现一个根为自己的，光盘数就加一
-----------------------------美国血统
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void dfs(int st,int fn,int ss,int nn);
char zhong[50];
char qian[50];
int n;

int main()
{
    scanf("%s",zhong);
    scanf("%s",qian);
    n=strlen(qian);

    dfs(0,n-1,0,n-1);
    return 0;
}

void dfs(int st,int fn,int ss,int nn)
{
    if(st>fn)return ;
     int p=ss;
     while(zhong[p]!=qian[st])
        p++;
     int sum=p-ss;
     dfs(st+1,sum+st,ss,p-1);
     dfs(sum+st+1,fn,p+1,nn);
     printf("%c",zhong[p]);
}

题解
跟之前的求先序一样的题型，这次是求后序
方法跟求先序差不多，根据先序找到根
找到根后可以从中序里找到左右子树
然后递归调用，之前求先序，先序是父左右
先输出跟，再dfs左子树，再dfs右子树
这次是求后序，后序是左右父
先dfs左子树，再dfs右子树，最后输出根
要注意每次调用dfs的起点和终点
我在这里卡住了，起点终点搞错了几次
这次是根据先序求后序，先序的根在最前面
所以起点终点都会跟之前后序求先序不一样
-------------------------------二叉树深度
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int sum=0;
void dfs(int x,int step);
int fa[1000005][2];

int n;

int main()
{
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++)
    {
        scanf("%d %d",&fa[i][0],&fa[i][1]);
    }
    dfs(1,1);
    printf("%d",sum);
    return 0;
}

void dfs(int x,int step)
{
    if(fa[x][0]==0&&fa[x][1]==0)
    {
        if(sum<step)sum=step;
        return ;
    }
    if(fa[x][0]!=0)
    dfs(fa[x][0],step+1);
    if(fa[x][1]!=0)
    dfs(fa[x][1],step+1);
}

题解
这题求树的深度，题目里还把深度俩字给加粗了
好家伙，都明示了呗，那我肯定用深度优先搜索咯
先拿二维数组fa储存每个节点的数据
然后开搜，当遇到叶子结点时结束
没遇到叶子结点就继续搜左右结点
每搜一次步数加一，全部搜完后
输出最大的步数即可
-----------------------------新二叉树
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int sum=0;
void dfs(char x);
char fa[30][3];
int n;

int main()
{
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++)
    {
        scanf("%s",fa[i]);
    }
    dfs(fa[1][0]);

    return 0;
}

void dfs(char x)
{
    int i;
    printf("%c",x);
    for(i=1;i<=n;i++)
    {
        if(fa[i][0]==x)
            break;
    }
    if(fa[i][1]=='*'&&fa[i][2]=='*')
    {
        return ;
    }
    if(fa[i][1]!='*')
    dfs(fa[i][1]);
    if(fa[i][2]!='*')
    dfs(fa[i][2]);
}

题解
刚做完求深度的题，用的深搜
于是我想这题应该也能用深搜做
完事把求深度的代码改了一下
就变成这题的AC代码了
二维字符数组fa储存每个节点的信息
dfs函数接收父节点作为参数
先输出父节点，然后递归找左节点
再递归找右节点，父左右先序遍历
没有左右节点则返回
------------------------------

总计5h

明日放假