【4.12日题解】——美国血统

简介: 【4.12日题解】——美国血统

☘前言☘

今日份水题开始。希望有想要提高的同学跟我们一起来刷题0.0

4.12日每日一题——美国血统


🧑🏻作者简介:一个从工业设计改行学嵌入式的年轻人

✨联系方式:2201891280(QQ)

⏳全文大约阅读时间: 20min


全文目录

☘前言☘

解题思路

📑写在最后

P1827 [USACO3.4] 美国血统 American Heritage


解题思路

这部分其实是考研的重点,太长时间不用都快忘记了,其实思路就是分割字符串,比如给的样例。


ABEDFCHG

CBADEFGH


分割之后的样子就应该是:


[ABEDF]C[HG]

C[BADEF][GH]


这个对应着代码去看下标就能理解了。


#include <cstdio>

#include <cstring>

#include <cstdlib>



struct node{
    char val;
    struct node *left, *right;
};
struct node *noot;
char zhongxu[30], prev[30];
void create(int zleft, int zright, int pleft,int pright,node **root){//生成树
    if(zleft > zright || pleft > pright)    return;//直接就是空啦
    int i,j;
    for(i = pleft, j = zleft;i < pright;i++,j++)    //查找分割点
        if(zhongxu[j] == prev[pleft]) break;
    (*root) = (struct node *)malloc(sizeof(struct node));   //建立节点
    node *p = *root;
    p->val = prev[pleft];
    p->left = p->right = NULL;
    create(zleft,j-1,pleft+1, i,&p->left);  //创建左子树
    create(j+1,zright,i+1,pright,&p->right);    //创建右子树
}
void hou(node *p){  //后续遍历
    if(p){
        hou(p->left);
        hou(p->right);
        putchar(p->val);
    }
}
int main(){
    scanf("%s %s",zhongxu,prev);
    node *root;
    create(0,strlen(zhongxu) - 1,0, strlen(prev) - 1,&root);
    hou(root);
}



相关文章
|
数据安全/隐私保护
[羊城杯 2020]easyre 1题解
buuctf-[羊城杯 2020]easyre 1题解
435 0
[羊城杯 2020]easyre 1题解
2022第十三届届蓝桥杯c++B组题解
2022第十三届届蓝桥杯c++B组题解
88 1
|
算法
山东第一届省赛 Greatest Number(优雅暴力+二分)
山东第一届省赛 Greatest Number(优雅暴力+二分)
71 1
|
C++
【PAT甲级 - C++题解】1070 Mooncake
【PAT甲级 - C++题解】1070 Mooncake
54 1
|
C++
【PAT甲级 - C++题解】1147 Heaps
【PAT甲级 - C++题解】1147 Heaps
70 0
|
存储 C++ 网络架构
【PAT甲级 - C++题解】1062 Talent and Virtue
【PAT甲级 - C++题解】1062 Talent and Virtue
58 0
|
C++
【PAT甲级 - C++题解】1116 Come on! Let‘s C
【PAT甲级 - C++题解】1116 Come on! Let‘s C
88 0
|
存储 C++
【PAT甲级 - C++题解】1095 Cars on Campus
【PAT甲级 - C++题解】1095 Cars on Campus
75 0
|
存储 C++
【PAT甲级 - C++题解】1002 A+B for Polynomials
【PAT甲级 - C++题解】1002 A+B for Polynomials
55 0