updated

DallasAutumn · Mar 1, 2020 · cb6c0c0 · cb6c0c0
1 parent f10bd95
commit cb6c0c0
Show file tree

Hide file tree

Showing 17 changed files with 1,039 additions and 0 deletions.
diff --git a/A1003.md b/A1003.md
@@ -0,0 +1,121 @@
+# A1003 Emergency
+
+## 1.题意理解
+大眼一扫，有city（城市）有roads（道路），需要用图来建模。城市为结点，道路为边（无向边）。
+
+题目中还涉及一个要素，就是每个城市救援队的数量，建模为点权。
+
+给定你所在的位置（起点），发生事故的城市（终点），你需要沿着最短路径一边叫人一边赶路，把尽可能多的队伍带过去。
+
+说人话：找出从起点到终点的**所有最短路径中，点权和最大的那一条**。
+
+题目要求输出两个数字：最短路径条数，最短路径中的最大点权和。
+
+## 2.题目分析
+起点终点都给定了，单源最短路问题，并且要找出完整的路径。
+
+这里使用模板：**Dijkstra + DFS**，dijkstra求最短路，dfs把dijkstra存好的结点前驱关系搜出最短路线。
+
+## 3.参考代码
+```cpp
+#include <iostream>
+#include <cstdio>
+#include <cstdlib>
+#include <vector>
+#include <queue>
+#include <algorithm>
+#include <map>
+#include <utility>
+using namespace std;
+
+const int N = 550;
+const int INF = 0x3f3f3f3f;
+
+int G[N][N];
+int rescue[N], optValue = 0, numPath = 0;
+int dist[N];
+int n, m, c1, c2;
+bool visited[N] = {false};
+vector<int> pre[N], path, tempPath;
+
+void dijkstra(int start)
+{
+    fill(dist, dist + N, INF);
+    dist[start] = 0;
+
+    for (int i = 0; i < n; i++)
+    {
+        int u = -1, MIN = INF;
+        for (int j = 0; j < n; j++)
+            if (!visited[j] && dist[j] < MIN)
+            {
+                u = j;
+                MIN = dist[j];
+            }
+
+        if (u == -1)
+            return;
+
+        visited[u] = true;
+
+        for (int v = 0; v < n; v++)
+            if (!visited[v] && G[u][v] != INF)
+                if (dist[u] + G[u][v] < dist[v])
+                {
+                    dist[v] = dist[u] + G[u][v];
+                    pre[v].clear();
+                    pre[v].push_back(u);
+                }
+                else if (dist[u] + G[u][v] == dist[v])
+                    pre[v].push_back(u);
+    }
+}
+
+//深搜+回溯找最短路径
+void dfs(int v, int start)
+{
+    if (v == start)
+    {
+        numPath++;
+        tempPath.push_back(v);
+        int value = 0;
+        for (int i = 0; i < tempPath.size(); i++)
+            value += rescue[tempPath[i]];
+        if (value > optValue)
+        {
+            optValue = value;
+            path = tempPath;
+        }
+        tempPath.pop_back();
+        return;
+    }
+    tempPath.push_back(v);
+    for (int i = 0; i < pre[v].size(); i++)
+        dfs(pre[v][i], start);
+    tempPath.pop_back();
+}
+
+int main()
+{
+    int u, v, w;
+    fill(G[0], G[0] + N * N, INF);
+    scanf("%d %d %d %d", &n, &m, &c1, &c2);
+    for (int i = 0; i < n; i++)
+        scanf("%d", &rescue[i]);
+    for (int i = 0; i < m; i++)
+    {
+        scanf("%d %d %d", &u, &v, &w);
+        G[u][v] = G[v][u] = w;
+    }
+
+    dijkstra(c1);
+    dfs(c2, c1);
+
+    printf("%d %d\n", numPath, optValue);
+    // system("pause");
+    return 0;
+}
+```
+> 注意点：
+> - 积累通用模板：dijkstra + dfs。由于题目要求输出最短路径条数，于是设置了一个全局变量numPath，在dfs中，每次搜索到叶节点就让numPath++，意思是搜出了一条最短路。注意dfs进入的搜索树中，根结点为终点，叶结点为起点，也就是倒着搜回去的。
+> - 注意对邻接矩阵二维数组初始化的fill写法，以及INF常量的定义。本题中邻接矩阵只存储了距离权重，若有其他权重，需要一并初始化，并根据题意选择初始化为0还是INF。
diff --git a/A1004.md b/A1004.md
@@ -0,0 +1,92 @@
+# A1004 Counting Leaves
+
+## 1.题目解释
+给出一棵树，每行给出一个非叶结点（有孩子的结点，non-leaf node），以及它的所有孩子结点（ID[1],ID[2],...ID[k])，统计**每层**叶子结点的个数。
+
+## 2.分析
+本质上还是树的遍历（搜索），从根结点开始，逐层往下搜索。
+
+## 3.参考代码
+广度优先（层序遍历）：
+```cpp
+#include <cstdio>
+#include <cstdlib>
+#include <vector>
+#include <algorithm>
+#include <queue>
+using namespace std;
+
+const int N = 110;
+int ans[N] = {}, depth[N] = {};
+vector<int> v[N];
+
+void bfs(int start)
+{
+    int now;
+    queue<int> q;
+    q.push(start);
+    while (!q.empty())
+    {
+        now = q.front();
+        q.pop();
+        if (v[now].size() == 0)
+            ans[depth[now]]++;
+        else
+            for (int i = 0; i < v[now].size(); i++)
+            {
+                depth[v[now][i]] = depth[now] + 1;
+                q.push(v[now][i]);
+            }
+    }
+}
+
+int main()
+{
+    int n, m, k, id, c;
+    depth[1] = 1;
+
+    scanf("%d %d", &n, &m);
+    for (int i = 0; i < m; i++)
+    {
+        scanf("%d %d", &id, &k);
+        for (int j = 0; j < k; j++)
+        {
+            scanf("%d", &c);
+            v[id].push_back(c);
+        }
+    }
+
+    int start = 1;
+    bfs(start);
+
+    int maxdepth = depth[max_element(depth, depth + N) - depth];
+
+    printf("%d", ans[1]);
+    for (int i = 2; i <= maxdepth; i++)
+        printf(" %d", ans[i]);
+
+    // system("pause");
+    return 0;
+}
+```
+> 解释：在广度优先搜索每一层的孩子结点的同时，记录它们的深度（记录在depth数组中），如果碰到某个结点没有孩子结点，就将该层叶子结点数目+1。
+
+几个可以积累的小细节：
+- 广搜的队列实现模板，不用多说
+- max_element函数求数组最大值（vector类似）
+
+最后附上一个相应的深搜代码实现供参考：
+```cpp
+void dfs(int index, int depth)
+{
+    if (v[index].size() == 0)
+    {
+        ans[depth]++;
+        maxdepth = max(maxdepth, depth);
+        return;
+    }
+    for (int i = 0; i < v[index].size(); i++)
+        dfs(v[index][i], depth + 1);
+}
+```
+深搜用递归实现，显得很简洁巧妙，散发着柳婼小姐姐的仙气~
diff --git a/A1051.md b/A1051.md
@@ -0,0 +1,58 @@
+# A1051 Pop Sequence
+
+## 1.题意理解
+本题考查经典数据结构问题：出栈序列，即将1~n按顺序压入栈中，问哪些query是合法的出栈序列。
+
+## 2.题目分析
+最简单的方法是直接模拟，先把1~n按顺序进栈，每进栈一个数，都把当前栈顶元素与query当前元素进行比较，只要相等就一直pop（模拟出栈），最后计数出栈元素的个数是否为n即可。
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+const int MAX = 1024;
+int m, n, k;
+
+int main()
+{
+    int num;
+    scanf("%d %d %d", &m, &n, &k);
+    for (int i = 0; i < k; i++)
+    {
+        bool flag = false;
+        vector<int> seq;
+        stack<int> s;
+        for (int j = 0; j < n; j++)
+        {
+            scanf("%d", &num);
+            seq.push_back(num);
+        }
+
+        int cur = 0;
+        for (int j = 1; j <= n; j++)
+        {
+            s.push(j);
+            if (s.size() > m)
+                break;
+            while (!s.empty() && s.top() == seq[cur])
+            {
+                s.pop();
+                cur++;
+            }
+        }
+        if (cur == n)
+            flag = true;
+        if (flag)
+            printf("YES\n");
+        else
+            printf("NO\n");
+    }
+    // system("pause");
+    return 0;
+}
+```
+此处可以积累一个重要结论：
+```出栈序列中，每个元素后面所有比它小的元素组成一个递减序列```
+根据这一性质，结合数学推导，可得到n个元素合法出栈序列计算公式（证明略去）：
+$$f(n)=\frac{C^n_{2n}}{n+1}$$
diff --git a/A1053.md b/A1053.md
@@ -0,0 +1,81 @@
+# A1053 Path of Equal Weight
+
+## 1.题目解释
+树的根节点id固定为0，给出每个非叶结点的所有子结点，给出所有结点的权重，给定一个整数S，要求输出从根到叶遍历的序列，使得这样的序列权重之和等于S。
+
+## 2.分析
+- 树的结构是完全给定的，且孩子结点是用下标表示的，可以用静态存储方法。
+- 我采用的是深搜+回溯的方法，需要用一个堆栈维护已经遍历过的序列，对序列求和看是否等于S即可。
+
+## 3.参考代码
+```cpp
+#include <cstdio>
+#include <cstdlib>
+#include <algorithm>
+#include <vector>
+#include <queue>
+using namespace std;
+
+const int N = 110;
+vector<int> temp;
+priority_queue<vector<int> > ans;
+int n, m, c, k;
+long long s;
+struct node
+{
+    int weight;
+    vector<int> child;
+} Node[N];
+
+void dfs(int root)
+{
+    if (Node[root].child.size() == 0) //leaf node
+    {
+        long long total = 0ll;
+        for (int i = 0; i < temp.size(); i++)
+            total += temp[i];
+        if (total == s)
+            ans.push(temp);
+        return;
+    }
+    else
+    {
+        for (int i = 0; i < Node[root].child.size(); i++)
+        {
+            temp.push_back(Node[Node[root].child[i]].weight);
+            dfs(Node[root].child[i]);
+            temp.pop_back();
+        }
+    }
+}
+
+int main()
+{
+    int id;
+    scanf("%d %d %lld", &n, &m, &s);
+    for (int i = 0; i < n; i++)
+        scanf("%d", &Node[i].weight);
+    for (int i = 0; i < m; i++)
+    {
+        scanf("%d %d", &id, &k);
+        for (int j = 0; j < k; j++)
+        {
+            scanf("%d", &c);
+            Node[id].child.push_back(c);
+        }
+    }
+    temp.push_back(Node[0].weight);
+    dfs(0);
+    while (!ans.empty())
+    {
+        vector<int> cur = ans.top();
+        ans.pop();
+        for (int i = 0; i < cur.size(); i++)
+            printf("%d%s", cur[i], i != cur.size() - 1 ? " " : "\n");
+    }
+    // printf("\n");
+    // system("pause");
+    return 0;
+}
+```
+由于最后要求将满足条件（权值和为S）的序列按字典序递降（原题表述为non-increasing，意思一样）输出，我使用了一个最大堆来逐个输出（当然把所有序列保存起来再排序也是可以的）。