【2022暑期训练-3】7-7 哥尼斯堡的“七桥问题”
哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。
可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(Leonhard Euler，1707—1783)最终解决了这个问题，并由此创立了拓扑学。
这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个无向图，问是否存在欧拉回路？
输入格式:输入第一行给出两个正整数，分别是节点数N (1≤N≤1000)和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。
输出格式:若欧拉回路存在则输出1，否则输出0。
输入样例1:12345678910116 101 22 33 14 55 66 41 41 63 43 6
输出样例1:11
输入样例2:1234567895 81 21 32 32 42 55 35 43 4
输出样例2:10
思路： 判断一个图是否有欧拉回路，其充分必要条件为不存在度为奇数的点。
同时此题还需判断图是否是连通状态的， ...
【2022暑期训练-3】7-3 二叉树的遍历！（简单）
二叉树作为FDS课程最核心的数据结构之一，要求每个人都掌握！
这是一道简单的二叉树问题！
我们将给出一颗二叉树，请你输出它的三种遍历，分别是先序遍历，中序遍历，后序遍历！
输入格式:二叉树将以这样的形式给出：
第一行给出一个正整数N（N<=100)，表示二叉树上的节点个数！
接下来N行，每行包含三个整数，i，l，r，分别代表第i个节点的左右孩子！
如果它的左/右孩子为空，则在对应位置给出-1！
题目保证1是根节点！
输出格式:请你输出它的三种遍历！
第一行输出先序遍历，第二行输出中序遍历，第三行输出后序遍历！
每行末尾无多余空格！
输入样例:在这里给出一组输入。例如：
123431 2 32 -1 -13 -1 -1
输出样例:在这里给出相应的输出。例如：
1231 2 32 1 32 3 1
思路： 基本可以当做二叉树先中后序的板子题
存储方式类似于第一题
代码：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#includ ...
【2022暑期训练-3】7-6 列出连通集
给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
输出格式:按照”{ v1 v2 … v**k }”的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。
输入样例:12345678 60 70 12 04 12 43 5
输出样例:123456{ 0 1 4 2 7 }{ 3 5 }{ 6 }{ 0 1 2 7 4 }{ 3 5 }{ 6 }
思路： 因为N<=10,并且总是从编号最小的顶点出发，按编号递增的顺序访问，所以最好的存储方式就是邻接矩阵。如果邻接表的话，还需要输入完后，对编号进行排序。
代码：12345678910111213141516171 ...
【2022暑期训练-3】7-5 图的存储
输出给定图的邻接矩阵和邻接表。
输入格式:输入第一行给出三个正整数，分别表示无向图的节点数N（1<N≤10）、边数M（≤50）和有向或无向标志S（1表示有向图，0表示无向图）。
随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号。
输出格式:首先输出图的邻接矩阵，即N行N列的元素值，有边其值为1，无边其值为0；以方阵形式输出，每个元素间有一个空格，末尾均有一空格。
然后输出图的邻接表，从第0行开始按顺序输出，共输出N行，具体样式见输出样例。冒号前后无空格，每个元素间有一个空格，末尾均有一空格。
由于图的存储是不唯一的，为了使得输出具有唯一的结果，我们约定以表头插入法构造邻接表。
输入样例:1234567896 8 01 22 33 44 55 66 43 61 5
输出样例:1234567891011120 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0:4 1 1:2 0 2:5 3 1 3:5 4 2 4:0 5 3 5:2 3 4
思路： ...
【2022暑期训练-3】7-8 旅游规划
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
输入格式:输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。
输出格式:在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。
输入样例:1234564 5 0 30 1 1 201 3 2 300 3 4 100 2 2 202 3 1 20
输出样例:13 40
思路： 直接套用Dijkstra就好
代码：123456789101112131415161718192021222324252627282930313233343536373839404 ...
【2022暑期训练-3】7-1 列出叶结点
对于给定的二叉树，本题要求你按从上到下、从左到右的顺序输出其所有叶节点。
输入格式：首先第一行给出一个正整数 N（≤10），为树中结点总数。树中的结点从 0 到 N−1 编号。随后 N 行，每行给出一个对应结点左右孩子的编号。如果某个孩子不存在，则在对应位置给出 “-“。编号间以 1 个空格分隔。
输出格式：在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：12345678981 -- -0 -2 7- -- -5 -4 6
输出样例：14 1 5
思路： 题目是按结点编号给出的左右孩子，所以不采用链式存储。定义一个结构体，存放左右孩子，node[i]代表编号为i的结点，node[i].left和node[i].right分别代表编号i的结点的左右孩子的编号。
然后进行数据读入和存储，然后我们用数组pre记录各个结点的父亲，pre[i]记录的是编号i的父亲编号。
题目说的是按照从上到下，从左到右的顺序输出叶子结点，很明显是层序遍历
代码：123456789101112131415161718192021222 ...
【2022暑期训练-3】7-4 还原二叉树
给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。
输入格式:输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。
输出格式:输出为一个整数，即该二叉树的高度。
输入样例:1239ABDFGHIECFDHGIBEAC
输出样例:15
思路： 这题有点难理解
还原二叉树：已知一颗二叉树:
先序遍历：ABCDEF中序遍历：CBAEDF由于前序遍历第一个打印的是 A 所以 A 为根结点由于中序遍历 CBAEDF 可知 C 和 B 是 A 的左子树的结点，E、D、F 是 A 右子树的结点
由于前序遍历中先 B 后 C ，所以 B 是 A 的左孩子，C 只能是 B 的孩子。中序遍历中先 C 后 B ，所以 C 是 B 的左孩子
前序遍历中顺序为 DEF，意味着 D 是 A 的右孩子E、F 是 D 的子孙，但不一定是左右孩子，可能有一个孙子中序遍历中顺序为 EDF，所以 E 是 D 的左孩子，F 是 D 的右孩子
求树的高度：树的高度其实是用递归来求得，树的高度=max(左子 ...
【2022暑期训练-1】7-10 求两个一元多项式的和
题目：假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。
输入格式:输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾客的到达时间T和事务处理时间P，并且假设输入数据已经按到达时间先后排好了顺序；最后一行给出正整数K（≤10），为开设的营业窗口数。这里假设每位顾客事务被处理的最长时间为60分钟。
输出格式:在第一行中输出平均等待时间（输出到小数点后1位）、最长等待时间、最后完成时间，之间用1个空格分隔，行末不能有多余空格。在第二行中按编号递增顺序输出每个窗口服务了多少名顾客，数字之间用1个空格分隔，行末不能有多余空格。
输入样例:123456789101190 201 151 612 1010 510 330 1831 2531 23
输出样例:126.2 17 615 3 1
思路依题意，我么可以每次处理一个 ...
【2022暑期训练-1】7-9 银行业务队列简单模拟
题目：设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。
输入格式:输入为一行正整数，其中第1个数字N(≤1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。
输出格式:按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。
输入样例:18 2 1 3 9 4 11 13 15
输出样例:11 3 2 9 11 4 13 15
思路本题就单纯模拟两个队列出队就好了，A出两个后B就出一个，注意A出第二个要判队列空不空，直到有一个队列空为止跳出，最后再循环把剩下有人的队列输出完。根据上述模拟，代码如下：
代码1234567891011121314151617181920212223242526272829303132333435363738 ...
【2022暑期训练-1】7-8 彩虹瓶
彩虹瓶的制作过程（并不）是这样的：先把一大批空瓶铺放在装填场地上，然后按照一定的顺序将每种颜色的小球均匀撒到这批瓶子里。
假设彩虹瓶里要按顺序装 N 种颜色的小球（不妨将顺序就编号为 1 到 N）。现在工厂里有每种颜色的小球各一箱，工人需要一箱一箱地将小球从工厂里搬到装填场地。如果搬来的这箱小球正好是可以装填的颜色，就直接拆箱装填；如果不是，就把箱子先码放在一个临时货架上，码放的方法就是一箱一箱堆上去。当一种颜色装填完以后，先看看货架顶端的一箱是不是下一个要装填的颜色，如果是就取下来装填，否则去工厂里再搬一箱过来。
如果工厂里发货的顺序比较好，工人就可以顺利地完成装填。例如要按顺序装填 7 种颜色，工厂按照 7、6、1、3、2、5、4 这个顺序发货，则工人先拿到 7、6 两种不能装填的颜色，将其按照 7 在下、6 在上的顺序堆在货架上；拿到 1 时可以直接装填；拿到 3 时又得临时码放在 6 号颜色箱上；拿到 2 时可以直接装填；随后从货架顶取下 3 进行装填；然后拿到 5，临时码放到 6 上面；最后取了 4 号颜色直接装填；剩下的工作就是顺序从货架上取下 5、6、7 依次装填。
但如 ...
