1.31总结

为什么和以前标题不一样了呢，是因为今天我感觉学到的东西太少了，很难按专题发，索性就直接写个总结水一篇好了

第一题：遍历问题

题解：真的纯思维题目，真的没啥，可说的，中序遍历取决于什么呢，我们通过上述实例，发现中序遍历的种类只取决于单个的结点（即我们只需要判断这个单个的没有兄弟的结点出现了几次）

通过思考我们会发现，这种单个的没有兄弟的结点出现的情况必然是在前序遍历中是‘AB’型，在后序遍历中就是‘‘BA’型，因此我们就可以循环去判断是否存在这样的结点

AC代码

#include <bits/stdc++.h>
using namespace std;

char a[100];
char b[100];
int main()
{
    scanf("%s",a);
    scanf("%s",b);
    int n=strlen(a);
    unsigned long long sum=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i]==b[j]&&a[i+1]==b[j-1]&&j-1>=0)
            {
                sum+=1;//统计单个结点的情况出现了多少次
            }
        }
    }
    int jie=1;
    for(int i=0;i<sum;i++)
    {
        jie*=2;//只需要没有一个结点就是2的n次方
    }
    printf("%d",jie);
    return 0;
}

 第二题：修复公路

题解：这题说难吧，也不是很难，就是需要在排序的时候用到快排，普通的排序会时间超限，

我们要对时间进行排序，让时间最少的先并在一起，然后遍历这块树，检查所有结点是否都并在一起，是否都并在一起我们要在并的操作上做一个处理，就是要下标大的并在下标小的上面，这样除了s[1]数组，别的存储的根节点都是1，有了思路就可以来看代码了

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int s[1005];
struct lu
{
    int x;
    int y;
    int t;
}l[100005];//将三个变量整成一个结构体，方便后续的交换
bool cmp(lu a,lu b)//升序来进行排列
{
    return a.t<b.t;
}
int temp;

int cha(int x)//查根节点
{
    while(s[x]>=0)
        x=s[x];
    return x;
}
void bing(int root1,int root2)//合并两个子树
{
    if(root1==root2) return ;
    if(root1<root2)
        s[root2]=root1;
    else
        s[root1]=root2;

}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        s[i]=-1;
    }
    for(int i=0; i<m; i++)
    {
        scanf("%d%d%d",&l[i].x,&l[i].y,&l[i].t);
    }
   sort(l,l+m,cmp);
    int sum;
    for(int i=0; i<m; i++)
    {
        sum=0;
        bing(cha(l[i].x),cha(l[i].y));
        for(int j=2; j<=n; j++)
        {
            if(s[j]!=-1)除了s[1]别的存储的都不会是-1这个数值
            {
                sum+=1;
                if(sum==n-1)//
                {
                    printf("%d",l[i].t);//输出最小时间
                    return 0;
                }
            }
        }
    }
    printf("-1");
    return 0;
}

 第三题：Grid Ice Floor

题解：这题相比于一般的深搜不一样，一般的的深搜是一步一步走，而这个是一下走到底，但终归还是大相径庭，很容易的就想到了

#include<stdio.h>
int dx[5]= {0,-1,0,1,0};//代表走法
int dy[5]= {0,0,-1,0,1};
int res;
char s[205][205];//棋盘数组
int book[205][205];//标记数组
int n,m;//棋盘大小
void dfs(int x,int y,int z)//x代表横坐标，y代表纵坐标，z代表方向
{
    int tx=x+dx[z];//在这个方向下一步所走到的地方
    int ty=y+dy[z];
    if(s[tx][ty]=='.')//如果可以通行
    {
        book[tx][ty]=1;//先标记了
        dfs(tx,ty,z);//在继续搜索
    }
    else//不能通行就说明碰到墙体了，这方向找完了
    {
        for(int i=1; i<5; i++)
        {
            tx=x+dx[i];//遍历四个方向的走法，看下次往哪个往哪个方向走
            ty=y+dy[i];
            if(s[tx][ty]=='#')//碰到墙体要排除，要在合法区间
                continue;
            while(book[tx][ty])
            {
                tx+=dx[i];
                ty+=dy[i];
            }
            if(s[tx][ty]=='.')//碰到路就继续标记，深搜
            {
                book[tx][ty]=1;
                dfs(tx,ty,i);
            }
        }
    }
}

int main()
{
    scanf("%d %d",&n,&m);//输入棋盘的大小
    getchar();
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
            scanf("%c",&s[i][j]);//输入棋盘布局
        getchar();
    }
    book[2][2]=1;//标记起始位置已经走过
    dfs(2,2,3);//肯定深搜俩方向，其余方向都是墙
    dfs(2,2,4);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(book[i][j])//只要标技术组标记过，就证明其访问过
                res++;
    printf("%d",res);
    return 0;
}