完犊子，三天后考试，这不捐款？

DallasAutumn · Dec 2, 2020 · 6220281 · 6220281
1 parent 2ab5e17
commit 6220281
Show file tree

Hide file tree

Showing 5 changed files with 137 additions and 16 deletions.
diff --git a/A1090.md b/A1090.md
@@ -0,0 +1,56 @@
+# A1090 Highest Price in Supply Chain
+
+## 1.题意理解
+给出一个一条供应链（一棵树），每转手一次都要提升一个差价（按比例给定），问能得到的最高零售价是多少，以及有几个零售商是这个最高价格。
+
+## 2.思路分析
+其实就是求树的高度。
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+const int N = 100010;
+int n;
+double p, r;
+
+vector<int> child[N];
+
+int maxdepth = -1, cnt = 1;
+void dfs(int root, int depth)
+{
+    if (!child[root].size())
+    {
+        if (depth > maxdepth)
+        {
+            maxdepth = depth;
+            cnt = 1;
+        }
+        else if (depth == maxdepth)
+            cnt++;
+        return;
+    }
+    for (int i = 0; i < child[root].size(); i++)
+        dfs(child[root][i], depth + 1);
+}
+
+int main()
+{
+    int root, c;
+    scanf("%d %lf %lf", &n, &p, &r);
+
+    for (int i = 0; i < n; i++)
+    {
+        scanf("%d", &c);
+        if (c != -1)
+            child[c].push_back(i); // 注意别把父子关系搞反！
+        else
+            root = i; // 供应商为-1，即没有供应商，那么它就是根结点。
+    }
+
+    dfs(root, 1);
+    printf("%.2lf %d\n", p * pow(1.0 + r / 100.0, maxdepth - 1), cnt); // 注意转手次数，以及比率是百分数
+    return 0;
+}
+```
diff --git a/A1119.md b/A1119.md
@@ -32,9 +32,9 @@ void get_in(int preL, int preR, int postL, int postR)
     if(numL == 0)
         flag = false; // 左子树长度为0，此时k==preL + 1，处在左子树根结点位置上，既是左子树根又是右子树根，说明序列不唯一，此时认为左子树不存在。（考虑一种情况即可）
     else
-        get_in(preL + 1, k - 1, postL, postL + numL - 1);
-    in.push_back(pre[preL]);
-    get_in(k, preR, postL + numL, postR - 1);
+        get_in(preL + 1, k - 1, postL, postL + numL - 1); // 左子树不空，处理左子树
+    in.push_back(pre[preL]); // 得到一个中序结点
+    get_in(k, preR, postL + numL, postR - 1); // 再处理右子树
 }
 
 int main()

diff --git a/A1147.md b/A1147.md
@@ -3,6 +3,8 @@
 ## 1. 题目理解
 给出一棵完全二叉树的层序遍历，判断是不是堆，如果是，继续判断是大顶堆还是小顶堆。
 
+（表面考堆，实际考完全二叉树）
+
 ## 2.题目分析
 完全二叉树的层序遍历和其顺序存储是一致的，直接读入即可。判断堆时，可以离线建堆也可以在线判断。笔者采用的是建堆方法。
 

diff --git a/dijkstra+dfs.md b/dijkstra+dfs.md
@@ -7,24 +7,34 @@ void dijkstra(int s)
 {
     fill(d, d + MAXV, INF);
     d[s] = 0;
-    for(int i = 0; i < n; i++){
+
+    for(int i = 0; i < n; i++)
+    {
         int u = -1, MIN = INF;
-        for(int j = 0; j < n; j++){
-            if(!vis[j] && d[j] < MIN){
+        for(int j = 0; j < n; j++)
+        {
+            if(!vis[j] && d[j] < MIN)
+            {
                 u = j;
                 MIN = d[j];
             }
         }
     }
+
     if(u == -1) return;
     vis[u] = true;
-    for(int v = 0; v < n; v++){
-        if(!vis[v] && G[u][v] != INF){
-            if(d[u] + G[u][v] < d[v]){
+
+    for(int v = 0; v < n; v++)
+    {
+        if(!vis[v] && G[u][v] != INF)
+        {
+            if(d[u] + G[u][v] < d[v])
+            {
                 d[v] = d[u] + G[u][v];
                 pre[v].clear();
                 pre[v].push_back(u);
-            }else if(d[u] + G[u][v] == d[v])
+            }
+            else if(d[u] + G[u][v] == d[v])
                 pre[v].push_back(u);
         }
     }
@@ -36,21 +46,29 @@ void dijkstra(int s)
 int optvalue;
 vector<int> pre[MAXV];
 vector<int> path, tempPath;
-void dfs(int v){
-    if(v == st){
+void dfs(int v)
+{
+    if(v == st)
+    {
         tempPath.push_back(v);
         int value = 0;
-        for(int i = tempPath.ize() - 1; i > 0; i--){
+
+        for(int i = tempPath.size() - 1; i > 0; i--)
+        {
             int id = tempPath[i], idNext = tempPath[i - 1];
             value += G[id][idNext];
-        if(value < optvalue){
+        }
+
+        if(value < optvalue)
+        {
             value = optvalue;
             path = tempPath;
         }
+
         tempPath.pop_back();
         return;
-        }
     }
+    
     tempPath.push_back(v);
     for(int i = 0; i < pre[v].size(); i++)
         dfs(pre[v][i]);

diff --git a/tricks.md b/tricks.md
@@ -30,4 +30,49 @@ int is_odd(int num)
 int is_odd(int num)
 {
     return num % 2;
-}
+}
+```
+
+## 3.判断质数
+```cpp
+bool isPrime(int n)
+{
+    if(n <= 2)
+        return false;
+
+    int sqr = (int)sqrt(1.0 * n);
+    for(int i = 0; i <= sqr; i++)
+        if(num % i == 0)
+            return false;
+
+    return true;
+}
+```
+
+## 4.求位数和
+```cpp
+int getDigitSum(int n)
+{
+    int ans = 0;
+    while(n)
+    {
+        ans += (n % 10);
+        n /= 10;
+    }
+    return ans;
+}
+```
+
+## 5.求最大公约数，最小公倍数
+```cpp
+int gcd(int a, int b)
+{
+    return !b ? a : gcd(b, a % b);
+}
+
+int lcm(int a, int b)
+{
+    int d = gcd(a, b);
+    return a / d * b;
+}
+```