发表更新课程 / CMU 15-44513 分钟读完 (大约1935个字)

Project #0 - C++ Primer

项目准备

项目地址：Project #0 - C++ Primer。

准备工作：创建项目仓库，学习 Git 分支，复习 C++，阅读谷歌 C++ 风格指南，学习 GDB。

Task #1 - Copy-On-Write Trie

实现

Get 函数

没有什么特别需要注意的，实现比较简单。

实现逻辑：

  • 如果 root_ == nullptr 为真，则返回 nullptr。
  • 沿着 Trie 树遍历，如果节点不存在，则返回 nullptr。
  • 如果目标节点不是 TrieNodeWithValue 类型，则返回 nullptr。
  • 否则，返回目标节点的值。

Put 函数

一开始比较疑惑的点是，智能指针存储的都是 const 修饰的节点，如果要修改就必须克隆。但是沿着树遍历的话，如果需要修改子节点，那么同样也需要让父结点指向克隆后的子节点，然后一直向上到根节点，看上去似乎使用栈比较合理。那么能不能不使用栈呢？

其实通过观察可以发现，从根节点一直到目标节点（表示字符串的节点）都是需要克隆的，如果节点存在的话。那么这样我们就可以在遍历的过程中克隆，只需要维护新克隆节点的非 const 指针就能做到。

本来想加个冗余节点减少判断的代码，但是感觉好像怎么弄都逃不过判断 key.empty() 和 root_ == nullptr。

实现逻辑：

  • 如果 key.empty() 为真：
    • 如果 root_ == nullptr 为真，则使用 value​ 构造 Trie 树并返回。
    • 否则，使用 root_->children_ 和 value 构造 Trie 树并返回。
  • 根据 root_ == nullptr 条件初始化新 Trie 树的 root。
  • 沿着旧 Trie 树克隆新 Trie 树的节点（最后一个字符对应的节点需要特殊处理）：
    • 如果克隆完所有字符，则返回新 Trie 树。
    • 否则，新 Trie 树继续创建旧 Trie 树不包含的节点，然后返回新 Trie 树。

Remove 函数

需要使用栈辅助删除，优化后代码好看多了，不像之前那么复杂（大概）。有以下几点需要注意：

① 节点不包含值需要转换为 TrieNode 类型，也就是说拷贝的时候需要调用 TrieNode::Clone()。

② 如果节点满足 children_.empty() && !is_value_node_ 条件，则需要移除该节点。一个节点的移除，可能会导致该节点的父节点也满足移除条件。移除时，记得 erase 父节点中 map 的 key。

实现逻辑：

  • 如果 root_ == nullptr 为真，则返回 *this。
  • 如果 key.empty() 为真，则调用 root_->TrieNode::Clone() 克隆，并返回新 Trie 树。
  • 沿着旧 Trie 树遍历，并将对应的节点入栈，如果节点不存在，则返回 *this。
  • 将栈顶的元素依次弹出，如果当前节点需要移除，则将其移除。
  • 否则，依次克隆栈中的元素，然后返回新 Trie 树。

补充

C++

因为平时用的 Java，所以有几个使用 C++ 的坑点需要注意一下。

① 使用 at 访问 const map 对象，因为 [] 运算符可能会自动添加键值。

1
2
3
const map<int,int> m;
cout << m[1024]; // 错误，No viable overloaded operator[] for type 'const map<int, int>'
cout << m.at(1024); // 正确

② = 拷贝对象的底层结构，不像 Java 中拷贝的是对象的地址（相当于 C++ 中的指针吧）。

1
2
3
4
5
map<int,int> m;
m[1024] = 1024;
auto n = m;
n[1024] = 2048;
cout << m[1024]; // 输出：1024

③ 在 Java 中只要是对象就可以和 null 比较，而 C++ 中只有指针可以和 nullptr 比较。

GDB

① 使用 GDB 调试经常会看到 Python Exception <class ‘gdb.error’>: There is no member named _M_p，点击此处产生该问题的原因，以及相应的解决方案告诉我下载 libstdc++6-dbgsym，完美解决问题。本来不想管这个问题的，结果任务三需要在调试时打印字符串。

② 之前做 CSAPP 的二进制炸弹实验用过 GDB，可以在此查看该课程提供的 GDB 教程。以及可以阅读：GDB Tutorial: Finding Segmentation Faults。

③ 使用 GDB 调试时，最后会报错 LeakSanitizer has encountered a fatal error，因为 LeakSanitizer 不能在 GDB 下工作。不用去管这个错误，只要在不用 GDB 的情况下测试通过就行。

CMake

项目推荐使用 clang-14 作为编译器，解决方案在此。

Task #2 - Concurrent Key-Value Store

实现

因为 Trie 是写时复制的，所以似乎不需要考虑其他复杂的上锁操作，只需要简单的使用 std::mutex 即可。读操作在获取 root_ 时上锁，获取完即可解锁。写操作同理，并且需要在整个操作内对 write_lock_ 上锁。Put 时记得使用 std::move()，因为值可能是不可复制的。

补充

① 关于线程和锁的知识，推荐阅读 CS110 Lecture 10: Threads and Mutexes。

② C++ 有个复制省略（Copy elision）的优化。

③ 关于 C++ 模板的 FAQ、template 关键字的讨论 和 Dependent names 的定义。（好复杂啊）之所以查这些内容，是因为 CLion 给我生成了不同的表达式：

1
2
3
auto value = root.template Get<T>(key);
root = root.template Put(key, std::move(value));
root = root.Remove(key);

以我现在的理解，模板类型是根据实参推断的，如果无法推断则需要在调用时显示添加 <> 来指定类型。然后何时使用 template 没怎么弄明白。

Task #3 - Debugging

实现

挺简单的，文件 trie_debug_test.cpp 指出在 28 行打断点，但我是在 Put 时打断点调试的，应该差不多吧。

补充

无语的是，在修复上个问题时无意间下载了 gcc-12，导致在 make 时报错：/usr/bin/ld: cannot find -lstdc++: No such file or directory，问题原因以及解决方案在此。

Task #4 - SQL String Functions

实现

文件的路径：./src/include/execution/expressions 和 ./src/planner/plan_func_call.cpp。实现大小写转换比较简单，但是如果使用 std::tolower 或许有一些注意事项。注册函数时，需要保证参数是有效的，即参数只有一个并且是 VARCHAR 类型。

测试结果

就是过不去 TrieDebugger.TestCase，结果发现不是我的问题，而是因为本地的随机数和测试的随机数不同，详情见 Discord 讨论。

修改之后通过！

项目小结

任务一是项目的核心，主要还是把逻辑理清楚，以及注意到 key 为空串的特殊用例。一开始很多东西都不懂，查找资料学习花费了很多时间，还有就是 Debug 任务一也费了一番功夫，因为当时边界条件没弄清楚。

发表更新算法 / Codeforces4 分钟读完 (大约573个字)

Educational Codeforces Round 153 (Rated for Div. 2)

Not a Substring

构造题。如果 \(s\) 中存在连续相同的括号，则可以构造交替出现的括号；如果 \(s\) 是交替出现的括号，那么就构造连续的括号，此时包含的唯一交替的括号就是 \(()\)，特判一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void solve() {
    char[] s = io.next().toCharArray();
    int n = s.length;
    boolean ok = false;
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i - 1]) {
            ok = true;
            break;
        }
    }
    if (new String(s).equals("()")) {
        io.println("NO");
        return;
    }
    io.println("YES");
    if (ok) io.println("()".repeat(n));
    else io.println("(".repeat(n) + ")".repeat(n));
}

Fancy Coins

数学题。假设最终使用 \(x\) 枚价值为 \(1\) 的硬币，\(y\) 枚价值为 \(k\) 的硬币。如果 \(x\) 大于等于 \(k\)，我们总是将其合成为价值为 \(k\) 的硬币，所以可以保证 \(x\) 小于 \(k\)。显然 \(x=m\bmod k\)，\(y=\frac{m}{k}\)。那么需要补充多少花色硬币呢？易知，需要补充 \(\max(0,x-a_{1})\) 个价值为 \(1\) 的花色硬币，和 \(\max (0,y-a_{k}-\max (0,\frac{a_{1}-x}{k}))\) 个价值为 \(k\) 的花色硬币。

1
2
3
4
5
public static void solve() {
    int m = io.nextInt(), k = io.nextInt(), a1 = io.nextInt(), ak = io.nextInt();
    int ans = Math.max(0, m % k - a1) + Math.max(0, m / k - ak - Math.max(0, a1 - m % k) / k);
    io.println(ans);
}

Game on Permutation

一开始的想法是，如果某个元素左边恰好只有一个小于它的元素，那么该位置就是胜位。然而暴力找每个位置左边比它小的元素个数的时间复杂度是 \(O(n^{2})\)，赛时就不知道怎么优化。其实我们可以知道，给定一个序列，胜位是固定不变的。所以可以考虑维护左边的最小元素（表示下一步是否可以下棋）和最小的胜位（如果大于最小胜位，则当前位必输），然后就可以很方便的模拟出答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void solve() {
    int n = io.nextInt();
    int[] p = new int[n];
    int ans = 0, min = n + 1, minWin = n + 1;
    for (int i = 0; i < n; i++) {
        p[i] = io.nextInt();
        if (min < p[i] && p[i] <= minWin) {
            ans++;
            minWin = Math.min(minWin, p[i]);
        }
        min = Math.min(min, p[i]);
    }
    io.println(ans);
}

Balanced String

不会不会。。o(╥﹏╥)o

发表更新算法 / AtCoder9 分钟读完 (大约1297个字)

AtCoder Beginner Contest 315

tcdr

模拟。

Java

1
2
3
4
5
6
7
8
9
public static void solve() {
    String s = io.next();
    var sb = new StringBuilder();
    Set<Character> set = Set.of('a', 'e', 'i', 'o', 'u');
    for (char c : s.toCharArray()) {
        if (!set.contains(c)) sb.append(c);
    }
    io.println(sb.toString());
}

C++

1
2
3
4
5
6
7
8
void solve() {
    string s;
    cin >> s;
    s.erase(remove_if(s.begin(), s.end(), [&](char c) {
        return set{'a', 'e', 'i', 'o', 'u'}.count(c);
    }), s.end());
    cout << s << "\n";
}

The Middle Day

模拟。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void solve() {
    int m = io.nextInt();
    int[] d = new int[m];
    int tot = 0;
    for (int i = 0; i < m; i++) {
        d[i] = io.nextInt();
        tot += d[i];
    }
    int mid = (tot + 1) / 2;
    for (int i = 0; i < m; i++) {
        if (mid <= d[i]) {
            io.println(i + 1 + " " + mid);
            return;
        }
        mid -= d[i];
    }
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
    int m;
    cin >> m;
    int tot = 0;
    vector<int> d(m);
    for (int i = 0; i < m; i++) {
        cin >> d[i];
        tot += d[i];
    }
    int mid = (tot + 1) / 2;
    for (int i = 0; i < m; i++) {
        if (mid <= d[i]) {
            cout << i + 1 << " " << mid << "\n";
            return;
        }
        mid -= d[i];
    }
}

Flavors

模拟。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void solve() {
    int n = io.nextInt();
    List<Integer>[] buckets = new List[n + 1];
    Arrays.setAll(buckets, k -> new ArrayList<>());
    for (int i = 0; i < n; i++) {
        int f = io.nextInt(), s = io.nextInt();
        buckets[f].add(s);
    }
    int ans = 0, max1 = 0, max2 = 0;
    for (var bucket : buckets) {
        if (bucket.isEmpty()) continue;
        Collections.sort(bucket, (a, b) -> b - a);
        int a = bucket.get(0);
        if (a > max1) {
            max2 = max1;
            max1 = a;
        } else if (a > max2) {
            max2 = a;
        }
        if (bucket.size() < 2) continue;
        int b = bucket.get(1);
        ans = Math.max(ans, a + b / 2);
    }
    ans = Math.max(ans, max1 + max2);
    io.println(ans);
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> buckets(n + 1);
    for (int i = 0; i < n; i++) {
        int f, s;
        cin >> f >> s;
        buckets[f].push_back(s);
    }
    int ans = 0, max1 = 0, max2 = 0;
    for (auto &bucket : buckets) {
        if (bucket.empty()) continue;
        nth_element(bucket.begin(), bucket.begin() + 1, bucket.end(), greater());
        if (bucket[0] > max1) {
            max2 = max1;
            max1 = bucket[0];
        } else if (bucket[0] > max2) {
            max2 = bucket[0];
        }
        if (bucket.size() < 2) continue;
        ans = max(ans, bucket[0] + bucket[1] / 2);
    }
    ans = max(ans, max1 + max2);
    cout << ans << "\n";
}

Magical Cookies

算是暴力吧。首先最多执行 \(m+n\) 次操作，然后每次操作将所有行和列遍历，判断是否可以标记。如果不优化，那么遍历的复杂度是 \(O(mn)\)，总时间复杂度就是 \(O(mn(m+n))\)，会超时。可以维护剩余的行数 \(r\) 和剩余的列数 \(c\)，那么如果某行的某颜色的数量等于列数，那么就说明可以标记该行，列同理。这样我们就可以只维护行列中的每个颜色有多少饼干，而不需要维护位置关系，从而将遍历的时间复杂度降为 \(O(26(m+n))\)。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public static void solve() {
    int m = io.nextInt(), n = io.nextInt();
    String[] arr = new String[m];
    for (int i = 0; i < m; i++) {
        arr[i] = io.next();
    }
    int[][] row = new int[m][26];
    int[][] col = new int[n][26];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            row[i][arr[i].charAt(j) - 'a']++;
            col[j][arr[i].charAt(j) - 'a']++;
        }
    }
    int r = m, c = n;
    boolean[] vr = new boolean[m];
    boolean[] vc = new boolean[n];
    for (int k = 0; k < m + n; k++) {
        List<int[]> mr = new ArrayList<>();
        List<int[]> mc = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            if (vr[i]) continue;
            for (int j = 0; j < 26; j++) {
                if (row[i][j] == c && c >= 2) {
                    mr.add(new int[]{i, j});
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (vc[i]) continue;
            for (int j = 0; j < 26; j++) {
                if (col[i][j] == r && r >= 2) {
                    mc.add(new int[]{i, j});
                }
            }
        }
        for (int[] p : mr) {
            r--;
            vr[p[0]] = true;
            for (int i = 0; i < n; i++) {
                col[i][p[1]]--;
            }
        }
        for (int[] p : mc) {
            c--;
            vc[p[0]] = true;
            for (int i = 0; i < m; i++) {
                row[i][p[1]]--;
            }
        }
    }
    io.println(r * c);
}

Prerequisites

首先找到第 \(1\) 本书的所有前置书，然后对所有书进行拓扑排序，将之前找到的前置书按拓扑排序的倒序打印即可。或者直接 DFS。。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public static void solve() {
    int n = io.nextInt();
    int[] indegree = new int[n];
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < n; i++) {
        int c = io.nextInt();
        for (int j = 0; j < c; j++) {
            int q = io.nextInt() - 1;
            g[i].add(q);
            indegree[q]++;
        }
    }

    boolean[] mark = new boolean[n];
    Queue<Integer> q = new LinkedList<>();
    q.offer(0);
    while (!q.isEmpty()) {
        int x = q.poll();
        for (int y : g[x]) {
            if (mark[y]) continue;
            mark[y] = true;
            q.offer(y);
        }
    }

    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            q.offer(i);
        }
    }
    Deque<Integer> ans = new ArrayDeque<>();
    while (!q.isEmpty()) {
        int x = q.poll();
        if (mark[x]) ans.push(x);
        for (int y : g[x]) {
            if (--indegree[y] == 0) {
                q.offer(y);
            }
        }
    }
    while (!ans.isEmpty()) io.print(ans.pop() + 1 + " ");
    io.println();
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void solve() {
    int n;
    cin >> n;

    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        int c;
        cin >> c;
        for (int j = 0; j < c; j++) {
            int q;
            cin >> q;
            q--;
            adj[i].push_back(q);
        }
    }

    vector<bool> mark(n);
    auto dfs = [&](auto self, int x) {
        if (mark[x]) {
            return;
        }
        for (auto y : adj[x]) {
            self(self, y);
        }
        mark[x] = true;
        if (x != 0) {
            std::cout << x + 1 << " ";
        }
    };
    dfs(dfs, 0);
    cout << "\n";
}

Shortcuts

动态规划，调试好久。。如果所有点都选，那么答案最多为 \(10^{9}\)，所以可以确定不选的点不会超过 \(30\)。然后定义状态 \(dp[i][j]\) 表示到达第 \(i\) 个点并且总共跳过 \(j\) 个点的最短距离。如何想到定义该状态呢，因为答案和具体选哪几个点无关，只和最短距离以及跳过多少个点有关，大概是这样吧。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static void solve() {
    int c = 30;
    int n = io.nextInt();
    int[] x = new int[n];
    int[] y = new int[n];
    for (int i = 0; i < n; i++) {
        x[i] = io.nextInt();
        y[i] = io.nextInt();
    }
    double[][] dp = new double[n][c];
    for (int i = 0; i < n; i++) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
    }
    dp[0][0] = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < c; j++) {
            for (int k = i + 1; k < n && k - i - 1 + j < c; k++) {
                int nj = j + k - i - 1;
                dp[k][nj] = Math.min(dp[k][nj], dp[i][j] + Math.sqrt((x[i] - x[k]) * (x[i] - x[k]) + (y[i] - y[k]) * (y[i] - y[k])));
            }
        }
    }
    double ans = Integer.MAX_VALUE;
    for (int i = 0; i < c; i++) {
        ans = Math.min(ans, dp[n - 1][i] + (i == 0 ? 0 : 1 << (i - 1)));
    }
    io.println(ans);
}

关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×