HBUACM

对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。 现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。 输入格式:输入的第一行包含一个正整数N（≤1000），第二行包含N个整数，为给出的整数键值序列，数字间以空格分隔。 输出格式:输出的第一行首先给出判断结果，如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，则输出YES，否侧输出NO。如果判断结果是YES，下一行输出对应二叉树的后序遍历序列。数字间以空格分隔，但行尾不能有多余的空格。 输入样例1:1278 6 5 7 10 8 11 输出样例1:12YES5 7 6 8 11 10 8 输入样例2:1278 6 8 5 10 9 11 输出样例2:1NO 思路：首先要明确 二叉搜索树 由于其本身得性质已知先序是可以写出后序遍历的 然后 假设是二叉搜索树，得到后序遍历 若长度为n，则成立，否则再判断镜面 ...

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。 输入格式：输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。 输出格式：在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。 输入样例：12371 2 3 4 5 6 74 1 3 2 6 5 7 输出样例：14 6 1 7 5 3 2 思路：中序前序得到树，再在层序遍历时”先入右后入左“达到镜面反转的结果。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include<iostream>#include<queue>using namespace std;typedef struct Node *Tree ...

河北大学程序设计训练营每日分享-day07 理论学科 今天已经是每日分享的第七篇，继续给大家分享左耳听风专栏的程序员练级攻略内容 这次给大家推荐的章节是 74 | 程序员练级攻略：理论学科 其实已经推荐了很多内容了，除看书看视频，也不要忘了多敲 多练习。 74 | 程序员练级攻略：理论学科 这篇文章中， 建议想进入专业编程领域的人，一定要学习算法、数据结构、网络模型、计算机原理等理论知识，并推荐了相应的学习素材，给出了作者的思考和建议。 解决算法问题的确是可以区分人类智商的一个比较好的方式，**这也是为什么好些公司用算法题当面试题来找到智商比较高的程序员。** 业务上我需要用算法比较两个数组中差异的布隆过滤器， 或是在做监控系统时实时计算过去一分钟的 P99 统计时的蓄水池算法， 或是数据库的 B+ 树索引， 还有 Linux 内核中的 epoll 的红黑树， 还有在做服务调度里的“背包问题”等都会用算法， 真的是会本质上帮助到你，也是会让你瞬间会产生成就感的事情。 这些理论知识可以说是计算机科学这门学科最精华的知识了，认真学习，理解其背后的逻辑和思维方式，会让你受益匪浅。不管是 ...

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式：输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。 输出格式：在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。 输入样例：12372 3 1 5 7 6 41 2 3 4 5 6 7 输出样例：14 1 6 3 5 7 2 思路：后中序得到二叉树，再利用队列进行层序遍历。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include<iostream>#include<queue>using namespace std;typedef struct Node{ int data; struct Node * lchild; struct Node * r ...

河北大学程序设计训练营每日分享-day06 左耳听风 专栏推荐Day06左耳听风专栏编程语言的选择 今天开始放慢一下分享的脚步 毕竟整个专栏是老牌程序员半辈子知识储备和经验的呈现，哪能轻松且短期都吸收呢！ 今天就只分享这一篇文章 关于语言的选择 73 | 程序员练级攻略：编程语言 陈皓 2018-06-12 一个合格的程序员应该掌握几门语言。一方面，这会让你对不同的语言进行比较，让你有更多的思考。另一方面，这也是一种学习能力的培养，会让你对于未来的新技术学习得更快。 一个合格的程序员应该掌握几门语言。 一方面，这会让你对不同的语言进行比较，让你有更多的思考。 另一方面，这也是一种学习能力的培养，会*让你对于未来的新技术学习得更快。 在编程语言方面，作者推荐学习 C、C++、Java 和 Go 四门语言，并分别阐释了推荐的原因。 摘录作者关于理论知识的理解 理论学科。 你需要学习像算法、数据结构、网络模型、计算机原理等计算机科学专业需要学习的知识。 为什么要学好这些理论上的知识呢？ 其一，这些理论知识可以说是计算机科学这门学科最精华的知识了。说得大一点，这些是人类智慧的精华。你只要想成 ...

河北大学程序设计训练营每日分享-day05 左耳听风 专栏推荐 之前的几次分享都是在围绕 数据结构与算法 这一单一模块进行分享，基础知识很重要，万丈高楼平地起，勿在浮沙筑高台。除了算法这一个模块，我们还有很多的知识也需要掌握。 大家大一学习的第一门课程便是 《计算机导论》，从计算思维的角度介绍计算机体系结构、软件硬件系统、问题求解、计算机网络、信息安全、数据库技术、办公软件的高级应用等内容。 或许大家学完了学术化的导论课程，仍然对自己的未来发展方向存在一些迷茫。 我今天给大家推荐一个 关于程序员发展的专栏 《左耳听风》，作者陈皓是一位有20年软件开发工作经验的资深程序员，专栏中的每篇文章都是陈皓多年“堵过的枪眼儿”“填过的坑儿”的深入思考和凝练，是一些与个人或企业切身利益相关的内容，或者说是更具指导性、更为商业化的内容。用他自己的话说，是一些非常来之不易的宝贵经验。 极客时间 左耳听风、 推荐内容每个用户可以任选6讲全文学习。 整个专栏共105讲，我着重选取了 程序员练级攻略 的 6讲 进行推荐 71 | 程序员练级攻略：正式入门 73 | 程序员练级攻略：编程语言 74 | 程序 ...

河北大学程序设计训练营每日分享-day04 算法慕课分享 之前已经分享过一些书籍和博客帮助大家学习数据结构与算法 但是从我个人的学习经历中，我觉得看书和看博客还是蛮枯燥的，互联网上已经有很多免费的教学视频可以帮助大家入门和学习，所以我今天打算推荐几个个人觉得还算不错的网课分享出来。 免费慕课推荐两门适合绝大部分同学的网课 浙大陈越姥姥的数据结构，课程在中国大学mooc上。 中国大学MOOC 数据结构 陈越 何钦铭 国家精品 推荐这门课程的主要原因是 每一个知识点的讲解都控制在几分钟之内，非常适合碎片化时间学习系统化知识。 其次这门课程和 咱们学院的数据结构课程的授课顺序和学习进度是一样的，学习陈越姥姥的这么慕课，既可以用来提升自己的编程水平 又可以填补自己在学校学习数据结构时遗漏的知识，并且学完这么课程无论是 PAT 甲级 还是天梯赛，绝大部分题目都不在话下。 坚持完成本课程学习、并按照要求完成所有练习的学员，应该具备了PAT（Programming Ability Test）甲级需要的所有基础知识，辅以充分的英语阅读能力和熟练的编程能力，应可以取得优良成绩。 清华邓俊 ...

天梯图书阅览室请你编写一个简单的图书借阅统计程序。当读者借书时，管理员输入书号并按下S键，程序开始计时；当读者还书时，管理员输入书号并按下E键，程序结束计时。书号为不超过1000的正整数。当管理员将0作为书号输入时，表示一天工作结束，你的程序应输出当天的读者借书次数和平均阅读时间。 注意：由于线路偶尔会有故障，可能出现不完整的纪录，即只有S没有E，或者只有E没有S的纪录，系统应能自动忽略这种无效纪录。另外，题目保证书号是书的唯一标识，同一本书在任何时间区间内只可能被一位读者借阅。 输入格式：输入在第一行给出一个正整数N（≤10），随后给出N天的纪录。每天的纪录由若干次借阅操作组成，每次操作占一行，格式为： 书号（[1, 1000]内的整数） 键值（S或E） 发生时间（hh:mm，其中hh是[0,23]内的整数，mm是[0, 59]内整数） 每一天的纪录保证按时间递增的顺序给出。 输出格式：对每天的纪录，在一行中输出当天的读者借书次数和平均阅读时间（以分钟为单位的精确到个位的整数时间）。 输入样例：12345678910111231 S 08:102 S 08:351 E 10:002 ...

图着色问题是一个著名的NP完全问题。给定无向图G=(V,E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？ 但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。 输入格式：输入在第一行给出3个整数V（0<V≤500）、E（≥0）和K（0<K≤V），分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1到V编号。随后E行，每行给出一条边的两个端点的编号。在图的信息给出之后，给出了一个正整数N（≤20），是待检查的颜色分配方案的个数。随后N行，每行顺次给出V个顶点的颜色（第i个数字表示第i个顶点的颜色），数字间以空格分隔。题目保证给定的无向图是合法的（即不存在自回路和重边）。 输出格式：对每种颜色分配方案，如果是图着色问题的一个解则输出Yes，否则输出No，每句占一行。 输入样例：12345678910111213146 8 32 11 34 62 52 45 45 63 641 2 3 3 1 24 5 6 6 4 51 2 3 4 5 62 3 4 2 3 4 输出样例：1234Yes ...

月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。 注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼，获得 72 + 45/2 = 94.5（亿元）。 输入格式：每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500（以万吨为单位）的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出 N 个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。 输出格式：对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后 2 位。 输入样例：1233 2018 15 1075 72 45 输出样例：194.50 代 ...