HBUACM

本题的要求很简单，就是求N个数字的和。麻烦的是，这些数字是以有理数分子/分母的形式给出的，你输出的和也必须是有理数的形式。 输入格式：输入第一行给出一个正整数N（≤100）。随后一行按格式a1/b1 a2/b2 ...给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外，负数的符号一定出现在分子前面。 输出格式：输出上述数字和的最简形式 —— 即将结果写成整数部分 分数部分，其中分数部分写成分子/分母，要求分子小于分母，且它们没有公因子。如果结果的整数部分为0，则只输出分数部分。 输入样例1：1252/5 4/15 1/30 -2/60 8/3 输出样例1：13 1/3 输入样例2：1224/3 2/3 输出样例2：12 输入样例3：1231/3 -1/6 1/8 输出样例3：17/24 思路先根据分数加法的公式进行累加$\frac{A}{B}+\frac{a}{b} = \frac{Ab+aB}{Bb}$，最后分离出整数部分和分数部分输出即可。 ...

一时间网上一片求救声，急问这个怎么破。其实这段代码很简单，index数组就是arr数组的下标，index[0]=2 对应 arr[2]=1，index[1]=0 对应 arr[0]=8，index[2]=3 对应 arr[3]=0，以此类推…… 很容易得到电话号码是18013820100。 本题要求你编写一个程序，为任何一个电话号码生成这段代码 —— 事实上，只要生成最前面两行就可以了，后面内容是不变的。 输入格式：输入在一行中给出一个由11位数字组成的手机号码。 输出格式：为输入的号码生成代码的前两行，其中arr中的数字必须按递减顺序给出。 输入样例：118013820100 输出样例：12int[] arr = new int[]{8,3,2,1,0};int[] index = new int[]{3,0,4,3,1,0,2,4,3,4,4}; 思路arr是电话号码中出现过数字的从大到小的排列；index是电话号码中每位数字在arr中的元素下标。 用vis[10]数组记录数字是否在电话号码中出现过；然后对vis数组逆 ...

以上是新浪微博中一奇葩贴：“我出生于1988年，直到25岁才遇到4个数字都不相同的年份。”也就是说，直到2013年才达到“4个数字都不相同”的要求。本题请你根据要求，自动填充“我出生于y年，直到x岁才遇到n个数字都不相同的年份”这句话。 输入格式：输入在一行中给出出生年份y和目标年份中不同数字的个数n，其中y在[1, 3000]之间，n可以是2、或3、或4。注意不足4位的年份要在前面补零，例如公元1年被认为是0001年，有2个不同的数字0和1。 输出格式：根据输入，输出x和能达到要求的年份。数字间以1个空格分隔，行首尾不得有多余空格。年份要按4位输出。注意：所谓“n个数字都不相同”是指不同的数字正好是n个。如“2013”被视为满足“4位数字都不同”的条件，但不被视为满足2位或3位数字不同的条件。 输入样例1：11988 4 输出样例1：125 2013 输入样例2：11 2 输出样例2：10 0001 思路判断年份y中是否有n个不同的数字，需要是不同的数字，所以使用set容器，将年份y中的每位数字放入set容器中，然后比较set容器大小与n是否相同。需要注意的是年份y如果是小于 ...

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。 输入格式：输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。 输出格式：将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出YES，如果该树是完全二叉树；否则输出NO。 输入样例1：12938 45 42 24 58 30 67 12 51 输出样例1：1238 45 24 58 42 30 12 67 51YES 输入样例2：12838 24 12 45 58 67 42 51 输出样例2：1238 45 24 58 42 12 67 51NO 思路跟上一题7-9 完全二叉树的层序遍历 (25 分)的思路十分类似，先得到层序遍历中每一个节点的左右子节点坐标，再将给出的N个正整数插入二叉搜索树中。 结构体数组node存放每个节点的左右孩子在层序遍历中的坐标和该节点的数据，首先判断node[0]的数据是 ...

国家给出了 8 岁男宝宝的标准身高为 130 厘米、标准体重为 27 公斤；8 岁女宝宝的标准身高为 129 厘米、标准体重为 25 公斤。 现在你要根据小宝宝的身高体重，给出补充营养的建议。 输入格式：输入在第一行给出一个不超过 10 的正整数 N，随后 N 行，每行给出一位宝宝的身体数据： 1性别 身高 体重 其中性别是 1 表示男生，0 表示女生。身高和体重都是不超过 200 的正整数。 输出格式：对于每一位宝宝，在一行中给出你的建议： 如果太矮了，输出：duo chi yu!（多吃鱼）； 如果太瘦了，输出：duo chi rou!（多吃肉）； 如果正标准，输出：wan mei!（完美）； 如果太高了，输出：ni li hai!（你厉害）； 如果太胖了，输出：shao chi rou!（少吃肉）。 先评价身高，再评价体重。两句话之间要有 1 个空格。 输入样例：1234540 130 231 129 271 130 300 128 27 输出样例：1234ni li hai! duo chi rou!duo chi yu! wan mei!wan mei! shao ch ...

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。 输入格式:输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。 输出格式:输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。 输入样例:123456789101112131415166 151 2 51 3 31 4 71 5 41 6 22 3 42 4 62 5 22 6 63 4 63 5 13 6 14 5 104 6 85 6 3 输出样例:112 思路可以使用并查集来做，使用结构体数组node a来存储两个村子及其公路的成本，按照成本从低到高排序， ans记录成本，初始化为0；cnt记录可以连接的村庄数量，初始化为1； 便利数组a，判断两个村庄是否已经连通，即判断二者跟节点是否相同；如果相同，说明两个村庄已连通，该条公路不需要修建；如果不同，合并这两个村庄，an ...

在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。 输入格式：输入在第一行给出一个正整数N（≤104），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人： K P[1] P[2] ⋯ P[K] 其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过104。 之后一行给出一个非负整数Q（≤104），是查询次数。随后Q行，每行给出一对被查询的人的编号。 输出格式：首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。 输入样例：1234567843 10 1 22 3 44 1 5 7 83 9 6 4210 53 7 输出样例：12310 2YN 思路这道题考察了并查集。并查集的模板主要包括四个部分：初始化，寻找根节点，合并，求连通分量个数。（给大家强烈推荐一篇文章 ...

学校有N个学生，许多同学在学习中与生活中成为了朋友，据说朋友关系有自反性（自己和自己是朋友），有对称性（你和我是朋友，我和你一定也是朋友），还有传递性，即如果A和B是朋友，且B和C是朋友，则A和C也是朋友，于是就形成了许多的朋友圈。下列矩阵表示的四个人的朋友圈：i行 j列为1表示是直接的朋友关系，为0表示并非直接的朋友关系，是否是间接的朋友不清楚。输入样例中，0,1,2是一个朋友圈，3号自己是一个朋友圈。故共有2个朋友圈。请编写程序，根据给定的关系矩阵，计算学校的朋友圈数量。 注意：因为关系矩阵是对称的，故只录入了下三角的数据，也就是只描述了i号学生与其前边的学生的朋友关系，后边的关系未再复述（包括对角线上的自己：N个学生，仅输入了N*(N+1)/2个数据）。 输入样例：12345411 11 0 10 0 0 1 输出样例：输出全校学生中的朋友圈的数量（指没有交集的朋友圈）： 12 思路这道题考察了并查集。并查集的模板主要包括四个部分：初始化，寻找根节点，合并，求连通分量个数。（给大家强烈推荐一篇文章，解释并查集非常形象易懂和有趣，链接） 1. 初始化 12345void ini ...

社交网络中我们给每个人定义了一个“活跃度”，现希望根据这个指标把人群分为两大类，即外向型（outgoing，即活跃度高的）和内向型（introverted，即活跃度低的）。要求两类人群的规模尽可能接近，而他们的总活跃度差距尽可能拉开。 输入格式：输入第一行给出一个正整数N（2≤N≤105）。随后一行给出N个正整数，分别是每个人的活跃度，其间以空格分隔。题目保证这些数字以及它们的和都不会超过231。 输出格式：按下列格式输出： 123Outgoing #: N1Introverted #: N2Diff = N3 其中N1是外向型人的个数；N2是内向型人的个数；N3是两群人总活跃度之差的绝对值。 输入样例1：121023 8 10 99 46 2333 46 1 666 555 输出样例1：123Outgoing #: 5Introverted #: 5Diff = 3611 输入样例2：1213110 79 218 69 3721 100 29 135 2 6 13 5188 85 输出样例2：123Outgoing #: 7Introverted #: 6 ...

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是完美二叉树。对于深度为 D 的，有 N 个结点的二叉树，若其结点对应于相同深度完美二叉树的层序遍历的前 N 个结点，这样的树就是完全二叉树。 给定一棵完全二叉树的后序遍历，请你给出这棵树的层序遍历结果。 输入格式：输入在第一行中给出正整数 N（≤30），即树中结点个数。第二行给出后序遍历序列，为 N 个不超过 100 的正整数。同一行中所有数字都以空格分隔。 输出格式：在一行中输出该树的层序遍历序列。所有数字都以 1 个空格分隔，行首尾不得有多余空格。 输入样例：12891 71 2 34 10 15 55 18 输出样例：118 34 55 71 2 10 15 91 思路常规做法是通过后序遍历还原二叉树，再进行层序遍历输出，但十分复杂，这道题可以采用逆向思维，因为完全二叉树层序遍历的某一节点的左右子结点坐标是确定的，分别是i*2和i*2+1，再通过在后序遍历左右根的根时，输入该节点数据，进而可以得到完整的层序遍历结果。 代码1234567891011121314151617181920212223#include & ...