day31 还原二叉树
河北大学程序设计训练营
题目要求：给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。
输入格式:输入首先给出正整数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 ...
day34 五服
呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？
输入格式：
输入第一行给出一个正整数N（2 ≤ N ≤104 ），随后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 ...
day33 搜索树判断
河北大学程序设计训练营
对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。
现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。
输入格式:输入的第一行包含一个正整数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 ...
day27 奥马尔·爱糖果
河北大学程序设计训练营
奥马尔喜欢吃很多糖果，但不幸的是，大部分的糖果都不健康。所以他的父母找到了一种方法，给每个糖果打分，分数越高，糖果就越健康(分数是一个整数，可以是正的、零的或负的)。一个孩子和他的父母买了一些糖果，他们到了卖糖果的地方，所有的糖果都被存储在一个N*M的二维网格中，每一行有M个糖果。行从上到下从1到N编号，列从左到右从1到M编号，每个单元格包含一个糖果健康值。奇怪的是，这个二维网格中的糖果的健康值总是从上到下、从左到右依次增大，如下图
奥马尔想买完一个子矩阵中的所有糖果，请你编程序求出他所能买得的最大的糖果健康值。
输入格式:输入的第一行是单个整数T，测试用例的数量(1≤T≤100)。每个测试用例开始一行包含空格隔开两个整数N M (1≤N,M≤1000)代表糖果网格的尺寸，紧随其后的是N行，每一个包含M个空格隔开整数，代表这一行糖果的健康值。网格中的每个整数将不小于- 2000，也不大于2000。
输出格式:对于每个测试用例，打印包含单个整数的一行，该整数表示从非空子矩形中可以获得的健康值的最大总和。
输入样例:在这里给出一组输入。例如：
13 3-4 - ...
day25 矩阵链相乘问题
河北大学程序设计训练营
题目描述：矩阵的乘法定义如下：设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 ...
day24 兔子跳楼梯
河北大学程序设计训练营[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 ...
day23 0-1背包
河北大学程序设计训练营[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}, \ ...
day22 最长公共子序列长度
河北大学程序设计训练营[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… ...
day21 最长对称子串
河北大学程序设计训练营[TOC]
day21 最长对称子串对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。
输入格式:输入在一行中给出长度不超过1000的非空字符串。
输出格式:在一行中输出最长对称子串的长度。
输入样例:1Is PAT&TAP symmetric?
输出样例:111
代码：
123456789101112131415161718192021222324#include<bits/stdc++.h>using namespace std;int main(){ string str; getline(cin,str); int maxLen=0; for(int i=0; i<str.size(); i++)//遍历每一点，以每一点为中心，向左右查看是否相等 { int j=1; while(i-j>=0&&i+j ...
day20 单链表的创建及遍历
单链表的创建及遍历读入n值及n个整数，建立单链表并遍历输出。
输入格式:读入n及n个整数。
输出格式:输出n个整数，以空格分隔（最后一个数的后面没有空格）。
输入样例:在这里给出一组输入。例如：
210 5
输出样例:在这里给出相应的输出。例如：
10 5
注意:
整个题没难度，最基本的单链表建立。注意申请内存空间的malloc函数的使用struct NList* newNode = (struct NList*)malloc(sizeof( struct NList ));
代码123456789101112131415161718192021222324252627282930313233343536373839404142#include <iostream>#include <malloc.h>using namespace std;struct NList{ int num;//数据域 struct NList* Next;//指针域};int main(){ int n , x; cin >> n; ...
