单链表
题目要求
题目描述：
实现一个单链表，链表初始为空，支持三种操作：
- 向链表头插入一个数；
- 删除第 k 个插入的数后面的数；
- 在第 k个插入的数后插入一个数。
现在要对该链表进行 M次操作，进行完所有操作后，从头到尾输出整个链表。
注意: 题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式：
输出格式：
共一行，将整个链表从头到尾输出。
数据范围：
1≤M≤100000
所有操作保证合法。
输入样例：
10 H 9 I 1 1 D 1 D 0 H 6 I 3 6 I 4 5 I 4 5 I 3 4 D 6
输出样例：
6 4 6 5
思路分析
模板类题目，对插入和删除操作必须做到能够快速打出代码的程度。
代码
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 100010; int head, idx; int e[N], ne[N]; void add_head(int x) { e[idx] = x, ne[idx] = head, head = idx ++; } void remove(int k) { ne[k] = ne[ne[k]]; } void add_k(int k, int x) { e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++; } int main() { head = -1; int m; scanf("%d", &m); while (m -- ) { char op[2]; scanf("%s", op); if (op[0] == 'H') { int x; scanf("%d", &x); add_head(x); } else if (op[0] == 'D') { int k; scanf("%d", &k); if (!k) head = ne[head]; else remove(k - 1); } else { int k, x; scanf("%d%d", &k, &x); add_k(k - 1, x); } } for (int i = head; ~i; i = ne[i]) printf("%d ", e[i]); return 0; }
大臣的旅费
题目要求
题目描述：
输入格式：
输出格式：
输出一个整数，表示大臣 J 最多花费的路费是多少。
数据范围：
输入样例：
5 1 2 2 1 3 1 2 4 5 2 5 4
输出样例：
135
思路分析
结论推导：（感兴趣的可以看看）
🌞🌞🌞综上所述，(2 3 ) 是直径。
代码 （vector存储的dfs）
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 100010; struct Edge { int id, w; }; int n; vector<Edge>v[N]; int dist[N]; void dfs(int u, int father, int distance) { dist[u] = distance; for (auto t : v[u]) if (t.id != father) dfs(t.id, u, dist[u] + t.w); } int main() { scanf("%d", &n); for (int i = 0; i < n - 1; i ++ ) { int p, q, d; scanf("%d%d%d", &p, &q, &d); v[p].push_back({q, d}); v[q].push_back({p, d}); } dfs(1, -1, 0); int u = 1; for (int i = 1; i <= n; i ++ ) if (dist[u] < dist[i]) u = i; dfs(u, -1, 0); for (int i = 1; i <= n; i ++ ) if (dist[u] < dist[i]) u = i; int s = dist[u]; // s 就是树的直径 printf("%lld\n", (1ll + s) * s / 2 + s * 10); return 0; }
代码 (链表存储的dfs)
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 100010; int n; int h[N], e[2 * N], w[2 * N], ne[2 * N], idx; int dist[N]; void add(int p, int q, int d) { e[idx] = q, w[idx] = d, ne[idx] = h[p], h[p] = idx ++; } void dfs(int u, int father, int distance) { dist[u] = distance; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j != father) dfs(j, u, distance + w[i]); } } int main() { memset(h, -1, sizeof h); scanf("%d", &n); for (int i = 0; i < n; i ++ ) { int p, q, d; scanf("%d%d%d", &p, &q, &d); add(p, q, d); add(q, p, d); } int u = 1; dfs(1, -1, 0); for (int i = 1; i <= n; i ++ ) if (dist[u] < dist[i]) u = i; dfs(u, -1, 0); for (int i = 1; i <= n; i ++ ) if (dist[u] < dist[i]) u = i; int s = dist[u]; printf("%lld\n", s * 10 + (1ll + s) * s / 2); return 0; }
代码 (链表存储的bfs)
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int N = 100010; int n; int idx, h[N], e[2 * N], ne[2 * N], w[2 * N]; int dist[N]; queue<int> q; void add(int p, int q, int d) { e[idx] = q, w[idx] = d, ne[idx] = h[p], h[p] = idx ++; } void bfs(int u) { q.push(u); dist[u] = 0; while (q.size()) { auto t = q.front(); q.pop(); for (int i = h[t]; ~i; i = ne[i] ) { int j = e[i]; if (dist[j] != -1) continue; dist[j] = dist[t] + w[i]; q.push(j); } } } int main() { memset(h, -1, sizeof h); memset(dist, -1, sizeof dist); scanf("%d", &n); for (int i = 0; i < n - 1; i ++ ) { int p, q, d; scanf("%d%d%d", &p, &q, &d); add(p, q, d); add(q, p, d); } int u = 1; bfs(u); for (int i = 1; i <= n; i ++ ) if (dist[u] < dist[i]) u = i; memset(dist, -1, sizeof dist); bfs(u); for (int i = 1; i <= n; i ++ ) if (dist[u] < dist[i]) u = i; int s = dist[u]; printf("%lld\n", 10 * s + (1ll + s) * s / 2); return 0; }
