团队程序设计天梯赛-3.31排位赛总结

港控/mmm° 2023-10-03 18:38 14阅读 0赞

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

*  7-1 逆序的三位数 (10 分)
 *   *  题目描述
     *  知识点
     *  代码
 *  7-2 九宫格输入法 (10 分)
 *   *  题目描述
     *  知识点
     *  代码
 *  7-3 装箱问题 (15 分)假设有N项物品，大小分别为s
 *   *  思路
     *  代码
 *  7-4 掉入陷阱的数字 (15 分)
 *   *  题目描述
     *  知识点
     *  代码
 *  7-5 龟兔赛跑 (20 分)
 *   *  题目描述
     *  思路
     *  注意点
     *  知识点
     *  代码一（参考代码）
     *  代码二（我的代码）
 *  7-6 谷歌的招聘 (20 分)
 *   *  题目描述
     *  思路
     *  知识点
     *  代码
 *  7-7 火星文 (25 分)
 *   *  题目描述
     *  知识点
     *  注意点
     *  思路
     *  代码
 *  7-8 地下迷宫探索 (25 分)
 *   *  题目描述
     *  思路
     *  知识点
     *  代码
 *  7-9 二叉搜索树的2层结点统计 (25 分)
 *   *  题目描述
     *  思路
     *  知识点
     *  说明
     *  代码一（二叉链表建树）
     *  代码二（只有14分）
 *  7-10 天梯地图 (25 分)
 *   *  题目描述
     *  思路
     *  代码
     *   *  ps：还没看
 *  7-11 长城 (25 分)
 *   *  题目描述
     *  思路
     *  代码
     *   *  ps：还没看

## 7-1 逆序的三位数 (10 分) ##

### 题目描述 ###

程序每次读入一个正3位数，然后输出按位逆序的数字。注意：当输入的数字含有结尾的0时，输出不应带有前导的0。比如输入700，输出应该是7。

输入格式：  
每个测试是一个3位的正整数。

输出格式：  
输出按位逆序的数。

输入样例：

123

输出样例：

321

### 知识点 ###

*  reverse（）函数的使用：可以翻转数组，字符串，向量等！！[C++中的reverse()函数][C_reverse]
 *  stoi（）函数的使用：将字符串转化为对应的数字，（会去掉前导0！！）

### 代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int main() {
        
    	string s;
    	cin >> s;
    	reverse(s.begin(), s.end());
    	cout << stoi(s);
    	return 0;
    }

## 7-2 九宫格输入法 (10 分) ##

### 题目描述 ###

假设有九宫格输入法键盘布局如下：

[ 1,.?! ] [ 2ABC ] [ 3DEF  ]
     [ 4GHI  ] [ 5JKL ] [ 6MNO  ]
     [ 7PQRS ] [ 8TUV ] [ 9WXYZ ]
               [ 0空  ]

注意：中括号\[ \]仅为了表示键盘的分隔，不是输入字符。每个中括号中，位于首位的数字字符即是键盘的按键，按一下即可输入该数字字符。多次按同一个键，则输入的字符依次循环轮流，例如按两次3，则输入D；按5次7，则输入S；按6次2，则输入A。按键0的输入组合是0和空格字符，即按两次0输入空格。

你需要对于给定的按键组合，给出该组合对应的文本。

输入格式:  
输入在一行中给出数个字符的按键组合（例如 999 表示按3次9），每个字符的按键组合之间用空格间隔，最后一个输入法组合之后以换行结束。输入数据至少包括一个字符的按键组合，且输入总长度不超过500个字符。

输出格式:  
在一行中输出该按键组合对应的文本。

输入样例:

22 5555 22 666 00 88 888 7777 4444 666 44

输出样例:

ALAN TURING

### 知识点 ###

取模的运用，取模的时候要小心，不确定的话可以枚举几个看看

### 代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int main() {
        
    	string a[] = {
        "00", "1,.?!", "2ABC", "3DEF", "4GHI", "5JKL", "6MNO",
    	              "7PQRS", "8TUV", "9WXYZ"
    	             };
    	string s;
    	while(cin>>s) {
        
    		int t = (s.size()-1)%(a[s[0]-48].size());
    		if(s[0]=='0' && t==0) cout << '0';
    		else if(s[0]=='0' && t==1) cout << ' ';
    		else cout << a[s[0]-48][t];
    	}
    	return 0;
    }

## 7-3 装箱问题 (15 分)假设有N项物品，大小分别为s ##

1  
  
、s  
2  
  
、…、s  
i  
  
、…、s  
N  
  
，其中s  
i  
  
为满足1≤s  
i  
  
≤100的整数。要把这些物品装入到容量为100的一批箱子（序号1-N）中。装箱方法是：对每项物品, 顺序扫描箱子，把该物品放入足以能够容下它的第一个箱子中。请写一个程序模拟这种装箱过程，并输出每个物品所在的箱子序号，以及放置全部物品所需的箱子数目。

输入格式：  
输入第一行给出物品个数N（≤1000）；第二行给出N个正整数s  
i  
  
（1≤s  
i  
  
≤100，表示第i项物品的大小）。

输出格式：  
按照输入顺序输出每个物品的大小及其所在的箱子序号，每个物品占1行，最后一行输出所需的箱子数目。

输入样例：

8
    60 70 80 90 30 40 10 20

输出样例：

60 1
    70 2
    80 3
    90 4
    30 1
    40 5
    10 1
    20 2
    5

### 思路 ###

两层循环，先用容量100初始化数组，循环时能装下就减去所需容量

### 代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int main() {
        
    	int n;
    	cin >> n;
    	vector<int> a;
    	for(int i=0; i<n; i++) a.push_back(100);
    	int max = 0;
    	for(int i=0; i<n; i++) {
        
    		int x, j;
    		cin >> x;
    		for(j=0; a[j]<x; j++);
    		cout << x << " " << j+1 << endl;
    		if(j+1>max) max = j+1;
    		a[j] -= x;
    	}
    	cout << max;
    	return 0;
    }

## 7-4 掉入陷阱的数字 (15 分) ##

### 题目描述 ###

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_11_color_FFFFFF_t_70_g_se_x_16]  
输入格式:  
在一行内给出一个自然数N 0（N 0 <30000）。  
输出格式:  
![在这里插入图片描述][f8d119e393e94f1482ce8ae8d754cad4.png]  
输入样例:

输出样例:

1:16
    2:22
    3:13
    4:13

### 知识点 ###

关于求各个位数之和的两种方法  
方法一（将数字分割后求）

int fun(int x) {
        
    	int res = 0;
    	while(x) {
        
    		res += x%10;
    		x /= 10;
    	}
    	return res*3+1;
    }

方法二（转为字符串后各个位数相加）

int each_num = n;
    	string s = to_string(each_num);
    	int sum_each=0;
    	for(int i=0; i<s.size(); i++) {
        
    		sum_each+=s[i]-'0';
    	}
    	int each_res = sum_each*3+1;

按题目要求进行循环即可

### 代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int fun(int x) {
        
    	int res = 0;
    	while(x) {
        
    		res += x%10;
    		x /= 10;
    	}
    	return res*3+1;
    }
    int main() {
        
    	int n;
    	cin >> n;
    	for(int i=1; ; i++)
    		 {
        
    		int x = fun(n);
    		printf("%d:%d\n", i, x);
    		if(x==n) break;
    		n = x;
    	}
    }

## 7-5 龟兔赛跑 (20 分) ##

### 题目描述 ###

乌龟与兔子进行赛跑，跑场是一个矩型跑道，跑道边可以随地进行休息。乌龟每分钟可以前进3米，兔子每分钟前进9米；兔子嫌乌龟跑得慢，觉得肯定能跑赢乌龟，于是，每跑10分钟回头看一下乌龟，若发现自己超过乌龟，就在路边休息，每次休息30分钟，否则继续跑10分钟；而乌龟非常努力，一直跑，不休息。假定乌龟与兔子在同一起点同一时刻开始起跑，请问T分钟后乌龟和兔子谁跑得快？

输入格式：  
输入在一行中给出比赛时间T（分钟）。

输出格式：  
在一行中输出比赛的结果：乌龟赢输出@*@，兔子赢输出\_，平局则输出-*\-；后跟1空格，再输出胜利者跑完的距离。

输入样例：

242

输出样例：

@_@ 726

### 思路 ###

参考代码中是把每一分钟两者的情况都算出来（先把乌龟的算出来）  
我的代码是直接从0开始遍历每一分钟，根据对应的情况进行比较，flag为true时代表兔子在跑，false为在休息

### 注意点 ###

注意两者打平的时候也要输出跑过的距离（两者相等）

### 知识点 ###

.back()可取得容器中的最后一个值！！！

### 代码一（参考代码） ###

#include<bits/stdc++.h>
    using namespace std;
    int main() {
        
    	int t;
    	cin >> t;
    	vector<int> a, b;
    	a.push_back(0);
    	b.push_back(0);
    	for(int i=1; i<=t+30; i++) a.push_back(i*3);//提前计算乌龟第i分钟跑了多少米
    	int k = 0;
    	while(k<=t) {
        
    		if(k<=t)
    			for(int i=0; i<10; i++, k++) //跑10分钟
    				b.push_back(b.back()+9);
    		if(k<=t && b[k]>a[k]) //是否需要休息30分钟
    			for(int i=0; i<30; i++, k++)
    				b.push_back(b.back());
    	}
    	if(a[t]>b[t]) cout << "@_@ " << a[t];
    	else if(a[t]==b[t]) cout << "-_- " << a[t];
    	else cout << "^_^ " << b[t];
    	return 0;
    }

### 代码二（我的代码） ###

#include <bits/stdc++.h>
    using namespace std;
    int main() {
        
    	int rab = 0;
    	int tut = 0;
    	int n;
    	cin>>n;
    	int run_time=0;
    	int flag = true;
    	for(int i=0; i<n; i++) {
        
    		if(i==run_time) {
        
    			flag = true;
    		}
    		if(i%10==0&&flag) {
        
    			if(rab>tut) {
        
    				flag = false;
    				run_time = i+30;
    			} else {
        
    				flag = true;
    			}
    
    		}
    		if(flag) {
        
    			rab+=9;
    		}
    		tut+=3;
    	}
    //	cout<<rab<<" "<<tut<<endl;
    	if(rab>tut) {
        
    		cout<<"^_^ "<<rab;
    	} else if(rab<tut) {
        
    		cout<<"@_@ "<<tut;
    	} else {
        
    		cout<<"-_- "<<tut;
    	}
    }

## 7-6 谷歌的招聘 (20 分) ##

### 题目描述 ###

004 年 7 月，谷歌在硅谷的 101 号公路边竖立了一块巨大的广告牌（如下图）用于招聘。内容超级简单，就是一个以 .com 结尾的网址，而前面的网址是一个 10 位素数，这个素数是自然常数 e 中最早出现的 10 位连续数字。能找出这个素数的人，就可以通过访问谷歌的这个网站进入招聘流程的下一步。

自然常数 e 是一个著名的超越数，前面若干位写出来是这样的：e = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921… 其中粗体标出的 10 位数就是答案。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_11_color_FFFFFF_t_70_g_se_x_16 1]

本题要求你编程解决一个更通用的问题：从任一给定的长度为 L 的数字中，找出最早出现的 K 位连续数字所组成的素数。

输入格式：  
输入在第一行给出 2 个正整数，分别是 L（不超过 1000 的正整数，为数字长度）和 K（小于 10 的正整数）。接下来一行给出一个长度为 L 的正整数 N。

输出格式：  
在一行中输出 N 中最早出现的 K 位连续数字所组成的素数。如果这样的素数不存在，则输出 404。注意，原始数字中的前导零也计算在位数之内。例如在 200236 中找 4 位素数，0023 算是解；但第一位 2 不能被当成 0002 输出，因为在原始数字中不存在这个 2 的前导零。

输入样例 1：

20 5
    23654987725541023819

输出样例 1：

49877

输入样例 2：

10 3
    2468001680

输出样例 2：

404

### 思路 ###

以字符串形式输入，遍历字符串，不断截取所需长度的字符串，使用stoi（会自动去掉前导0）将截取的字符串转为整型数，调用判断素数的函数，如果是素数则输出该数，flag设为true，若flag为false则输出404

### 知识点 ###

*  求素数的几种方法（一般开个方就够用了）  
    [求质数（素数）的函数][Link 1]
 *  截取字符串中的子串：s.substr()  
    语法  
    substr(size\_type \_Off = 0,size\_type \_Count = npos)  
    一种构造string的方法  
    形式 ： s.substr(pos, len)  
    返回值： string，包含s中从pos开始的len个字符的拷贝（pos的默认值是0，len的默认值是s.size() - pos，即不加参数会默认拷贝整个s）  
    异常 ：若pos的值超过了string的大小，则substr函数会抛出一个out\_of\_range异常；若pos+n的值超过了string的大小，则substr会调整n的值，只拷贝到string的末尾  
    注意参数是开始位置和截取的长度！！！！
 *  stoi

### 代码 ###

#include<iostream>
    #include<string>
    #include<cmath>
    using namespace std;
    bool prime(int x) {
        
    	if(x<=1) return false;
    	int k = sqrt(x);
    	for(int i=2; i<=k; i++)
    		if(x%i==0) return false;
    	return true;
    }
    int main() {
        
    	int n, k;
    	cin >> n >> k;
    	string s;
    	cin >> s;
    	int flag = 0;
    	for(int i=0; i<=n-k; i++) {
        
    		string tmp = s.substr(i, k);
    		if(prime(stoi(tmp))) {
        
    			cout << tmp;
    			flag = 1;
    			break;
    		}
    	}
    	if(flag==0) cout << "404";
    	return 0;
    }

## 7-7 火星文 (25 分) ##

### 题目描述 ###

火星人是以 13 进制计数的：

地球人的 0 被火星人称为 tret。 地球人数字 1 到 12 的火星文分别为：jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec。 火星人将进位以后的 12 个高位数字分别称为：tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou。 例如地球人的数字 29 翻译成火星文就是 hel mar；而火星文 elo nov 对应地球数字 115。为了方便交流，请你编写程序实现地球和火星数字之间的互译。

输入格式:  
输入第一行给出一个正整数 N（<100），随后 N 行，每行给出一个 \[0, 169) 区间内的数字 —— 或者是地球文，或者是火星文。

输出格式:  
对应输入的每一行，在一行中输出翻译后的另一种语言的数字。

输入样例:

4
    29
    5
    elo nov
    tam

输出样例:

hel mar
    may
    115
    13

### 知识点 ###

*  13进制与10进制的转换
 *  用substr截取字符串中的子串
 *  isdigit判断该字符是否为数字对应的字符

### 注意点 ###

注意输出火星文时有三种情况：1.只有高位（这时候低位不是输出tret！！！参考样例中的最后一个），2.只有低位 3. 高低位都有

### 思路 ###

这个题目，考的是细心以及逻辑表现  
数值转为火星后，如果低位为0，只输出高位（样例就是这样）  
输出火星时：1.只有高位，2.只有低位 3. 高低位都有，要注意三种情况下的空格和换行处理  
火星转数值：要注意高位单词有可能跟低位单词一起出现，也有可能单独出现

### 代码 ###

#include<bits/stdc++.h>
    using namespace std;
    string di[] = {
        "tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug",
                   "sep", "oct", "nov", "dec"
                  };
    string gao[] = {
        "", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo",
                    "syy", "lok", "mer", "jou"
                   };
    void huoxing(int x) {
        
    	//数值转火星
    	if(x==0)//把这种情况放在下面的else-if一起处理也可以，不过这样写不容易错。
    		 {
        
    		cout << di[0] << endl;
    		return;
    		
    	}
    	if(x/13) cout << gao[x/13];
    	if(x/13 && x%13) cout << " " << di[x%13];
    	else if(x%13) cout << di[x%13];
    	cout << endl;
    }
    void shuzi(string s) {
        
    	//火星转数值 ?
    	if(s=="tret")//这五行不写也可以，因为下面会处理到这种情况
    		 {
        
    		cout << 0 << endl;
    		return;
    		
    	} 
    	string t1 = "", t2;
    	if(s.size()>3)
    		 {
        
    		t1 = s.substr(0, 3);
    		t2 = s.substr(4);
    		
    	}
    	else t2 = s;
    	int x = 0, y = 0;
    	for(int i=0; i<13; i++)
    	 {
        
    		if(gao[i]==t1) x = i*13;
    		if(di[i]==t2) y = i;
    		if(gao[i]==t2) y = i*13;//t2的单词有可能是高位单词也有可能是低位单词
    		
    	}
    	??cout << x+y << endl;
    }
    int main() {
        
    	int n;
    	cin >> n;
    	getchar();
    	while(n--)
    	{
        
    		string s;
    		getline(cin, s);
    		if(isdigit(s[0])) huoxing(stoi(s));
    		else shuzi(s);
    		
    	} 
    	return 0;
    }

## 7-8 地下迷宫探索 (25 分) ##

### 题目描述 ###

地道战是在抗日战争时期，在华北平原上抗日军民利用地道打击日本侵略者的作战方式。地道网是房连房、街连街、村连村的地下工事，如下图所示。  
![在这里插入图片描述][0e9d60df778943438fd9dad87911f36d.png]  
我们在回顾前辈们艰苦卓绝的战争生活的同时，真心钦佩他们的聪明才智。在现在和平发展的年代，对多数人来说，探索地下通道或许只是一种娱乐或者益智的游戏。本实验案例以探索地下通道迷宫作为内容。

假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点（包括通道的端点）上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点？  
![在这里插入图片描述][c479d6e7ff744849a164f7c5bf710a31.png]  
输入格式:  
输入第一行给出三个正整数，分别表示地下迷宫的节点数N（1<N≤1000，表示通道所有交叉点和端点）、边数M（≤3000，表示通道数）和探索起始节点编号S（节点从1到N编号）。随后的M行对应M条边（通道），每行给出一对正整数，分别是该条边直接连通的两个节点的编号。

输出格式:  
若可以点亮所有节点的灯，则输出从S开始并以S结束的包含所有节点的序列，序列中相邻的节点一定有边（通道）；否则虽然不能点亮所有节点的灯，但还是输出点亮部分灯的节点序列，最后输出0，此时表示迷宫不是连通图。

由于深度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以节点小编号优先的次序访问（点灯）。在点亮所有可以点亮的灯后，以原路返回的方式回到起点。

输入样例1:

6 8 1
    1 2
    2 3
    3 4
    4 5
    5 6
    6 4
    3 6
    1 5

输出样例1:

1 2 3 4 5 6 5 4 3 2 1

输入样例2:

6 6 6
    1 2
    1 3
    2 3
    5 4
    6 5
    6 4

输出样例2:

6 4 5 4 6 0

### 思路 ###

每个顶点可以经过多次。  
只要没遍历过的顶点都得遍历。  
因为要列出返回路径，所以在访问了下一个顶点后，当前顶点还得入栈。

### 知识点 ###

用vis数组记录当前点是否被访问  
深搜

### 代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int n, m, s;
    int a[1001][1001];
    bool vis[1001];
    vector<int> path, bpath;
    int cnt, bcnt = 0;
    void dfs(int t) {
        
    	path.push_back(t);
    	vis[t] = 1;
    	for(int i=1; i<=n; i++) {
        
    		if(a[t][i]==1 && vis[i]==0) {
        
    			dfs(i);
    			path.push_back(t);//回头会经过这个点
    		}
    	}
    }
    int main() {
        
    	cin >> n >> m >> s;
    	while(m--) {
        
    		int x, y;
    		cin >> x >> y;
    		a[x][y] = a[y][x] = 1;
    	}
    	dfs(s);
    	int flag = 0;
    	for(int x:path) {
        
    		if(flag) cout << " ";
    		flag = 1;
    		cout << x;
    	}
    	for(int i=1; i<=n; i++)
    		if(vis[i]==0) {
        
    			cout << " 0";
    			break;
    		}
    	return 0;
    }

## 7-9 二叉搜索树的2层结点统计 (25 分) ##

### 题目描述 ###

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

将一系列数字按给定顺序插入一棵初始为空的二叉搜索树，你的任务是统计结果树中最下面 2 层的结点数。

输入格式：输入在第一行给出一个正整数 N (≤1000)，为插入数字的个数。第二行给出 N 个 \[−1000,1000\] 区间内的整数。数字间以空格分隔。

输出格式：在一行中输出最下面 2 层的结点总数。

输入样例：

9 
    25 30 42 16 20 20 35 -5 28

输出样例：

### 思路 ###

根据题目要求建立二叉搜索树  
这个不能使用map来建立二叉搜索树，会超时。因为map是基于红黑树的，每次查找都是O(logn)  
使用数据结构里的二叉链表建树

### 知识点 ###

使用二叉链表建树！！  
先定义结点结构体

struct node{
        
    	int value;
    	node *lch,*rch;
    };

递归建立二叉搜索树

void cre(node* &t, int x, int level) {
        
    	if(t==NULL) {
        
    		t = new node;
    		t->lch = t->rch = NULL;
    		t->value = x;
    		cnt[level]++;
    		if(level>mmax) mmax = level;
    		return;
    	}
    	if(x<=t->value) cre(t->lch, x, level+1);
    	else cre(t->rch, x, level+1);
    }

### 说明 ###

我当时一开始用的是数组，结果段错误，然后用了vector也是段错误，一开始开的小只有10分，但后来开到1000000就有14分了！！但还是不能全过，后来改用了map结果有的点运行超时，还是不能全过，但这种建树的方法还是很棒的！！见代码二

### 代码一（二叉链表建树） ###

#include<bits/stdc++.h>
    using namespace std;
    struct node {
        
    	int value;
    	node *lch, *rch;
    };
    int mmax = 0;
    map<int, int> cnt;//cnt[第几层] = 结点个数
    void cre(node* &t, int x, int level) {
        
    	if(t==NULL) {
        
    		t = new node;
    		t->lch = t->rch = NULL;
    		t->value = x;
    		cnt[level]++;
    		if(level>mmax) mmax = level;
    		return;
    	}
    	if(x<=t->value) cre(t->lch, x, level+1);
    	else cre(t->rch, x, level+1);
    }
    int main() {
        
    	int n;
    	cin >> n;
    	node *root = NULL;
    	while(n--) {
        
    		int x;
    		cin >> x;
    		cre(root, x, 1);
    	}
    	cout << cnt[mmax]+cnt[mmax-1];
    }

### 代码二（只有14分） ###

#include <bits/stdc++.h>
    using namespace std;
    //int tree[10000];
    //int ceng[10000];
    map<long long,long long> m1;
    map<long long,long long> m2;
    
    int max_id = 0;
    void insert(int x){
        
    	long long i=1;
    	long long cnt = 0;
    	while(m1[i]!=0){
        
    		cnt++;
    		if(x<=m1[i]){
        
    			i=i*2;
    		}
    		else{
        
    			i=i*2+1;
    		}
    	}
    	m1[i] = x;
    	m2[i] = cnt;
    //	max_id = max(max_id,i);
    }
    int main(){
        
    	long long n;
    	cin>>n;
    	
    	long long root;
    	cin>>root;
    	m1[1] = root;
    	for(long long i=2;i<=n;i++){
        
    		long long num;
    		cin>>num;
    		insert(num);
    	}
    //	for(long long i=1;i<=max_id;i++){
        
    //		cout<<tree[0][i]<<" ";
    //	}
    //	for(long long i=1;i<=max_id;i++){
        
    //		cout<<tree[1][i]<<" ";
    //	}
    	long long max_ceng = 0;
    //	for(long long i=1;i<=max_id;i++){
        
    		for(auto t:m2){
        
    			if(t.second>max_ceng){
        
    			max_ceng = t.second;
    		}
    		}
    		
    //	}
    	long long max_ceng_minus1 = max_ceng-1;
    	long long cnt_res = 0;
    //	for(long long i=1;i<=max_id;i++){
        
    		for(auto t:m2){
        
    			if(t.second == max_ceng||t.second == max_ceng_minus1){
        
    			cnt_res++;
    		}
    		}
    		
    //	}
    	cout<<cnt_res;
    	
    }

## 7-10 天梯地图 (25 分) ##

### 题目描述 ###

本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。

输入格式：  
输入在第一行给出两个正整数N（2 ≤ N ≤ 500）和M，分别为地图中所有标记地点的个数和连接地点的道路条数。随后M行，每行按如下格式给出一条道路的信息：

V1 V2 one-way length time  
其中V1和V2是道路的两个端点的编号（从0到N-1）；如果该道路是从V1到V2的单行线，则one-way为1，否则为0；length是道路的长度；time是通过该路所需要的时间。最后给出一对起点和终点的编号。

输出格式：  
首先按下列格式输出最快到达的时间T和用节点编号表示的路线：

Time = T: 起点 => 节点1 => … => 终点  
然后在下一行按下列格式输出最短距离D和用节点编号表示的路线：

Distance = D: 起点 => 节点1 => … => 终点  
如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的。

如果这两条路线是完全一样的，则按下列格式输出：

Time = T; Distance = D: 起点 => 节点1 => … => 终点  
输入样例1：

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

输出样例1：

Time = 6: 5 => 4 => 8 => 3
    Distance = 3: 5 => 1 => 3

输入样例2：

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

输出样例2：

Time = 3; Distance = 4: 3 => 2 => 5

### 思路 ###

使用Dijkstra满分，dfs最后一个点超时  
但是这个问题的Dijkstra，少点耐心细心都不行，太容易错了  
dfs始终只关注当前路径，那些最短找最少，最快找最短，设置变量就  
行，不像Dijkstra，搞一大堆辅助数组。而且一个dfs可以同时求最短长度和时间。

### 代码 ###

#include<bits/stdc++.h>
    using namespace std;
    const int inf = INT_MAX;
    const int mm = 500;
    int n, m;
    int b, e;
    int len[mm][mm], ti[mm][mm];
    int lenpre[mm], tipre[mm];
    int blen[mm], bti[mm];
    void Dij1(int data[][mm], int res[], int pre[]) {
        
    	bool vis[mm] = {
        0};
    	int pathlen[mm] = {
        0};
    	fill(res, res+n, inf);
    	for(int i=0; i<n; i++) {
         //初始化
    		if(data[b][i]!=inf) {
        
    			res[i] = data[b][i];
    			pathlen[i]++;
    			pre[i] = b;
    		}
    	}
    	vis[b] = 1;
    	for(int i=1; i<n; i++) {
        
    		int min = inf, minid;
    		for(int j=0; j<n; j++) {
         //选最小
    			if(!vis[j]) {
        
    				if(res[j]<min) min = res[j], minid = j;
    				else if(res[j]!=inf && res[j]==min)
    					if(pathlen[j]<pathlen[minid]) minid = j;
    			}
    		}
    		vis[minid] = 1;
    		if(minid==e) break;
    		for(int j=0; j<n; j++) {
         //根据最小刷新其他
    			if(!vis[j] && data[minid][j]!=inf) {
        
    				if(data[minid][j]+res[minid] < res[j]) {
        
    					res[j] = data[minid][j]+res[minid];
    					pathlen[j] = pathlen[minid]+1;
    					pre[j] = minid;
    				} else if(data[minid][j]+res[minid] == res[j] &&
    				          pathlen[minid]+1<pathlen[j]) {
        
    					pathlen[j] = pathlen[minid]+1;
    					pre[j] = minid;
    				}
    			}
    		}
    	}
    }
    void Dij2(int data[][mm], int res[], int pre[]) {
        
    	//时间
    	bool vis[mm] = {
        0};
    	fill(res, res+n, inf);
    	int dis[mm];//记录对应时间路径的最短距离
    	fill(dis, dis+n, inf);
    	for(int i=0; i<n; i++) {
         //初始化
    		if(data[b][i]!=inf) {
        
    			res[i] = data[b][i];
    			pre[i] = b;
    			dis[i] = len[b][i];//原始数据
    		}
    	}
    	vis[b] = 1;
    	for(int i=1; i<n; i++) {
        
    		int min = inf, minid;
    		for(int j=0; j<n; j++) {
         //选最小
    			if(!vis[j] && res[j]<min) min = res[j], minid = j;
    			else if(!vis[j] && res[j]==min && dis[j]<dis[minid]) minid = j;
    		}
    //cout << "minid: " << minid << endl;
    		vis[minid] = 1;
    		if(minid==e) break;
    		for(int j=0; j<n; j++) {
         //根据最小刷新其他
    			if(!vis[j] && data[minid][j]!=inf) {
        
    				if(data[minid][j]+res[minid] < res[j]) {
        
    					res[j] = data[minid][j]+res[minid];
    					pre[j] = minid;
    					dis[j] = dis[minid] + len[minid][j];
    				} else if(data[minid][j]+res[minid]==res[j] &&
    				          dis[minid]+len[minid][j]<dis[j]) {
        
    					pre[j] = minid;
    					dis[j] = dis[minid] + len[minid][j];
    				}
    			}
    		}
    	}
    }
    int main() {
        
    	cin >> n >> m;
    	fill(len[0], len[0]+mm*mm, inf);
    	fill(ti[0], ti[0]+mm*mm, inf);
    	while(m--) {
        
    		int v1, v2, one, l, t;
    		cin >> v1 >> v2 >> one >> l >> t;
    		len[v1][v2] = l;
    		ti[v1][v2] = t;
    		if(one==0) len[v2][v1] = l, ti[v2][v1] = t;
    	}
    	cin >> b >> e;
    	Dij1(len, blen, lenpre);
    	Dij2(ti, bti, tipre);
    	vector<int> lenpa, tipa;//存储最终路径
    	int now = e;
    	while(now != b) {
        
    		lenpa.push_back(now);
    		now = lenpre[now];
    	}
    	now = e;
    	while(now != b) {
        
    		tipa.push_back(now);
    		now = tipre[now];
    	}
    	if(lenpa!=tipa) {
        
    		cout << "Time = " << bti[e] << ": " << b;
    		for(int i=tipa.size()-1; i>=0; i--) printf(" => %d", tipa[i]);
    		cout << "\nDistance = " << blen[e] << ": " << b;
    		for(int i=lenpa.size()-1; i>=0; i--) printf(" => %d", lenpa[i]);
    	} else {
        
    		printf("Time = %d; Distance = %d: %d", bti[e], blen[e], b);
    		for(int i=tipa.size()-1; i>=0; i--) printf(" => %d", tipa[i]);
    	}
    }

#### ps：还没看 ####

## 7-11 长城 (25 分) ##

### 题目描述 ###

正如我们所知，中国古代长城的建造是为了抵御外敌入侵。在长城上，建造了许多烽火台。每个烽火台都监视着一个特定的地区范围。一旦某个地区有外敌入侵，值守在对应烽火台上的士兵就会将敌情通报给周围的烽火台，并迅速接力地传递到总部。

现在如图1所示，若水平为南北方向、垂直为海拔高度方向，假设长城就是依次相联的一系列线段，而且在此范围内的任一垂直线与这些线段有且仅有唯一的交点。  
![在这里插入图片描述][bcae1a1216d74d0a994d05c8903f28f0.png]  
进一步地，假设烽火台只能建造在线段的端点处。我们认为烽火台本身是没有高度的，每个烽火台只负责向北方（图1中向左）瞭望，而且一旦有外敌入侵，只要敌人与烽火台之间未被山体遮挡，哨兵就会立即察觉。当然，按照这一军规，对于南侧的敌情各烽火台并不负责任。一旦哨兵发现敌情，他就会立即以狼烟或烽火的形式，向其南方的烽火台传递警报，直到位于最南侧的总部。

以图2中的长城为例，负责守卫的四个烽火台用蓝白圆点示意，最南侧的总部用红色圆点示意。如果红色星形标示的地方出现敌情，将被哨兵们发现并沿红色折线将警报传递到总部。当然，就这个例子而言只需两个烽火台的协作，但其他位置的敌情可能需要更多。

然而反过来，即便这里的4个烽火台全部参与，依然有不能覆盖的（黄色）区域。  
![在这里插入图片描述][ea84cf113e714bd6ba4f725011bf8586.png]  
另外，为避免歧义，我们在这里约定，与某个烽火台的视线刚好相切的区域都认为可以被该烽火台所监视。以图3中的长城为例，若A、B、C、D点均共线，且在D点设置一处烽火台，则A、B、C以及线段BC上的任何一点都在该烽火台的监视范围之内。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_12_color_FFFFFF_t_70_g_se_x_16]  
好了，倘若你是秦始皇的太尉，为不致出现更多孟姜女式的悲剧，如何在保证长城安全的前提下，使消耗的民力（建造的烽火台）最少呢？

输入格式：  
输入在第一行给出一个正整数N（3 ≤ N ≤10  
5  
），即刻画长城边缘的折线顶点（含起点和终点）数。随后N行，每行给出一个顶点的x和y坐标，其间以空格分隔。注意顶点从南到北依次给出，第一个顶点为总部所在位置。坐标为区间\[−10  
9  
,10  
9  
)内的整数，且没有重合点。

输出格式：  
在一行中输出所需建造烽火台（不含总部）的最少数目。

输入样例：

10
    67 32
    48 -49
    32 53
    22 -44
    19 22
    11 40
    10 -65
    -1 -23
    -3 31
    -7 59

输出样例：

### 思路 ###

用了个最粗笨的办法：  
要判断当前点t是否需要设岗，那就判断 t是否 线段t+1->t 与 线段 t->之前的哨岗 之间的凸点，只要有一  
次不是凸点，那t就不需要设岗，反之，说明之前的哨岗都看不到线段t+1->t，t必须设岗。  
这个方法效率较低，因为每次都得跟之前的哨岗做判断，但居然满分。好吧。

### 代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int n;
    int x[100000], y[100000];
    vector<int> res;
    bool ju(int t) {
        
    	//判断t是否 t->t+1->之前的哨岗 这条折线的凸点，如果全是，那t必须设置哨岗
    	int i;
    	for(i=res.size()-1; i>=0; i--) {
        
    		int k = res[i];
    		float k1 = 1.0*(y[t] - y[t+1]) / (x[t] - x[t+1]);
    		float k2 = 1.0*(y[k] - y[t+1]) / (x[k] - x[t+1]);
    		if(k2>=k1)//t+1与之前某哨岗k的连线斜率大于等于t+1与t的连线斜率，说明本次t不是凸点
    			??return false;//无需设岗
    	}
    	return true;//需要设岗
    }
    int main() {
        
    	cin >> n;
    	for(int i=0; i<n; i++)
    		cin >> x[i] >> y[i];
    	res.push_back(0);//0是哨岗
    	int cnt = 0;
    	for(int i=1; i<n-1; i++) {
        
    		//判断当前点与下一个点的连线斜率k2，当前点与上一个岗的连线斜率k1，谁大
    		if(ju(i)) {
         //判断当前点是否需要作为哨岗
    			cnt++;
    			res.push_back(i);
    		}
    	}
    	cout << cnt;
    }

#### ps：还没看 ####

[C_reverse]: https://blog.csdn.net/YMWM_/article/details/115468297
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_11_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/c52767c9668a43f683f9fbe299d558cd.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAR0NUVFRUVFQ=,size_11,color_FFFFFF,t_70,g_se,x_16
[f8d119e393e94f1482ce8ae8d754cad4.png]: https://img-blog.csdnimg.cn/f8d119e393e94f1482ce8ae8d754cad4.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_11_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/51c0c0a1d6bc4ca692c59208e7def5a8.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAR0NUVFRUVFQ=,size_11,color_FFFFFF,t_70,g_se,x_16
[Link 1]: https://blog.csdn.net/qq_43280520/article/details/86619122
[0e9d60df778943438fd9dad87911f36d.png]: https://img-blog.csdnimg.cn/0e9d60df778943438fd9dad87911f36d.png
[c479d6e7ff744849a164f7c5bf710a31.png]: https://img-blog.csdnimg.cn/c479d6e7ff744849a164f7c5bf710a31.png
[bcae1a1216d74d0a994d05c8903f28f0.png]: https://img-blog.csdnimg.cn/bcae1a1216d74d0a994d05c8903f28f0.png
[ea84cf113e714bd6ba4f725011bf8586.png]: https://img-blog.csdnimg.cn/ea84cf113e714bd6ba4f725011bf8586.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_12_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/fbf9dd2934dc4848b8290950b2f0afe2.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAR0NUVFRUVFQ=,size_12,color_FFFFFF,t_70,g_se,x_16