真题集P91---2018年计专真题

三(2)自由树直径

思路

1、吉大出的题目，没规定是否是有权图，以及是否是有向图，所以这里默认，权值是1的无向图。

1、如果权值都一样，用邻接表存储，如果权值不同，换成邻接矩阵存储。
2、无向图和有向图，在bfs都一样，但是存储邻接表，邻接矩阵时候，无向图要正反存两次，但是有向图只需要存一次。

2、思路：
<1>我们从任意一个点出发，bfs，找到离出发点最远的节点p1(最后一个出队列的点一定满足)。
<2>我们再从p1出发，找距离它最远的点p2(也同样是最后一个出队列的)
<3>p1和p2之间的距离就是答案

代码

因为我们在bfs的时候，也要兼顾维护距离出发点的距离，所以用结构体存储，方便书写代码。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
struct point {//需要同时维护dis不如直接用结构体非常好理解
	int num;
	int len;
};
point bfs(vector<vector<int>> edge, int p) {//参数：图、起点
	//初始化
	bool visit[1000];
	point distant[1000];
	int n = edge.size();
	for (int i = 0; i < n; i++) {
		visit[i] = false;
		distant[i].len = 0;
		distant[i].num = 0;
	}
	//准备BFS
	visit[p] = true;
	queue<point> help;
	help.push({ p,0 });
	point ans;//标记出最后一个出队列的节点
	//开始BFS
	while (!help.empty()) {
		point tmp = help.front();
		help.pop();
		ans = tmp;
		for (int e : edge[tmp.num]) {
			if (!visit[e]) {
				visit[e] = true;
				help.push({ e,tmp.len + 1 });
			}
		}
	}
	return ans;//每次要BFS具体最远的节点，就是最后出队列的节点，所以标记一下
}
void function_three() {
	vector<vector<int>> edge;
	int n = 0, m = 0;
	cin >> n >> m;
	edge.resize(n);
	for (int i = 0; i < m; i++) {
		int a = 0, b = 0;
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	//开始算法
	point p1 = bfs(edge, 0);
	point ans = bfs(edge, p1.num);
	cout << ans.len;

	return;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

四

思路

这种题很简单
1、一共100钱，公鸡(x)最多20，所以最多枚举到20即可，不要枚举多了！！！！
2、一共100钱，母鸡(y)最多33，所以最多枚举到33即可，不要枚举多了！！！！
3、z=100-x-y就是小鸡个数，但一定要保证，能整除(三只1块钱，所以必须是3的倍数)！！！！！！！
4、最后总钱数要等与100.

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
void function_four() {
	int x = 0, y = 0, z = 0;
	for (; x <= 20; x++) {//全买公鸡，最多20只
		for (; y <= 33; y++) {//全买母鸡，最多33只
			z = 100 - x - y;
			if (z % 3 == 0 && 5 * x + 3 * y + z / 3 == 100) {//保证小鸡子个数整除3，且百钱
				cout << x << ' ' << y << ' ' << z;
				return;
			}
		}
	}
	return;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

五

思路

模拟就行

代码

一定注意：写除法的时候，一定得吧分母用大括号括起来，包好了，里面再加以运算

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int getNum(int n) {
	int ans = 1;
	for (int i = 1; i <= n; i++) {
		ans *= i;
	}
	return ans;
}
double function_five(int cur, int n) {
	if (cur == n) {
		return (double)cur / ((cur + 1)*(getNum(cur + 2)));//加好括号!!!1
	}
	return function_five(cur + 1, n)+ (double)cur / ((cur + 1)*(getNum(cur + 2)));//除法分母上加一个大括号包好，里面再运算!!!!!!
} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22