`
huyifan951124
  • 浏览: 82737 次
社区版块
存档分类
最新评论

hdu5444 模拟

 
阅读更多

题目大意:给你一棵树的先序遍历和中序遍历,让你求给定点的位置。

算法思路:根据中序遍历和先序遍历的特点,模拟即可(这模拟模了我快三小时,我也是醉了)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
#define MAXN 1005
string str[MAXN];
int t,n,q;
int a[MAXN],b[MAXN];
bool visited[MAXN];
int main()
{
    scanf("%d",&t);

    while(t--)
    {
        memset(visited,false,sizeof(visited));
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }

        for(int i=1; i<=n; i++)
        {
            str[i]="";
        }
        for(int i=1; i<=n; i++)
        {
            b[a[i]]=i;
        }
        visited[a[1]]=true;
        //左子树
        for(int i=2; i<=a[1]; i++)
        {
            if(a[i]<a[i-1])
            {
                str[a[i]]=str[a[i-1]]+'E';
                visited[a[i]]=true;
            }
            else if(a[i]>a[i-1])
            {
                int f=a[i];
                while(f>1)
                {
                    f--;
                    if(visited[f]&&b[f]<b[a[i]])
                        break;
                }
                str[a[i]]=str[a[b[f]]]+'W';
                visited[a[i]]=true;
            }
        }
        //右子树
        int k=1+a[1];
        if(a[k]<a[1])
        {
            str[a[k]]=str[a[1]]+'E';
            visited[a[k]]=true;
        }
        else if(a[k]>a[1])
        {
            int f=a[k];
            str[a[k]]=str[a[1]]+'W';
            visited[a[k]]=true;
        }

        for(int i=a[1]+2; i<=n; i++)
        {
            if(a[i]<a[i-1])
            {
                str[a[i]]=str[a[i-1]]+'E';
                visited[a[i]]=true;
            }
            else if(a[i]>a[i-1])
            {
                int f=a[i];
                while(f>a[1])
                {
                    f--;
                    if(visited[f]&&b[f]<b[a[i]])
                        break;
                }
                str[a[i]]=str[a[b[f]]]+'W';
                visited[a[i]]=true;
            }
        }

        scanf("%d",&q);
        for(int i=1; i<=q; i++)
        {
            int x;
            scanf("%d",&x);
            cout<<str[x]<<endl;
        }

    }
}

 

0
0
分享到:
评论

相关推荐

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中...1030 简单题,可用模拟过 等等。 ACM HDU 题目分类是一个非常重要的参考资源,对于编程选手来说,掌握这些分类可以帮助他们更好地理解和解决问题。

    ACM HDU

    7. **模拟法**:直接按照题目描述进行程序模拟,解决一些逻辑性较强的问题。 学习和理解ACM HDU的题解,不仅可以提升编程能力,还能帮助我们理解和运用计算机科学的核心原理,为日常开发工作提供有力的支持。同时,...

    HDU acm-PPT课件

    模拟竞赛是提高实战能力的有效方式,通过参与在线判题平台(如HDU OJ)的练习,可以锻炼快速阅读题目、理解和解决问题的能力。同时,ACM竞赛强调团队协作,学习如何与队友有效沟通,分工合作,共同解决问题,也是...

    ACM hdu 代码大全3000例,部分代码有详细解析

    - 模拟竞赛:通过模拟真实的ACM比赛环境,提升解决实际问题的速度和准确率。 总之,"ACM HDU代码大全3000例"是一个宝贵的编程学习资源,无论你是初学者还是经验丰富的程序员,都能从中受益匪浅。通过学习和实践...

    hdu 300+ AC 代码

    大数计算的应用包括加密算法、金融计算和数学模拟等。在编程竞赛中,大数问题可能涉及到加减乘除、模运算以及大数比较等操作。 2. **线段树**:线段树是一种数据结构,用于高效地处理区间查询和更新操作。它可以...

    hdu2000-2014ac代码

    7. **模拟法**:对于一些规则明确的问题,可以通过编写程序模拟其过程来求解。 8. **编码技巧**:如何有效地输出答案,处理输入数据,避免溢出等。 这个压缩包里的代码可能是对上述知识点的具体实现,通过阅读和...

    ACM HDU 2000-2099 解题报告 杭电 ACM

    8. **学习方法**:解题报告也可能提供学习和训练的建议,如如何选择练习题目,如何分析和总结解题经验,以及如何通过模拟赛提升实战能力。 9. **案例分析**:通过对典型题目的深度剖析,报告可以帮助读者理解复杂...

    HDU ACM JAVA 部分题目源代码

    HDU ACM(全称:Hangzhou Dianzi University Algorithm Competition)是杭州电子科技大学举办的一项在线算法竞赛,旨在提升参赛者的问题解决能力和编程技巧,特别是使用JAVA等编程语言解决算法问题的能力。...

    HDU_软工_计组实验1~8

    【标题】"HDU_软工_计组实验1~8"所涵盖的知识点主要集中在计算机组织(简称计组)的实践操作层面,这通常包括对计算机硬件结构、指令系统、存储器体系、数据表示以及处理器工作原理等基础知识的深入理解和应用。...

    HDU 杭电操作系统实验 (通过验收)

    包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...

    hdu1020.rar_hdu1020

    这个题目要求参赛者编写一个程序,模拟一个猜数字的游戏过程,其中游戏规则相当简单:计算机随机选择一个介于1到N之间的整数,玩家有若干次机会猜测这个数字,每次猜测后,计算机会给出提示,告诉玩家猜的数字是偏大...

    2019 Multi-University Training Contest 4(2019hdu多校第五场数据与标程).zip

    这个资源对于学习者来说,是一个绝佳的实践平台,可以模拟真实的竞赛环境,通过解题来提升编程思维、算法设计和调试技巧。不仅如此,研究标程也能帮助学习者了解更高效或者更优雅的编程方式,提升代码质量。对于准备...

    bfs.rar_hdu

    题目“bfs.rar_hdu”暗示了这是一个关于广度优先搜索(Breadth-First Search, BFS)的问题,源自HDU(杭州电子科技大学)的在线编程竞赛平台。通常,这类题目会涉及图论或者树的遍历,考察算法实现和逻辑思维能力。 ...

    HDU-2000-2099.rar_hdu

    9. **模拟与建模**:2351-2400号题目可能需要对实际问题进行抽象,通过编写程序模拟现实世界中的过程。 10. **位运算**:位运算在某些情况下可以提高代码的运行效率,2401-2450号题目可能会用到位运算技巧来解决...

    hdu5102.zip_K.

    标题中的"hdu5102.zip_K."暗示这是一个与编程竞赛相关的题目,通常在HDU(杭州电子科技大学)在线判题系统中出现。这个题目可能是一个编程挑战,要求参赛者解决一个特定的问题,并提交源代码以供自动评判。"K."可能...

    HDU公选课抢课插件

    HDU公选课抢课插件是一款专为杭州电子科技大学(HDU)方正教学平台设计的自动化脚本工具,其主要目标是帮助用户在公选课报名时提高成功率,解决由于课程名额有限、手动操作速度慢而导致的抢课难题。这款插件的设计...

    hdu acm教案5-7

    5. **模拟**:针对一些实际问题进行精确的计算机模拟,如计数、概率计算等。 6. **贪心策略**:对于一些局部最优能保证全局最优的问题,贪心算法是有效的解决手段。 7. **复杂度分析**:理解时间复杂度和空间...

    hdu3398.zip_visual c

    然后,可以使用模拟输入的方式测试代码,或者直接在HDU Online Judge上提交编译后的程序进行在线验证。 7. **调试技巧**:在遇到问题时,利用Visual C++的调试器可以帮助找出代码中的错误,通过设置断点、查看变量...

Global site tag (gtag.js) - Google Analytics