蓝桥杯第十六讲--疑难杂题（二）

2022-09-03 173

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 蓝桥杯第十六讲--疑难杂题

距离

题目要求

题目描述：

输入格式：

输出格式：

共 m 行，对于每次询问，输出一行询问结果。

数据范围：

输入样例1：

输出样例1：

100
100

输入样例2：

输出样例2：

10
25

思路分析

Tarjan-离线求LCA

在线做法：读一个询问，处理一个，输出一个

离线做法：读完全部询问，再全部处理完，再全部输出

在深度优先遍历时，将所有点分成三大类

2 号点：代表已经访问并结束回溯

1 号点：代表正在访问

0 号点：代表还没有访问过

其中所有 2 号点和正在搜索的 1 号点路径中已经通过并查集合并成一个集合

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 10010, M = N * 2;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int p[N];
int res[M * 2];
int st[N];
vector<PII> query[N];   // first存查询的另外一个点，second存查询编号
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dist[j] = dist[u] + w[i];
        dfs(j, u);
    }
}
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void tarjan(int u)
{
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            tarjan(j);
            p[j] = u;
        }
    }
    for (auto item : query[u])
    {
        int y = item.first, id = item.second;
        if (st[y] == 2)
        {
            int anc = find(y);
            res[id] = dist[u] + dist[y] - dist[anc] * 2;
        }
    }
    st[u] = 2;
}
int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a != b)
        {
            query[a].push_back({b, i});
            query[b].push_back({a, i});
        }
    }
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    dfs(1, -1);
    tarjan(1);
    for (int i = 0; i < m; i ++ ) printf("%d\n", res[i]);
    return 0;
}

模拟散列表

题目要求

题目描述：

输入格式：

输出格式：

数据范围：

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

思路分析

板子题，需要对代码关键部分进行背诵，详细的代码逻辑解释见博客：哈希表

代码

#include <cstring>
#include <iostream>
using namespace std;
const int N = 200003, null = 0x3f3f3f3f;
int h[N];
int find(int x)
{
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x)
    {
        t ++ ;
        if (t == N) t = 0;
    }
    return t;
}
int main()
{
    memset(h, 0x3f, sizeof h);
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}