团队程序设计天梯赛-寒假训练1总结

灰太狼 2023-10-03 18:26 16阅读 0赞

#### 文章目录 ####

*  7-6 情人节 (15 分)
 *   *  题目
     *  知识点
     *  代码
 *  7-7 吃火锅 (15 分)
 *   *  题目
     *  知识点
     *  代码
 *  7-8 点赞 (20 分)
 *   *  思路
     *  代码
 *  7-9 N个数求和 (20 分)
 *   *  题目
     *  思路
     *  知识点
     *  代码
 *  7-10 阅览室 (20 分)
 *   *  题目
     *  注意点
     *  知识点
     *  代码
 *  7-11 古风排版 (20 分)
 *   *  题目
     *  思路
     *  代码
 *  7-12 这是二叉搜索树吗？ (25 分)
 *   *  题目
     *  思路
     *  代码
 *  7-13 红色警报 (25 分)
 *   *  题目
     *  思路
     *  代码
 *  7-14 单身狗 (25 分)
 *   *  题目
     *  思路
     *  代码
 *  7-15 插入排序还是归并排序 (25 分)
 *   *  题目
     *  思路
     *  知识点
     *  代码
 *  7-16 关于堆的判断 (25 分)
 *   *  题目
     *  思路技巧
     *  知识点
     *  代码

## 7-6 情人节 (15 分) ##

### 题目 ###

以上是朋友圈中一奇葩贴：“2月14情人节了，我决定造福大家。第2个赞和第14个赞的，我介绍你俩认识…………咱三吃饭…你俩请…”。现给出此贴下点赞的朋友名单，请你找出那两位要请客的倒霉蛋。

输入格式：  
输入按照点赞的先后顺序给出不知道多少个点赞的人名，每个人名占一行，为不超过10个英文字母的非空单词，以回车结束。一个英文句点.标志输入的结束，这个符号不算在点赞名单里。

输出格式：  
根据点赞情况在一行中输出结论：若存在第2个人A和第14个人B，则输出“A and B are inviting you to dinner…”；若只有A没有B，则输出“A is the only one for you…”；若连A都没有，则输出“Momo… No one is for you …”。

输入样例1：

GaoXZh
    Magi
    Einst
    Quark
    LaoLao
    FatMouse
    ZhaShen
    fantacy
    latesum
    SenSen
    QuanQuan
    whatever
    whenever
    Potaty
    hahaha
    .

输出样例1：

Magi and Potaty are inviting you to dinner...

输入样例2：

LaoLao
    FatMouse
    whoever

.  
输出样例2：

FatMouse is the only one for you...

输入样例3：

LaoLao
    .

输出样例3：

Momo... No one is for you ...

### 知识点 ###

使用：

string s;
    while(cin>>s)//不断读入字符串
    {
        
    if(s==".") break;//当读入的字符串是"."
    v.push_back(s);
    }

实现不断读入字符串

### 代码 ###

#include<iostream>
    using namespace std;
    int main() {
        
    	vector<string> v;//每次读入的字符串
    	string s;
    	while(cin>>s) {
         //不断读入字符串
    		if(s==".") break;//当读入的字符串是"."
    		v.push_back(s);
    	}
    	if(v.size()>=14)
    		cout << v[1] << " and " << v[13] << " are inviting you to dinner...";
    	else if(v.size()>=2)
    		cout << v[1] << " is the only one for you...";
    	else
    		cout << "Momo... No one is for you ...";
    	return 0;
    }

## 7-7 吃火锅 (15 分) ##

### 题目 ###

以上图片来自微信朋友圈：这种天气你有什么破事打电话给我基本没用。但是如果你说“吃火锅”，那就厉害了，我们的故事就开始了。

本题要求你实现一个程序，自动检查你朋友给你发来的信息里有没有 chi1 huo3 guo1。

输入格式：  
输入每行给出一句不超过 80 个字符的、以回车结尾的朋友信息，信息为非空字符串，仅包括字母、数字、空格、可见的半角标点符号。当读到某一行只有一个英文句点 . 时，输入结束，此行不算在朋友信息里。

输出格式：  
首先在一行中输出朋友信息的总条数。然后对朋友的每一行信息，检查其中是否包含 chi1 huo3 guo1，并且统计这样厉害的信息有多少条。在第二行中首先输出第一次出现 chi1 huo3 guo1 的信息是第几条（从 1 开始计数），然后输出这类信息的总条数，其间以一个空格分隔。题目保证输出的所有数字不超过 100。

如果朋友从头到尾都没提 chi1 huo3 guo1 这个关键词，则在第二行输出一个表情 -\_-\#。

输入样例 1：

Hello!
    are you there?
    wantta chi1 huo3 guo1?
    that's so li hai le
    our story begins from chi1 huo3 guo1 le

.  
输出样例 1：

5
    3 2

输入样例 2：

Hello!
    are you there?
    wantta qi huo3 guo1 chi1huo3guo1?
    that's so li hai le
    our story begins from ci1 huo4 guo2 le

.  
输出样例 2：

5
    -_-#

### 知识点 ###

字符串中查找子串的find函数  
参考链接：[C++ string中的find()函数][C_ string_find]

### 代码 ###

#include<cstring>
    #include<iostream>
    using namespace std;
    int main() {
        
    	int num = 0, cnt = 0;
    	int start = 0;
    	string s;
    	while(1) {
        
    		getline(cin, s);
    		if(s==".")
    			break;
    		num++;
    		if(s.find("chi1 huo3 guo1")!=string::npos) {
        
    			if(start==0) start = num;
    			cnt++;
    		}
    	}
    	cout << num << endl;
    	if(cnt==0) cout << "-_-#" << endl;
    	else cout << start << " " << cnt;
    }

## 7-8 点赞 (20 分) ##

微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。本题就要求你写个程序，通过统计一个人点赞的纪录，分析这个人的特性。

输入格式：  
输入在第一行给出一个正整数N（≤1000），是该用户点赞的博文数量。随后N行，每行给出一篇被其点赞的博文的特性描述，格式为“K F  
1  
  
⋯F  
K  
  
”，其中1≤K≤10，F  
i  
  
（i=1,⋯,K）是特性标签的编号，我们将所有特性标签从1到1000编号。数字间以空格分隔。

输出格式：  
统计所有被点赞的博文中最常出现的那个特性标签，在一行中输出它的编号和出现次数，数字间隔1个空格。如果有并列，则输出编号最大的那个。

输入样例：

4
    3 889 233 2
    5 100 3 233 2 73
    4 3 73 889 2
    2 233 123

输出样例：

233 3

### 思路 ###

开个大的数组，统计各个标签出现的次数并比较即可

### 代码 ###

#include<iostream>
    using namespace std;
    int main() {
        
    	int n, label; //用户点赞博文的数量
    	cin >> n;
    	int a[1001] = {
        0}; //a[i]:标签为i的出现次数
    	for(int i=0; i<n; i++)  {
         //有n行
    		int k;
    		cin >> k;
    		for(int j=0; j<k; j++) //每行有k个数
    		{
        
    			cin >> label;
    			a[label]++;
    			//数组下标由1开始
    		}
    	}
    	label = 1; //label:出现最多的标签,假设1号标签出现最多
    	for(int i=2; i<=1000; i++)//从2号开始比较
    		if(a[i] >= a[label])
    			label = i;
    	cout << label << " " << a[label];
    	return 0;
    }

## 7-9 N个数求和 (20 分) ##

### 题目 ###

本题的要求很简单，就是求N个数字的和。麻烦的是，这些数字是以有理数分子/分母的形式给出的，你输出的和也必须是有理数的形式。

输入格式：  
输入第一行给出一个正整数N（≤100）。随后一行按格式a1/b1 a2/b2 …给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外，负数的符号一定出现在分子前面。

输出格式：  
输出上述数字和的最简形式 —— 即将结果写成整数部分 分数部分，其中分数部分写成分子/分母，要求分子小于分母，且它们没有公因子。如果结果的整数部分为0，则只输出分数部分。

输入样例1：

5
    2/5 4/15 1/30 -2/60 8/3

输出样例1：

3 1/3

输入样例2：

2
    4/3 2/3

输出样例2：

输入样例3：

3
    1/3 -1/6 1/8

输出样例3：

7/24

### 思路 ###

测试点5是答案为0的情况  
可使用 algorithm 库的 \_\_gcd()函数  
读一个求和一个，结果是suma/sumb  
如何求和？分母通分后分子求和，求和后再约分  
注意不同情况下的输出格式

### 知识点 ###

*  algorithm库中的\_\_gcd()函数求两个数的最大公约数

__gcd(a,b)求a,b的最大公因数
    a*b/__gcd(a,b)求a,b的最小公倍数

传统方法实现求最大公约数：[【C/C++】求最大公约数的三种方法][C_C]

*  按照规定格式输出

### 代码 ###

#include<iostream>
    #include<algorithm>
    //#include<cmath>
    using namespace std;
    void sum(int a, int b, int &suma, int &sumb);
    int lcd(int x, int y);
    void output(int a, int b);
    int main() {
        
    	int a, b, suma=0, sumb=1;
    	int n;
    	cin >> n;
    	int i;
    	char c;
    	for(i=0; i<n; i++) {
        
    		cin >> a >> c >> b;
    		sum(a, b, suma, sumb);
    	}
    	output(suma, sumb);
    }
    void sum(int a, int b, int &suma, int &sumb) {
        
    	int l = lcd(b, sumb);//求两个分母的最小公倍数
    	suma = suma*(l/sumb) + a*(l/b);
    	sumb = l;
    //cout << suma << " " << sumb << endl;
    	int g = __gcd(abs(suma), sumb);//求suma与sumb的最大公约数
    	suma = suma/g;
    	sumb = sumb/g;
    }
    int lcd(int x, int y) {
        
    	//求x与y的最小公倍数
    	return x*y/__gcd(x, y);
    }
    void output(int a, int b) {
        
    	//按格式要求输出分子为a，分母为b 的数
    	if(a<0) {
        
    		cout << "-";
    		a = -a;
    	}
    	if(a==0)
    		cout << "0" << endl;
    	if(a/b>0) {
        
    		cout << a/b;
    		if(a%b!=0)
    			cout << " ";
    	}
    	if(a%b!=0)
    		cout << a%b << "/" << b << endl;
    }

## 7-10 阅览室 (20 分) ##

### 题目 ###

天梯图书阅览室请你编写一个简单的图书借阅统计程序。当读者借书时，管理员输入书号并按下S键，程序开始计时；当读者还书时，管理员输入书号并按下E键，程序结束计时。书号为不超过1000的正整数。当管理员将0作为书号输入时，表示一天工作结束，你的程序应输出当天的读者借书次数和平均阅读时间。

注意：由于线路偶尔会有故障，可能出现不完整的纪录，即只有S没有E，或者只有E没有S的纪录，系统应能自动忽略这种无效纪录。另外，题目保证书号是书的唯一标识，同一本书在任何时间区间内只可能被一位读者借阅。

输入格式：  
输入在第一行给出一个正整数N（≤10），随后给出N天的纪录。每天的纪录由若干次借阅操作组成，每次操作占一行，格式为：

书号（\[1, 1000\]内的整数） 键值（S或E） 发生时间（hh:mm，其中hh是\[0,23\]内的整数，mm是\[0, 59\]内整数）

每一天的纪录保证按时间递增的顺序给出。

输出格式：  
对每天的纪录，在一行中输出当天的读者借书次数和平均阅读时间（以分钟为单位的精确到个位的整数时间）。

输入样例：

3
    1 S 08:10
    2 S 08:35
    1 E 10:00
    2 E 13:16
    0 S 17:00
    0 S 17:00
    3 E 08:10
    1 S 08:20
    2 S 09:00
    1 E 09:20
    0 E 17:00

输出样例：

2 196
    0 0
    1 60

### 注意点 ###

注意干扰因素：借还没有匹配，或者多次借/还同一本书

### 知识点 ###

*  使用fill()函数对数组进行填充：[C++ 中 fill() 的使用][C_ _ fill_]
 *  c++中的floor（向下取整），ceil（向上取整），round（四舍五入）函数：[C语言（C++）中：详解floor函数、ceil函数和round函数][C_C_floor_ceil_round]

### 代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int main() {
        
    	int n;
    	cin >> n;
    	while(n--) {
        
    		int a[1001];
    		fill(a, a+1001, -1);
    		int cnt = 0, sum = 0;
    		while(1) {
        
    			int x, h, m;
    			char c;
    			scanf("%d %c %d:%d", &x, &c, &h, &m);
    			if(x==0) {
        
    				printf("%d %d\n", cnt, cnt==0?0:int(ceil(1.0*sum/cnt)));
    //printf("%d %d\n", cnt, cnt==0?0:int(round(1.0*sum/cnt)));
    				break;
    			} else if(c=='S') a[x] = h*60+m;
    			else if(c=='E' && a[x]!=-1) cnt++, sum+=h*60+m-a[x], a[x]=-1;
    		}
    	}
    	return 0;
    }

## 7-11 古风排版 (20 分) ##

### 题目 ###

中国的古人写文字，是从右向左竖向排版的。本题就请你编写程序，把一段文字按古风排版。

输入格式：  
输入在第一行给出一个正整数N（<100），是每一列的字符数。第二行给出一个长度不超过1000的非空字符串，以回车结束。

输出格式：  
按古风格式排版给定的字符串，每列N个字符（除了最后一列可能不足N个）。

输入样例：

This is a test case  
输出样例：

asa T
    st ih
    e tsi
     ce s

### 思路 ###

1、按照要求一步步cout出来  
2、找出要求格式与原字符串的对应关系后打印

### 代码 ###

思路一代码：

#include <bits/stdc++.h>
    using namespace std;
    char res[10005][10005];
    int main(){
        
    // 	memset(res,sizeof(res),' ');
    	int n;
    	cin>>n;
    	string s;
    	getchar(); 
    	getline(cin,s);
    //	int col_num = ceil(1.0*s.length()/n);
    	int len = s.size();
    	int col_num = len / n + 1;
    	if(len % n == 0) col_num --;
    //	cout<<col_num;
    	int cnt = 0;
    	for(int i = col_num;i>=1;i--){
        
    		for(int j=1;j<=n;j++){
        
    			res[j][i] = s[cnt]?s[cnt]:' ';
    			cnt++;
    		}
    	}
    	for(int i=1;i<=n;i++){
        
    		for(int j=1;j<=col_num;j++){
        
    			cout<<res[i][j];
    		}
    		cout<<'\n';
    	}
    	
    }

思路二代码：

#include<iostream>
    using namespace std;
    int main() {
        
    	int k;
    	string s;
    	cin >> k;
    	getchar();
    	getline(cin, s);
    	int i, j;
    	for(int i=0; i<k; i++)//输出k行
    		 {
        
    		for(int j=(s.size()-1)/k; j>=0; j--)//每行
    			if(j*k+i < s.size()) cout << s[j*k+i];
    			else cout << " ";
    		cout << endl;
    		
    	}
    }

## 7-12 这是二叉搜索树吗？ (25 分) ##

### 题目 ###

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

其左子树中所有结点的键值小于该结点的键值；  
其右子树中所有结点的键值大于等于该结点的键值；  
其左右子树都是二叉搜索树。  
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：  
输入的第一行给出正整数 N（≤1000）。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式：  
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

输入样例 1：

7
    8 6 5 7 10 8 11

输出样例 1：

YES
    5 7 6 8 11 10 8

输入样例 2：

7
    8 10 11 8 6 7 5

输出样例 2：

YES
    11 8 10 7 5 6 8

输入样例 3：

7
    8 6 8 5 10 9 11

输出样例 3：

### 思路 ###

*  先判断本身是否二叉搜索树，不是再判断其镜像是否  
    使用函数ju()判断本身或其镜像，参数mirror用于标记判断本身还是判断镜像。参数s用于返回本次调用  
    后产生的后序序列。
 *  一棵先序序列的树是二叉搜索树的条件：左子树都小于根&&右子树都大于等于根&&左子树是二叉搜索  
    树 && 右子树是二叉搜索树。后两步可使用递归完成。
 *  后序遍历如何产生？递归过程中产生：左子树先序遍历序列+右子树先序遍历序列+根。前面两个序列通  
    过递归调用产生。

### 代码 ###

#include<iostream>
    using namespace std;
    bool ju(int a[], int l, int r, bool mirror, string &s) {
        
    	//判断a[l:r]这部分数据构成的子树或其镜像是否二叉搜索树。s用于返回本次遍历产生的先序序列。
    	if(r-l<=0) {
        
    		if(r==l) s = to_string(a[l]);//只剩一个结点
    		else s = "";
    		return true;
    	}
    	int i, j;
    	if(mirror) {
         //镜像
    		for(i=l+1; i<=r && a[i]>=a[l]; i++);
    		for(j=i; j<=r && a[j]<a[l]; j++);
    	} else {
        
    		for(i=l+1; i<=r && a[i]<a[l]; i++);
    		for(j=i; j<=r && a[j]>=a[l]; j++);
    	}
    	if(j<=r) return false;
    	string s1="", s2="";
    	if(ju(a, l+1, i-1, mirror, s1) && ju(a, i, r, mirror, s2)) {
        
    		if(s1!="") s1 += " ";
    		if(s2!="") s2 += " ";
    		s = s1 + s2 + to_string(a[l]);
    		return true;
    	} else return false;
    }
    int main() {
        
    	int n;
    	cin >> n;
    	int a[1000];
    	for(int i=0; i<n; i++) cin >> a[i];
    	string res1 = "", res2 = "";
    //false：本身 true：镜像
    	if(ju(a, 0, n-1, false, res1)) cout << "YES\n" << res1;
    	else if(ju(a, 0, n-1, true, res2)) cout << "YES\n" << res2;
    	else cout << "NO\n";
    	return 0;
    }

## 7-13 红色警报 (25 分) ##

### 题目 ###

战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的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.。

输入样例：

5 4
    0 1
    1 3
    3 0
    0 4
    5
    1 2 0 4 3

输出样例：

City 1 is lost.
    City 2 is lost.
    Red Alert: City 0 is lost!
    City 4 is lost.
    City 3 is lost.
    Game Over.

### 思路 ###

这个没啥，就是每被攻占一个城市就重新计算一次连通分量数。如果分量数比上一次多了不止一个，就  
说明Red Alert  
为什么本次可以比上次多一个？因为某城市被占领后，它会独立为一个连通分量  
使用dfs(t)深搜从t开始的每个连接点。使用 fun()多次调用dfs(), 调用次数就是连通分量数。

### 代码 ###

//不断计算连通分量
    #include<bits/stdc++.h>
    using namespace std;
    bool vis[500] = {
        0};
    int n;
    int a[500][500] = {
        0};
    void dfs(int t) {
        
    	vis[t] = 0;
    	for(int i=0; i<n; i++)
    		if(a[t][i]==1 && vis[i]==1)
    			dfs(i);
    }
    int fun() {
        
    	for(int i=0; i<n; i++) vis[i] = 1;
    	int cnt = 0;
    	for(int i=0; i<n; i++) {
        
    		if(vis[i]==1) {
        
    			cnt++;
    			dfs(i);
    		}
    	}
    	return cnt;
    }
    int main() {
        
    	int m;
    	cin >> n >> m;
    	for(int i=0; i<m; i++) {
        
    		int x, y;
    		cin >> x >> y;
    		a[x][y] = a[y][x] = 1;
    	}
    	int cnt = fun();
    	int k;
    	cin >> k;
    	for(int i=0; i<k; i++) {
        
    		int x;
    		cin >> x;
    		for(int j=0; j<n; j++) a[x][j] = a[j][x] = 0;
    		int tmp = fun();
    //被删的城市本身成了一个连通分量
    		if(tmp>cnt+1) printf("Red Alert: City %d is lost!\n", x);
    		else printf("City %d is lost.\n", x);
    		cnt = tmp;
    		if(i==n-1) cout << "Game Over.";
    	}
    	return 0;
    }

## 7-14 单身狗 (25 分) ##

### 题目 ###

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。

输入格式：  
输入第一行给出一个正整数 N（≤50000），是已知夫妻/伴侣的对数；随后 N 行，每行给出一对夫妻/伴侣——为方便起见，每人对应一个 ID 号，为 5 位数字（从 00000 到 99999），ID 间以空格分隔；之后给出一个正整数 M（≤10000），为参加派对的总人数；随后一行给出这 M 位客人的 ID，以空格分隔。题目保证无人重婚或脚踩两条船。

输出格式：  
首先第一行输出落单客人的总人数；随后第二行按 ID 递增顺序列出落单的客人。ID 间用 1 个空格分隔，行的首尾不得有多余空格。

输入样例：

3
    11111 22222
    33333 44444
    55555 66666
    7
    55555 44444 10000 88888 22222 11111 23333

输出样例：

5
    10000 23333 44444 55555 88888

### 思路 ###

使用a数组存储伴侣关系，下标表示ID号。  
因为要按照ID 递增顺序列出落单的客人，所以使用b数组标记要判断的客人，下标表示ID号。回头顺序  
遍历b数组并判断就行。  
测试点2是全0的问题

### 代码 ###

#include<iostream>
    #include<string>
    #include<algorithm>
    using namespace std;
    int main() {
        
    	int n;
    	cin >> n;
    	int a[100000];
    	for(int i=0; i<100000; i++) a[i] = -1;
    	for(int i=0; i<n; i++) {
        
    		int x, y;
    		cin >> x >> y;
    		a[x] = y, a[y] = x;
    	}
    	int b[100000] = {
        0};
    	cin >> n;
    	for(int i=0; i<n; i++) {
        
    		int x;
    		cin >> x;
    		b[x] = 1;
    	}
    	int cnt = 0;
    	for(int i=0; i<=99999; i++)
    		if(b[i] && (a[i]==-1 || b[a[i]]==0)) cnt++, b[i]=-1;
    	if(cnt==0) {
        
    		cout << 0;
    		return 0;
    	}
    	??cout << cnt << endl;
    	int flag = 0;
    	for(int i=0; i<=99999; i++)
    		if(b[i]==-1) {
        
    			if(flag) printf(" %05d", i);
    			else printf("%05d", i);
    			flag = 1;
    		}
    	return 0;
    }

## 7-15 插入排序还是归并排序 (25 分) ##

### 题目 ###

根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入格式：  
输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式：  
首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

输入样例 1：

10
    3 1 2 8 7 5 9 4 6 0
    1 2 3 7 8 5 9 4 6 0

输出样例 1：

Insertion Sort
    1 2 3 5 7 8 9 4 6 0

输入样例 2：

10
    3 1 2 8 7 5 9 4 0 6
    1 3 2 8 5 7 4 9 0 6

输出样例 2：

Merge Sort
    1 2 3 8 4 5 7 9 0 6

### 思路 ###

*  先判断是否插入排序，不是再判断是否归并排序
 *  如果是插入排序产生的中间序列：前一截一定是非降序，剩下那截一定跟原来未排序的序列一致。
 *  归并的判断我也没有好办法，归并一次对比一次

### 知识点 ###

*  插入排序原理
 *  “如果是插入排序产生的中间序列：前一截一定是非降序，剩下那截一定跟原来未排序的序列一致。”
 *  归并排序原理
 *  归并排序代码实现（巧妙）：

void merge(int a[], int b[], int n) {
        
    	int i, k, end;
    	int flag = 0;
    	for(k=1; k<n; k*=2) {
        
    		if(equal(a, b, n)) flag = 1;
    		for(i=0; i+k<n; i+=2*k) {
        
    			end = (i+k+k<=n ? i+k+k : n);
    			sort(a+i, a+end);
    		}
    		if(flag) break;
    	}
    	cout << "Merge Sort\n";
    	output(a, n);
    }

### 代码 ###

#include<iostream>
    #include<algorithm>
    using namespace std;
    bool equal(int a[], int b[], int n) {
        
    	for(int i=0; i<n; i++)
    		if(a[i]!=b[i]) return false;
    	return true;
    }
    void output(int a[], int n) {
        
    	cout << a[0];
    	for(int i=1; i<n; i++)
    		cout << " " << a[i];
    }
    bool insert(int a[], int b[], int n) {
        
    	int i, j;
    	for(i=1; i<n && b[i]>=b[i-1]; i++);
    	for(j=i; j<n && b[j]==a[j]; j++);
    	if(j<n) return false;
    	int x = b[i];
    	for(j=i-1; j>=0 && b[j]>x; j--) b[j+1] = b[j];
    	b[j+1] = x;
    	cout << "Insertion Sort\n";
    	output(b, n);
    	return true;
    }
    void merge(int a[], int b[], int n) {
        
    	int i, k, end;
    	int flag = 0;
    	for(k=1; k<n; k*=2) {
        
    		if(equal(a, b, n)) flag = 1;
    		for(i=0; i+k<n; i+=2*k) {
        
    			end = (i+k+k<=n ? i+k+k : n);
    			sort(a+i, a+end);
    		}
    		if(flag) break;
    	}
    	cout << "Merge Sort\n";
    	output(a, n);
    }
    int main() {
        
    	int n, i;
    	cin >> n;
    	int a[100], b[100];
    	for(i=0; i<n; i++) cin >> a[i];
    	for(i=0; i<n; i++) cin >> b[i];
    	if(insert(a, b, n)) return 0;
    	merge(a, b, n);
    	return 0;
    }

## 7-16 关于堆的判断 (25 分) ##

### 题目 ###

将一系列给定数字顺序插入一个初始为空的小顶堆H\[\]。随后判断一系列相关命题是否为真。命题分下列几种：

x is the root：x是根结点；  
x and y are siblings：x和y是兄弟结点；  
x is the parent of y：x是y的父结点；  
x is a child of y：x是y的一个子结点。  
输入格式：  
每组测试第1行包含2个正整数N（≤ 1000）和M（≤ 20），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间\[−10000,10000\]内的N个要被插入一个初始为空的小顶堆的整数。之后M行，每行给出一个命题。题目保证命题中的结点键值都是存在的。

输出格式：  
对输入的每个命题，如果其为真，则在一行中输出T，否则输出F。

输入样例：

5 4
    46 23 26 24 10
    24 is the root
    26 and 23 are siblings
    46 is the parent of 23
    23 is a child of 10

输出样例：

F
    T
    F
    T

### 思路技巧 ###

技巧：注意数据有可能是负数。来一个调整一个（往上调整），比全部存入数组再调整方便（从n/2开始  
往下调整），因为往上调只有一个父结点，往下有两个孩子结点。而且全部存入数组再调整，答案未必  
正确。因为得到的堆跟来一个调整一个可能不相同。

### 知识点 ###

*  堆排序
 *  调整堆代码实现：（来一个调整一个）

void adjust(int a[], int s) {
        
    	//假设a[1..s-1]已经是堆，将a[1..s]调整为以a[1]为根的小根堆
    	int j = s/2;
    	while(j>=1) {
        
    		if(a[j]<a[s]) break;
    		swap(a[s], a[j]);
    		s = j;
    		j = s/2;
    	}
    }

*  堆排序中根节点，兄弟节点，父节点，子节点的判断的具体实现：  
    兄弟节点：

if(s[0]=='a') {
         //26 and 23 are siblings
    			int y;
    			cin >> y >> s >> s;
    			int flag = 0;
    			if(xpos%2==0) {
        
    				if(xpos+1<=n && a[xpos+1]==y) flag = 1;
    			} else if(xpos>1 && a[xpos-1]==y) flag = 1;
    			if(flag)cout << "T\n";
    			else cout << "F\n";

父节点：

if(s[0]=='a') {
         //23 is a child of 10
    				int y;
    				cin >> s >> s >> y;
    				if(xpos/2>0 && a[xpos/2]==y) cout << "T\n";
    				else cout << "F\n";

子节点：

else {
        
    					int y;
    					cin >> s >> y;//46 is the parent of 23
    					if((xpos*2<=n && a[xpos*2]==y) || (xpos*2+1<=n &&
    					                                   a[xpos*2+1]==y)) cout << "T\n";
    					else cout << "F\n";
    				}

根节点：

if(s[0]=='r') {
         //24 is the root
    					if(xpos==1) cout << "T\n";
    					else cout << "F\n";

### 代码 ###

#include<bits/stdc++.h>
    using namespace std;
    void adjust(int a[], int s) {
        
    	//假设a[1..s-1]已经是堆，将a[1..s]调整为以a[1]为根的小根堆
    	int j = s/2;
    	while(j>=1) {
        
    		if(a[j]<a[s]) break;
    		swap(a[s], a[j]);
    		s = j;
    		j = s/2;
    	}
    }
    int main() {
        
    	int n, m;
    	cin >> n >> m;
    	int a[1001];
    	for(int i=1; i<=n; i++)
    		 {
        
    		cin >> a[i];
    		adjust(a, i);
    		
    	}
    	for(int i=0; i<m; i++) {
        
    		string s;
    		int x;
    		cin >> x >> s;
    		int xpos;
    		for(xpos=1; xpos<=n; xpos++)
    			if(a[xpos]==x) break;
    		if(s[0]=='a') {
         //26 and 23 are siblings
    			int y;
    			cin >> y >> s >> s;
    			int flag = 0;
    			if(xpos%2==0) {
        
    				if(xpos+1<=n && a[xpos+1]==y) flag = 1;
    			} else if(xpos>1 && a[xpos-1]==y) flag = 1;
    			if(flag)cout << "T\n";
    			else cout << "F\n";
    		} else {
        
    			cin >> s;
    			if(s[0]=='a') {
         //23 is a child of 10
    				int y;
    				cin >> s >> s >> y;
    				if(xpos/2>0 && a[xpos/2]==y) cout << "T\n";
    				else cout << "F\n";
    			} else {
        
    				cin >> s;
    				if(s[0]=='r') {
         //24 is the root
    					if(xpos==1) cout << "T\n";
    					else cout << "F\n";
    				} else {
        
    					int y;
    					cin >> s >> y;//46 is the parent of 23
    					if((xpos*2<=n && a[xpos*2]==y) || (xpos*2+1<=n &&
    					                                   a[xpos*2+1]==y)) cout << "T\n";
    					else cout << "F\n";
    				}
    			}
    		}
    	}
    	return 0;
    }

[C_ string_find]: https://www.cnblogs.com/wkfvawl/p/9429128.html
[C_C]: https://blog.csdn.net/qq_31828515/article/details/51812154
[C_ _ fill_]: https://blog.csdn.net/liu16659/article/details/87152348
[C_C_floor_ceil_round]: https://blog.csdn.net/dangzhangjing97/article/details/81279862