HBUACM

天梯赛经验分享-曹晨 author: 曹晨 date: 2020-11-21 20:44:40 无序列表（加号和嵌套）Unordered Lists (+) String类型操作 insert erase() substr() compare() find() replace() 基本算法 dfs和bfs 并查集 单/多源最短路问题 最小生成树 二叉树的遍历 拓扑图 优先队列 最近公共祖先 01背包 kmp思维能力和编写代码能力 思维能力主要考察对算法的理解，但是实际代码比较的短小。比如01背包，并查集，优先队列等，这一部分主要需要大家对算法有比较深入的理解，比如01背包等需要你搞懂内部的原理 代码的编写能力则需要大量的训练，思维可能比较的简单但是代码量比较的多，应该从平时尽量的养成规范的编写代码习惯，背会各种代码模板：DFS。琐碎的知识点 char *,string,const char *之间的转化 字符串和数字之间的转化 stringstream的使用 getline(cin,x) getchar()等等对缓冲区最后一个回车的影响 分割字符串strtok函数 C++ ...

markdown 文章内容作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。 输入格式: 输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。 输出格式: 第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。 输入样例: 4 5 0 320 30 40 100 1 11 3 20 3 30 2 ...

河北大学程序设计训练营 题目要求：给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。 输入格式:输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。 输出格式:输出为一个整数，即该二叉树的高度。 输入样例: 9ABDFGHIECFDHGIBEAC 输出样例: 5 先看怎么恢复二叉树：先序遍历第一个字母即为树的根，其他字母可视为子树的根。中序遍历中字母的位置为相对位置，比如，BAC ，就是 恢复就是在先序遍历中找子树的根，然后在中序遍历里判断它的左右子树，以题目为例，这样就恢复完了。 再来看怎么求二叉树高度：迭代分别求左右子树的高度，较高的就为树的高度。 代码： 1234567891011121314151617181920212223242526272829303132#include<bits/stdc++.h>using namespace std;string str1,str2;int Height(int t1,int t2,int lenth,int ...

呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？ 输入格式： 输入第一行给出一个正整数N（2 ≤ N ≤10​4​​ ），随后N行，每行按以下格式给出一个人的信息：本人ID 性别 父亲ID 母亲ID其中ID是5位数字，每人不同；性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考，则相应的ID位置上标记为-1。接下来给出一个正整数K，随后K行，每行给出一对有情人的ID，其间以空格分隔。 注意：题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。 输出格式：对每一对有情人，判断他们的关系是否可以通婚：如果两人是同性，输出Never Mind；如果是异性并且关系出了五服，输出Yes；如果异性关系未出五服，输出No。 输入样例： 2400001 M 01111 -100002 F 02222 0333300003 M 02222 0333300004 F 04444 0333300005 M 04444 05555 ...

河北大学程序设计训练营 对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。 现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。 输入格式:输入的第一行包含一个正整数N（≤1000），第二行包含N个整数，为给出的整数键值序列，数字间以空格分隔。 输出格式:输出的第一行首先给出判断结果，如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，则输出YES，否侧输出NO。如果判断结果是YES，下一行输出对应二叉树的后序遍历序列。数字间以空格分隔，但行尾不能有多余的空格。 输入样例1: 78 6 5 7 10 8 11 输出样例1: YES5 7 6 8 11 10 8 输入样例2: 78 6 8 5 10 9 11 输出样例2: NO 1234567891011121314151617181920212223242526272829303132333435363 ...

河北大学程序设计训练营 奥马尔喜欢吃很多糖果，但不幸的是，大部分的糖果都不健康。所以他的父母找到了一种方法，给每个糖果打分，分数越高，糖果就越健康(分数是一个整数，可以是正的、零的或负的)。一个孩子和他的父母买了一些糖果，他们到了卖糖果的地方，所有的糖果都被存储在一个N*M的二维网格中，每一行有M个糖果。行从上到下从1到N编号，列从左到右从1到M编号，每个单元格包含一个糖果健康值。奇怪的是，这个二维网格中的糖果的健康值总是从上到下、从左到右依次增大，如下图 奥马尔想买完一个子矩阵中的所有糖果，请你编程序求出他所能买得的最大的糖果健康值。 输入格式:输入的第一行是单个整数T，测试用例的数量(1≤T≤100)。每个测试用例开始一行包含空格隔开两个整数N M (1≤N,M≤1000)代表糖果网格的尺寸，紧随其后的是N行，每一个包含M个空格隔开整数，代表这一行糖果的健康值。网格中的每个整数将不小于- 2000，也不大于2000。 输出格式:对于每个测试用例，打印包含单个整数的一行，该整数表示从非空子矩形中可以获得的健康值的最大总和。 输入样例:在这里给出一组输入。例如： 13 3-4 - ...

河北大学程序设计训练营 题目描述：矩阵的乘法定义如下：设A是m×p的矩阵，B是p×n的矩阵，则A与B的乘积为m×n的矩阵，记作C=AB，其中，矩阵C中的第i行第j列元素cij 可以表示为：当多个矩阵相乘时，采用不同的计算顺序所需的乘法次数不相同。例如，A是50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵， 计算ABC有两种方式：(AB)C和A(BC)，前一种需要15000次乘法计算，后一种则只需3500次。 设A1 ,A2 ,…,An 为矩阵序列，Ai 是阶为Pi−1 ∗Pi 的矩阵(1≤i≤n)。试确定矩阵的乘法顺序，使得计算A1 A2 …An 过程中元素相乘的总次数最少。 输入格式:每个输入文件为一个测试用例，每个测试用例的第一行给出一个正整数(1≤n≤100)，表示一共有n个矩阵A1 ,A2 ,…,An ，第二行给出n+1个整数P0 ,P1 …Pn ，以空格分隔，其中1≤Pi ≤100(0≤i≤n)，第i个矩阵Ai 是阶为Pi−1 ∗Pi 的矩阵。 输出格式:获得上述矩阵的乘积，所需的最少乘法次数。 输入样例:在这里给出一组输入。例如： 530 35 15 5 10 ...

河北大学程序设计训练营[TOC] day24 兔子跳楼梯小兔子喜欢蹦蹦跳跳上楼梯 ，它能一次跳1阶楼梯，也能一次跳上2阶楼梯。问小兔子要上一个n阶的楼梯，最多有多少种不同上楼的走法？ 输入格式:输入一行包含一个整数 n，表示有几阶楼梯。 输出格式:上楼梯的走法数。 输入样例1: 3 输出样例1: 3 分析：评测用例规模与约定对于 20%的评测用例，1≤n≤10。 对于 50%的评测用例，1≤n≤100。 对于 80%的评测用例，1≤n≤1000。 对于所有评测用例，1≤n≤10000。 最简单的DP问题。我们知道，在这个上楼梯问题中，一次能上1阶或2阶楼梯。在到达第n(n>1)阶楼梯的时候，可以是从第n-1阶楼梯向上跳1阶楼梯，也可以是从n-2阶楼梯向上跳2阶楼梯。那么可以得出动规方程：a[n]=a[n-1]+a[n-2]。注意，当n<=1的时候要先处理，a[0]=a[1]=1。 123456789101112131415#include<iostream>using namespace std;int main(){int n;int a[100 ...

河北大学程序设计训练营[TOC] day23 0-1背包题目 给定n(n<=100)种物品和一个背包。物品i的重量是wi，价值为vi，背包的容量为C(C<=1000)。问:应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。 输入格式:共有n+1行输入： 第一行为n值和c值，表示n件物品和背包容量c； 接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。 输出格式:输出装入背包中物品的最大总价值。 输入样例:在这里给出一组输入。例如： 1234565 102 62 36 55 44 6 输出样例:在这里给出相应的输出。例如： 115 思路【思考一】朴素解法： 在0-1背包问题中，我不能直接使用贪心算法，但是我们可以引入阶段的概念。设d(i,j)为“把第一个i，i+1,i+2….n个物品装到容量为j的背包中最大总重量”那么我们就很容易地就能写出状态转移方程：$$\mathrm{d} \mathrm{p}(\mathrm{i}, \ ...

河北大学程序设计训练营[TOC] day22 最长公共子序列长度求两个字符串的最长公共子序列长度。 输入格式:输入长度≤100的两个字符串。 输出格式:输出两个字符串的最长公共子序列长度。 输入样例1: ABCBDABBDCABA 输出样例1: 4 输入样例2: ABACDEFPGHIK 输出样例2: 0 分析：最长公共子序列(LCS)只需要保证两个字符串中字符位置一样。 两个字符串:串A和串B。已知两字符串:A0,A1…Ai…An-1 和 B0,B1…Bj…Bm-1。 有以下递推关系:(1)当Ai = Bj时:A0,A1…Ai-1,Ai 和 B0,B1…Bj-1,Bj的LCS长度 等于 A0,A1…Ai-1 和 B0,B1…Bj-1的LCS长度+1。(2)当Ai != Bj时:A0,A1…Ai-1,Ai 和 B0,B1…Bj-1,Bj的LCS长度 等于 max(A0,A1…Ai-1 和 B0,B1…Bj-1,Bj的LCS长度 , A0,A1…Ai-1,Ai 和 B0,B1…Bj-1的LCS长度)。 DP思路：1、数组array[i][j]用来表示 两个字符串A0,A1…Ai… ...