明天模拟怎么办啊好慌

DallasAutumn · Jul 21, 2020 · ad97871 · ad97871
1 parent a76b4d4
commit ad97871
Show file tree

Hide file tree

Showing 4 changed files with 282 additions and 0 deletions.
diff --git a/A1132.md b/A1132.md
@@ -0,0 +1,40 @@
+# A1132
+
+## 1.题意理解
+判断一个整数从中间位数截断后，前半部分能否整除后半部分。
+
+## 2.思路分析
+按照要求实现即可，注意判断分母为0情况。
+
+## 3.参考代码
+```cpp
+#include<bits/stdc++.h>
+using namespace std;
+
+int main()
+{
+    int n;
+    string s;
+
+    scanf("%d", &n);
+    for(int i = 0; i < n; i++)
+    {
+        cin >> s;
+        int l = s.length();
+        string t1 = s.substr(0, l / 2);
+        string t2 = s.substr(l / 2, l / 2);
+
+        if(stoi(t1) * stoi(t2) == 0)
+            printf("No\n");
+        else
+        {
+            if(stoi(s) % (stoi(t1) * stoi(t2)) == 0)
+                printf("Yes\n");
+            else
+                printf("No\n");
+        }
+    }
+
+    return 0;
+}
+```
diff --git a/A1133.md b/A1133.md
@@ -0,0 +1,66 @@
+# A1133 Splitting A Linked List
+
+## 1.题意理解
+将一个链表拆成负数，[0, K]，大于K的三段重新组合。
+
+## 2.思路分析
+先把三个区间的链表节点存储到三个数组里，再重新组合，注意有的区间可能没有结点。
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+const int N = 100100;
+
+struct node
+{
+    int Address, Data, Next;
+} nodes[N];
+vector<node> v1, v2, v3;
+vector<vector<node>> valid;
+
+int main()
+{
+    int s, n, k;
+    int addr;
+
+    scanf("%d%d%d", &s, &n, &k);
+    for(int i = 0; i < n; i++)
+    {
+        scanf("%d", &addr);
+        nodes[addr].Address = addr;
+        scanf("%d%d", &nodes[addr].Data, &nodes[addr].Next);
+    }
+
+    for(int head = s; head != -1; head = nodes[head].Next)
+    {
+        node nd = nodes[head];
+        if(nd.Data < 0)
+            v1.push_back(nd);
+        else if(0 <= nd.Data && nd.Data <= k)
+            v2.push_back(nd);
+        else
+            v3.push_back(nd);
+    }
+
+    if(v1.size()) valid.push_back(v1);
+    if(v2.size()) valid.push_back(v2);
+    if(v3.size()) valid.push_back(v3);
+
+    for(int i = 0; i < valid.size(); i++)
+    {
+        auto vec = valid[i];
+
+        for(int j = 0; j < vec.size() - 1; j++)
+            printf("%05d %d %05d\n", vec[j].Address, vec[j].Data, vec[j + 1].Address);
+
+        if(i != valid.size() - 1)
+            printf("%05d %d %05d\n", vec.back().Address, vec.back().Data, valid[i + 1].front().Address);
+        else
+            printf("%05d %d -1\n", vec.back().Address, vec.back().Data);
+    }
+
+    return 0;
+}
+```
diff --git a/A1134.md b/A1134.md
@@ -0,0 +1,62 @@
+# A1134 Vertex Cover
+
+## 1.题意理解
+给出vertex cover的定义：一个图的vertex的子集，所有边至少和其中一个结点有关。
+
+## 2.思路分析
+hash思想，每读入一个结点，就把它连接的边标记上，最后检查所有边是否都被标记即可
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+const int N = 10010;
+vector<int> adj[N];
+
+int main()
+{
+    int n, m, k, u, v, nv;
+
+    scanf("%d%d", &n, &m);
+    for (int i = 0; i < m; i++)
+    {
+        scanf("%d%d", &u, &v);
+        adj[u].push_back(v);
+        adj[v].push_back(u);
+    }
+
+    scanf("%d", &k);
+    for (int i = 0; i < k; i++)
+    {
+        bool flag = true;
+        vector<int> degree(n);
+        for (int j = 0; j < n; j++)
+            degree[j] = adj[j].size();
+
+        scanf("%d", &nv);
+        for (int j = 0; j < nv; j++)
+        {
+            scanf("%d", &u);
+            degree[u] = 0;
+
+            for (int v : adj[u])
+                if (degree[v])
+                    degree[v]--;
+        }
+
+        for (int it : degree)
+        {
+            if (it)
+            {
+                flag = false;
+                break;
+            }
+        }
+
+        printf("%s\n", flag ? "Yes" : "No");
+    }
+
+    return 0;
+}
+```
diff --git a/A1135.md b/A1135.md
@@ -0,0 +1,114 @@
+# A1134 Is It A Red-Black Tree
+
+## 1.题意理解
+别激动，没超纲，红黑树是啥告诉你了。如果有AVL树的底子，是完全可以kill掉的。
+
+给出了红黑树的五条性质：
+- 每个节点非红即黑
+- 根黑
+- 叶黑
+- 红节点的子结点黑
+- 从一个结点出发到叶结点，所有路径上的黑结点数量相同（这条性质是红黑树以平衡树为基础的一个体现）
+
+## 2.思路分析
+根据这五条性质，设计检验函数即可，需要有一定的递归功底。
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+struct node
+{
+    int data;
+    node *left, *right;
+    node(int x)
+    {
+        data = x;
+        left = right = nullptr;
+    }
+};
+unordered_map<int, int> black;
+
+node *insert(node *root, int x)
+{
+    if (root == nullptr)
+        root = new node(x);
+    else if (x < root->data)
+        root->left = insert(root->left, x);
+    else
+        root->right = insert(root->right, x);
+
+    return root;
+}
+
+bool is_black(node *root)
+{
+    if (root == nullptr)
+        return true;
+    else
+        return black[root->data];
+}
+
+bool check_child(node *root)
+{
+    if (root == nullptr)
+        return true;
+
+    bool flag = true;
+    if (!is_black(root))
+        flag = is_black(root->left) && is_black(root->right);
+
+    return flag && check_child(root->left) && check_child(root->right);
+}
+
+int black_num(node *root) // 类比AVL树的高度
+{
+    if (root == nullptr)
+        return 1; //这里return多少其实都行
+
+    int l = black_num(root->left);
+    int r = black_num(root->right);
+
+    return is_black(root) ? max(l, r) + 1 : max(l, r);
+}
+
+bool check_num(node *root)
+{
+    if (root == nullptr)
+        return true;
+
+    if (black_num(root->left) != black_num(root->right))
+        return false;
+
+    return check_num(root->left) && check_num(root->right);
+}
+
+int main()
+{
+    int k, n, x;
+
+    scanf("%d", &k);
+    for (int i = 0; i < k; i++)
+    {
+        node *root = nullptr;
+        black.clear();
+
+        scanf("%d", &n);
+        for (int j = 0; j < n; j++)
+        {
+            scanf("%d", &x);
+            root = insert(root, abs(x));
+            if (x > 0)
+                black[x] = 1;
+        }
+
+        if (is_black(root) && check_child(root) && check_num(root))
+            printf("Yes\n");
+        else
+            printf("No\n");
+    }
+
+    return 0;
+}
+```