专栏文章

GESP-Lv8总结(202406)

EEverything_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipyrkts
此快照首次捕获于
2025/12/03 20:09
3 个月前
此快照最后确认于
2025/12/03 20:09
3 个月前
查看原文

GESP C++ 八级 2024 年 06 月

题目链接

错题

( T4 ) 有V个顶点、E条边的图的深度优先搜索遍历时间复杂度为
错误的:O(V)\color{red}{错误的:O(V})
正确的:O(V+E)\color{green}正确的:O(V+E)
求时间复杂度，我们就需要先搞清楚源代码是什么？以下为 DFS 模板
CPP
void dfs(int now, int fa)
{
	for(int i : e[now])
	{
		if(i == fa) continue;
		dfs(i, now);
	}
}
显然的，DFS 完之后 每一个节点和每一条边都会枚举一遍，所以时间复杂度为 O(V+E)O(V + E)
( T8 ) 以下函数声明，哪个是符合C++语法的？
错误的:\color{red}错误的:
CPP
void BubbleSort(char a[][], int n);
正确的:\color{green}正确的:
CPP
void BubbleSort(char a[][20], int n);
我一开始一不知道为什么，我甩给编译器编译了一下
JAVASCRIPT
[Error] declaration of 'a' as multidimensional array must have bounds for all dimensions except the first
意思就是
[错误]将“a”声明为多维数组必须对除第一个维度之外的所有维度都有边界
原因也就显而易见了
( T9 ) 下面有关C++重载的说法，错误的是
根本不会:)\color{red}根本不会:)
函数重载的规则如下
函数名称必须相同：重载的函数必须拥有相同的名称。
参数列表必须不同：参数的数量、类型或顺序必须有所不同。
返回类型可以不同：即使两个函数的参数列表完全相同，它们的返回类型也可以不同，但这通常不被视为重载。
不能通过返回类型区分重载：不能仅通过返回类型的不同来区分重载函数。
( T6 ) 在 NN 个元素的二叉排序树中查找一个元素，最差情况的时间复杂度是 O(log⁡N)O(\log{N})。False\color{red}{False}
这一题的二叉排序树查找问题让我忽略了一个因素，就是 当该元素如果和根相同两子树都要查找，所以最差时间复杂度依旧显而易见了，答案为 O(N)O(N)
( T7 ) C++语言中，可以为同一个类定义多个析构函数。 False\color{red}{False}
根本不会:)×2\color{red}根本不会:) × 2
参考博客

最远点对 普及+/提高\color{52C41A}{普及+/提高}

不会只能看题解QAQ\color{red}{不会只能看题解QAQ}
因为题目说了 它是一棵树，所以我就可以将这一棵树的深度计算出来，既然它是一棵树，那么我们就应该将他当成一棵树来看待，不要在以图的角度来考虑问题。

解决方法如下

我们可以从最深的节点往上去寻找，但是这样做并不是最优解，我们很容易就举出反例: a
但是如果我们从第二深的 不相同颜色 的节点在计算，就可以弥补这个解。
做的图论的难题还是太少了
CPP
#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int maxn = 1e5 + 5, INF = 0x3f3f3f3f;
int n, x, y, deep[maxn], pos1, pos2, ans;
vector <int> e[maxn];
bool a[maxn];
void dfs(int now, int fa)
{
	for(int i : e[now])
	{
		if(i == fa) continue;
		deep[i] = deep[now] + 1;
		dfs(i, now);
	}
}
void doit(int now, int fa, int c, int l)
{
	if(a[now] == c) ans = max(ans, l);
	for(int i : e[now])
	{
		if(i == fa) continue;
		doit(i, now, c, l + 1);
	}
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &x), a[i] = x;
	for(int i = 1; i < n; i++)
	{
		scanf("%d %d", &x, &y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1, 0);
	// pos1 = 0, pos2 = 1;
	for(int i = 1; i <= n; i++)
	{
		if(!a[i])
		{
			if(deep[i] > deep[pos1])
				pos1 = i;
		}
		else
		{
			if(deep[i] > deep[pos2])
				pos2 = i;
		}
	}
	if(pos1) doit(pos1, 0, 1, 0);
	if(pos2) doit(pos2, 0, 0, 0);
	printf("%d", ans);
	return 0;
}

总结

  1. 基本尝试不熟悉，如 DFS 的时间复杂度，函数的定义以及声明。
  2. 排列组合题需要加强，如计算方案，可能性全面性。
  3. 图论题量不够

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...