数据结构与算法题目集(中文) - 7-27 家谱处理(30 分)

简介: 数据结构与算法题目集(中文) - 7-27 家谱处理(30 分)

题目链接:点击打开链接

题目大意:略。

解题思路:略。

AC 代码


#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
struct cmp
{
    bool operator()(const char* s1,const char* s2) const
    {
        return strcmp(s1,s2)<0; // default:map 根据 key 排序(字典序)
    }
};
map<char*,int,cmp> mp;
struct node
{
    char name[20];
    int par,space;
}*tree;
int n,m;
int calSp(char name[])
{
    char c;
    int cnt=0,k=0;
    while((c=getchar())==' ') cnt++;
    do
    {
        name[k++]=c;
    }while((c=getchar())!='\n');
    name[k]='\0';
    return cnt;
}
// 往前遍历第一个比他缩进少的就是他的父亲,否则就是亚当夏娃
int trace(int child)
{
    for(int i=child-1;i>=0;i--)
        if(tree[i].space<tree[child].space) return i;
    return -1;
}
int jde_child_parent(int aid, int bid)
{
    if(tree[aid].par==aid) tree[aid].par=trace(aid);
    return tree[aid].par==bid;
}
int jde_sibling(int aid, int bid)
{
    if(tree[aid].par==aid) tree[aid].par=trace(aid);
    if(tree[bid].par==bid) tree[bid].par=trace(bid);
    return tree[aid].par==tree[bid].par;
}
int jde_desce_ancest(int aid, int bid)
{
    while(aid!=-1)
        if(jde_child_parent(aid,bid)) return 1;
        else aid=tree[aid].par;
    return 0;
}
void solve()
{
    char a[20],with[20],b[20];
    scanf("%s%*s%*s%s%*s%s",a,with,b);
    int rs,aid=mp[a],bid=mp[b];
    char op=with[0];
    if(op=='c') rs=jde_child_parent(aid,bid);
    else if(op=='p') rs=jde_child_parent(bid,aid);
    else if(op=='s') rs=jde_sibling(aid,bid);
    else if(op=='d') rs=jde_desce_ancest(aid,bid);
    else if(op=='a') rs=jde_desce_ancest(bid,aid);
    puts(rs?"True":"False");
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        mp.clear();
        tree=(node*)malloc(sizeof(node)*n);
        getchar();
        for(int i=0;i<n;i++)
        {
            tree[i].space=calSp(tree[i].name);
            tree[i].par=i; // init
            mp[tree[i].name]=i;
        }
        tree[0].par=-1;
        for(int i=0;i<m;i++) solve();
    }
    return 0;
}
目录
相关文章
|
4月前
|
存储 SQL 算法
LeetCode题目113:多种算法实现 路径总和ll
LeetCode题目113:多种算法实现 路径总和ll
|
2月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
39 6
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
4月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
4月前
|
算法 机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
下一篇
无影云桌面