【2022寒假精进训练-3】7-3 出租
一时间网上一片求救声,急问这个怎么破。其实这段代码很简单,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数组逆 ...
【2022寒假精进训练-3】7-10 是否完全二叉搜索树
将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果。
输入格式:输入第一行给出一个不超过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]的数据是 ...
【2022寒假精进训练-3】7-1 吃鱼还是吃肉
国家给出了 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 ...
【2022寒假精进训练-3】7-6 朋友圈的数量
学校有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 ...
【2022寒假精进训练-3】7-7 部落
在一个社区里,每个人都有自己的小圈子,还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里,于是要请你统计一下,在一个给定社区中,到底有多少个互不相交的部落?并且检查任意两个人是否属于同一个部落。
输入格式:输入在第一行给出一个正整数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
思路这道题考察了并查集。并查集的模板主要包括四个部分:初始化,寻找根节点,合并,求连通分量个数。(给大家强烈推荐一篇文章 ...
【2022寒假精进训练-3】7-5 人以群分
社交网络中我们给每个人定义了一个“活跃度”,现希望根据这个指标把人群分为两大类,即外向型(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 ...
【2022寒假精进训练-3】7-8 公路村村通
现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。
输入格式:输入数据包括城镇数目正整数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 ...
【2022寒假精进训练-3】7-9 完全二叉树的层序遍历
一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是完美二叉树。对于深度为 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 & ...
【2022每日分享day08】《正则表达式必知必会》
河北大学2022寒假萌新程序设计训练每日知识分享-day08
每日分享——《正则表达式必知必会》正则表达式是一种威力无比强大的武器,几乎在所有的程序设计语言里和计算机平台上都可以用它来完成各种复杂的文本处理工作。本书从简单的文本匹配开始,循序渐进地介绍了很多复杂内容,其中包括回溯引用、条件性求值和前后查找,等等。每章都为读者准备了许多简明又实用的示例,有助于全面、系统、快速掌握正则表达式,并运用它们去解决实际问题。
【2022每日分享day07】《代码整洁之道》
河北大学2022寒假萌新程序设计训练每日知识分享-day07
每日分享——《代码整洁之道》《代码整洁之道》讲述了一系列行之有效的整洁代码操作实践。软件质量,不但依赖于架构及项目管理,而且与代码质量紧密相关。这一点,无论是敏捷开发流派还是传统开发流派,都不得不承认。《代码整洁之道》提出一种观念:代码质量与其整洁度成正比。干净的代码,既在质量上较为可靠,也为后期维护、升级奠定了良好基础。作为编程领域的佼佼者,这些实践在《代码整洁之道》中体现为一条条规则(或称“启示”),并辅以来自现实项目的正、反两面的范例。只要遵循这些规则,就能编写出干净的代码,从而有效提升代码质量。