【2022寒假精进训练-6】7-10 树的遍历
给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式:输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式:在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。。
输入样例:12372 3 1 5 7 6 41 2 3 4 5 6 7
输出样例:14 1 6 3 5 7 2
思路题目要求输出层序遍历,可以借助完全二叉树的思想: 某节点的左右节点索引关系分别为2 * n ,2 * n + 1。递归每次划分以左右子树,每次将当前根节点存入指定p位置,存入ans结果数组,最后直接输出即可。
代码1234567891011121314151617181920212223242526272829303132333435363738#include <iostream>#include <cstring>using namespace std;const int N = 10000;int n;int a ...
【2022每日分享day18】编辑器推荐-VS Code
河北大学2022寒假萌新程序设计训练每日知识分享-day18
每日分享——编辑器推荐-VS Code首先讲一下编译器和编辑器的区别。
编辑器也就是文本编辑器,是编辑源文件的程序(比如记事本,vscode,subline),编译器就是将源文件变成二进制可执行文件的程序。我们常用的CodeBlocks(可能是我们用的第一个写程序的东西),Dev-C++,VS等,其实是IDE(Integrated Development Environment,集成开发环境),包含了编辑和编译的功能。
VS Code是一个非常好用的编辑器。有三点好用的地方(我个人觉得):第一,好看(笑,颜值是第一生产力);第二,支持很多语言,比如c/c++,python,java,Verilog,html等等;第三,有很多扩展程序,也就是插件,各种各样的插件,可以说是编辑器里面的Chrome。
当然vscode只是一个编辑器。如果要使用他,还需要安装相应的编译器。之后就可以使用vscode,vscode里面内置终端,写完之后可以自己在命令行里编译运行,如果嫌麻烦可以下载一个CodeRunner的插件,一键运行,十分方便。
【2022每日分享day17】sizeof-strlen-size-length理解
河北大学2022寒假萌新程序设计训练每日知识分享-day17
每日分享——sizeof-strlen-size-length理解运算符:sizeof函数:strlen()、size()、length()
sizeof计算变量、常量名或是数据类型名占用的空间字节数;strlen传入C语言字符串(字符数组名或字符指针,以\0结尾),返回从传入的第一个字符到\0的长度;size和length都是string类的成员函数,两函数完全相同,返回C++字符串的长度。起初string是没有size函数的,后来C++引入STL后为保持各容器统一才加入的
其实归根结底还是区分开char*和string,搞清楚指针。推荐一本对于理解指针很有帮助的书——《深入理解C指针》,指针学着并不难,难的是学会了依旧看不懂别人指针的玩法。
【2022寒假精进训练-5】7-9 月饼
月饼是中国人在中秋佳节时吃的一种传统食品,不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量,请你计算可以获得的最大收益是多少。
注意:销售时允许取出一部分库存。样例给出的情形是这样的:假如我们有 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
思 ...
【2022寒假精进训练-5】7-13 社交集群
当你在社交网络平台注册时,一般总是被要求填写你的个人兴趣爱好,以便找到具有相同兴趣爱好的潜在的朋友。一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。
输入格式:输入在第一行给出一个正整数 N(≤1000),为社交网络平台注册的所有用户的人数。于是这些人从 1 到 N 编号。随后 N 行,每行按以下格式给出一个人的兴趣爱好列表:
Ki: hi[1] hi[2] …hi[Ki]
其中Ki(>0)是兴趣爱好的个数hi[j]是第j个兴趣爱好的编号,为区间 [1, 1000] 内的整数。
输出格式:首先在一行中输出不同的社交集群的个数。随后第二行按非增序输出每个集群中的人数。数字间以一个空格分隔,行末不得有多余空格。
输入样例:12345678983: 2 7 101: 42: 5 31: 41: 31: 44: 6 8 1 51: 4
输出样例:1234 3 1
思路这道题是一个并查集的模板题,每次读入一个人兴趣爱好时,根据他的兴趣爱好和前一个有共同兴趣爱好的人进行合并,最后判断一共有多少个集合再输出即可。
代码12345678910111213141516 ...
【2022寒假精进训练-5】7-10 列车调度
两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在入口处按照{8,4,2,5,3,9,1,6,7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?
输入格式:输入第一行给出一个整数N (2 ≤ N ≤105),下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。
输出格式:在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
输入样例:1298 4 2 5 3 9 1 6 7
输出样例:14
思路采用单调队列来解决这个问题,题目问按照输出递减的顺序最少需要几个铁轨,每辆火车,有两种情况:1.如果在现存的铁轨中,存在一个编号大于它的火车,则把这辆火车放入这条铁轨,然后更新这条铁轨最小的火车编码,2.如果找不到,则再开一条新的铁轨,最后输出铁轨数量。很明显,非常适合单调队列或者单调栈来实现。在找铁轨时,可以采用二分,因为存在单调性!
代码12345678910111213141516171 ...
【2022寒假精进训练-5】7-11 小字辈
本题给定一个庞大家族的家谱,要请你给出最小一辈的名单。
输入格式:输入在第一行给出家族人口总数 N(不超过 100 000 的正整数) —— 简单起见,我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号,其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。
输出格式:首先输出最小的辈分(老祖宗的辈分为 1,以下逐级递增)。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔,行首尾不得有多余空格。
输入样例:1292 6 5 5 -1 5 6 4 7
输出样例:1241 9
思路暴力,判断方案可不可行,暴力遍历每条边看左右两点颜色相不相同就行了,有相同的就说明方案不可行。点数最大v=500,边数最大v*(v-1)/2,设置存边数组g[N]应足够大。
这个题最坑的地方是方案必须为k种颜色。
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include<io ...
【2022寒假精进训练-5】7-12 红色警报
战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序,当失去一个城市导致国家被分裂为多个无法连通的区域时,就发出红色警报。注意:若该国本来就不完全连通,是分裂的k个区域,而失去一个城市并不改变其他城市之间的连通性,则不要发出警报。
输入格式:输入在第一行给出两个整数N(0 < N ≤ 500)和M(≤ 5000),分别为城市个数(于是默认城市从0到N-1编号)和连接两城市的通路条数。随后M行,每行给出一条通路所连接的两个城市的编号,其间以1个空格分隔。在城市信息之后给出被攻占的信息,即一个正整数K和随后的K个被攻占的城市的编号。
注意:输入保证给出的被攻占的城市编号都是合法的且无重复,但并不保证给出的通路没有重复。
输出格式:对每个被攻占的城市,如果它会改变整个国家的连通性,则输出Red Alert: City k is lost!,其中k是该城市的编号;否则只输出City k is lost.即可。如果该国失去了最后一个城市,则增加一行输出Game Over.。
输入样例:12345675 40 11 33 00 451 2 0 4 3
输出样例:123456Ci ...
【2022每日分享day16】经典例题:接雨水
河北大学2022寒假萌新程序设计训练每日知识分享-day16
每日分享—— 经典例题:接雨水
【2022每日分享day15】Codeforces
河北大学2022寒假萌新程序设计训练每日知识分享-day15
每日分享—— CodeforcesCodeforces https://codeforces.com/Codeforces是一个提供在线评测系统的俄罗斯网站,由一群来自俄罗斯萨拉托夫国立大学的程序员创建并维护。它最初是为那些对于解决问题和参加竞赛感兴趣的学生而设立。第一届Codeforces比赛于2010年2月19日有175名选手参加,到了2019年7月一共举办了超过650场,平均每一场有超过9000名参赛者。
很多大学都推荐计算机学生使用Codeforces来辅助学习。CMU的计算机教授Daniel Sleator认为在计算机学习时编程竞赛是必要的,因为在参赛的同时学生能够学到如何将传统的算法进行调整来适应实际问题,这样下来学生能够加深对于算法概念的理解。他就在他自己的课堂上便采用Codeforces的题目来作为范例指导学生。
比赛简介Codeforces平台有以下两种比赛活动:
Codeforces Rounds(短程比赛) 大约一周一次,时长2小时
Educational Contests(教育性比赛) ...