距离
题目要求
题目描述：
输入格式：
输出格式：
共 m 行，对于每次询问，输出一行询问结果。
数据范围：
输入样例1：
2 2 1 2 100 1 2 2 1
输出样例1：
100 100
输入样例2：
3 2 1 2 10 3 1 15 1 2 3 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; }
