GESP-Lv8总结(202406)

Everything_ · 2025-03-10 09:39:45 · 个人记录

GESP C++ 八级 2024 年 06 月

题目链接

错题

( T4 ) 有V个顶点、E条边的图的深度优先搜索遍历时间复杂度为

求时间复杂度，我们就需要先搞清楚源代码是什么？以下为 DFS 模板

void dfs(int now, int fa)
{
    for(int i : e[now])
    {
        if(i == fa) continue;
        dfs(i, now);
    }
}   

显然的，DFS 完之后 每一个节点和每一条边都会枚举一遍，所以时间复杂度为 O(V + E)

( T8 ) 以下函数声明，哪个是符合C++语法的？

void BubbleSort(char a[][], int n);

void BubbleSort(char a[][20], int n);

我一开始一不知道为什么，我甩给编译器编译了一下

[Error] declaration of 'a' as multidimensional array must have bounds for all dimensions except the first

意思就是

[错误]将“a”声明为多维数组必须对除第一个维度之外的所有维度都有边界

原因也就显而易见了

( T9 ) 下面有关C++重载的说法，错误的是

函数重载的规则如下

函数名称必须相同：重载的函数必须拥有相同的名称。

参数列表必须不同：参数的数量、类型或顺序必须有所不同。

返回类型可以不同：即使两个函数的参数列表完全相同，它们的返回类型也可以不同，但这通常不被视为重载。

不能通过返回类型区分重载：不能仅通过返回类型的不同来区分重载函数。

( T6 ) 在 N 个元素的二叉排序树中查找一个元素，最差情况的时间复杂度是 O(\log{N})。\color{red}{False}

这一题的二叉排序树查找问题让我忽略了一个因素，就是 当该元素如果和根相同两子树都要查找，所以最差时间复杂度依旧显而易见了，答案为 O(N)

( T7 ) C++语言中，可以为同一个类定义多个析构函数。 \color{red}{False}

参考博客

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

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

解决方法如下

我们可以从最深的节点往上去寻找，但是这样做并不是最优解，我们很容易就举出反例:

但是如果我们从第二深的 不相同颜色 的节点在计算，就可以弥补这个解。

做的图论的难题还是太少了

#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. 图论题量不够