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

AtCoder Beginner Contest 317

Potions

二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void solve() {
    int n = io.nextInt(), h = io.nextInt(), x = io.nextInt();
    int[] p = new int[n];
    for (int i = 0; i < n; i++) {
        p[i] = io.nextInt();
    }
    x = x - h;

    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (p[mid] < x) lo = mid + 1;
        else hi = mid - 1;
    }
    io.println(lo + 1);
}

MissingNo.

求和公式。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void solve() {
    int n = io.nextInt();
    int sum = 0;
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        int a = io.nextInt();
        sum += a;
        min = Math.min(min, a);
        max = Math.max(max, a);
    }
    io.println((min + max) * (max - min + 1) / 2 - sum);
}

Remembering the Days

暴力 DFS。

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
private static int ans = Integer.MIN_VALUE;

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();

    List<int[]>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < m; i++) {
        int u = io.nextInt() - 1, v = io.nextInt() - 1, w = io.nextInt();
        g[u].add(new int[]{v, w});
        g[v].add(new int[]{u, w});
    }

    boolean[] vis = new boolean[n];
    for (int i = 0; i < n; i++) {
        dfs(i, 0, g, vis);
    }
    io.println(ans);
}

private static void dfs(int x, int dis, List<int[]>[] g, boolean[] vis) {
    vis[x] = true;
    ans = Math.max(ans, dis);
    for (int[] t : g[x]) {
        int y = t[0], w = t[1];
        if (!vis[y]) {
            dfs(y, dis + w, g, vis);
        }
    }
    vis[x] = false;
}

President

01 背包，比赛时转移方程弄错了一个细节，本来以为和答案是等价的，赛后改下就过了。

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 n = io.nextInt();
    int sum = 0;
    int[] x = new int[n];
    int[] y = new int[n];
    int[] z = new int[n];
    for (int i = 0; i < n; i++) {
        x[i] = io.nextInt();
        y[i] = io.nextInt();
        z[i] = io.nextInt();
        sum += z[i];
    }

    long[] dp = new long[sum + 1];
    Arrays.fill(dp, Long.MAX_VALUE);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = sum; j >= z[i]; j--) {
            if (dp[j - z[i]] == Long.MAX_VALUE) continue;
            dp[j] = Math.min(dp[j], dp[j - z[i]] + Math.max(0, (y[i] - x[i] + 1) / 2));
        }
    }

    long ans = Long.MAX_VALUE;
    for (int i = (sum + 1) / 2; i <= sum; i++) {
        ans = Math.min(ans, dp[i]);
    }
    io.println(ans);
}

Avoid Eye Contact

模拟题，比赛时想复杂了，直接模拟就好。

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
54
55
56
57
58
59
60
public static void solve() {
    int h = io.nextInt(), w = io.nextInt();
    String[] a = new String[h];
    for (int i = 0; i < h; i++) {
        a[i] = io.next();
    }
    int s = -1, g = -1;
    boolean[][] mark = new boolean[h][w];
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            char c = a[i].charAt(j);
            if (c == 'S') {
                s = i * w + j;
            } else if (c == 'G') {
                g = i * w + j;
            } else if (c == '#') {
                mark[i][j] = true;
            } else if (c == '^') {
                mark[i][j] = true;
                for (int k = i - 1; k >= 0 && a[k].charAt(j) == '.'; k--) {
                    mark[k][j] = true;
                }
            } else if (c == 'v') {
                mark[i][j] = true;
                for (int k = i + 1; k < h && a[k].charAt(j) == '.'; k++) {
                    mark[k][j] = true;
                }
            } else if (c == '<') {
                mark[i][j] = true;
                for (int k = j - 1; k >= 0 && a[i].charAt(k) == '.'; k--) {
                    mark[i][k] = true;
                }
            } else if (c == '>') {
                mark[i][j] = true;
                for (int k = j + 1; k < w && a[i].charAt(k) == '.'; k++) {
                    mark[i][k] = true;
                }
            }
        }
    }
    int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    int[] dis = new int[h * w];
    Arrays.fill(dis, -1);
    dis[s] = 0;
    Queue<Integer> q = new LinkedList<>();
    q.offer(s);
    while (!q.isEmpty()) {
        int z = q.poll();
        int x = z / w, y = z % w;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w || mark[nx][ny]) continue;
            int nz = nx * w + ny;
            if (dis[nz] != -1) continue;
            dis[nz] = dis[z] + 1;
            q.offer(nz);
        }
    }
    io.println(dis[g]);
}
发表更新算法 / Codeforces7 分钟读完 (大约1103个字)

Codeforces Round 894 (Div. 3)

Gift Carpet

从左到右每列贪心取即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void solve() {
    int m = io.nextInt(), n = io.nextInt();
    String[] g = new String[m];
    for (int i = 0; i < m; i++) {
        g[i] = io.next();
    }
    int idx = 0;
    String s = "vika";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[j].charAt(i) == s.charAt(idx)) {
                idx++;
                break;
            }
        }
        if (idx == s.length()) {
            io.println("YES");
            return;
        }
    }
    io.println("NO");
}

Sequence Game

构造题。当 \(b_{i-1}>b_{i}\) 时，在两个数中间添加一个 \(1\) 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void solve() {
    int n = io.nextInt();
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt();
    }
    List<Integer> ans = new ArrayList<>();
    ans.add(b[0]);
    for (int i = 1; i < n; i++) {
        if (b[i] < b[i - 1]) ans.add(1);
        ans.add(b[i]);
    }
    io.println(ans.size());
    for (int x : ans) io.print(x + " ");
    io.println();
}

Flower City Fence

阅读理解。题目中的“对角线对称”这个概念根本不用管，就是不断对区间做加法，然后判断是否和原数组相等，可以使用差分 + 前缀和解决。看完题解，发现其实也可以 \(O(1)\) 空间解决，因为数组是非递增的，按顺序遍历就行，具体见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    for (int i = 0, j = n; i < n; i++) {
        for (; j > 0 && a[j - 1] <= i; j--) ;
        if (a[i] != j) {
            io.println("NO");
            return;
        }
    }
    io.println("YES");
}

Ice Cream Balls

题目描述很有问题，其实就是问从一个长度为 \(m\) 的序列中选两个值组成集合，使得不同集合的数目恰好为 \(n\) 的 \(m\) 是多少。可以先二分求 \(x\)，使得 \(C_{x}^{2}\leq n\) 且 \(C_{x+1}^{2}>n\)。然后答案就是 \(x+(n-C_{x}^{2})\)，表示 \([1,n-C_{x}^{2}]\) 范围内的每个数各取两个，以及 \([n-C_{x}^{2}+1,x]\) 范围内的每个数各取一个。PS：读题很容易漏掉恰好两个字。

1
2
3
4
5
6
7
8
9
10
public static void solve() {
    long n = io.nextLong();
    long lo = 2, hi = (long) 1e9 * 2;
    while (lo <= hi) {
        long mid = lo + (hi - lo) / 2;
        if (mid * (mid - 1) / 2 <= n) lo = mid + 1;
        else hi = mid - 1;
    }
    io.println(hi + (n - hi * (hi - 1) / 2));
}

Kolya and Movie Theatre

做这道题时漏掉“开业前一天去过电影院”这个条件，导致想了半天。答案要求最多看 \(m\) 部电影的最大娱乐价值，首先我们可以观察到娱乐值的下降幅度只与最后一次去电影院的日期 \(x\) 有关，即下降幅度为 \(x\cdot d\)。所以我们可以从前往后枚举 \(x\)，并且维护最大长度为 \(m\) 的优先队列，来保证最多看 \(m\) 部电影。需要注意电影的娱乐值可能是负数，而我们只需要在优先队列中存储正数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), d = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = io.nextInt();
    PriorityQueue<Integer> q = new PriorityQueue<>();
    long sum = 0L, ans = 0L;
    for (int i = 0; i < n; i++) {
        if (a[i] <= 0) continue;
        q.offer(a[i]);
        sum += a[i];
        if (q.size() > m) sum -= q.poll();
        ans = Math.max(ans, sum - (long) d * (i + 1));
    }
    io.println(ans);
}

Magic Will Save the World

初见时想到的是二分时间 + 动态规划，赛后优化发现可以直接动态规划做。我是用背包做的，\(dp[i][j]\) 表示前 \(i\) 个怪物使用 \(j\) 点法术值能够击败的怪物总强度最大是多少，然后枚举水法术值计算答案。但是其实可以不用这样，我们只需要知道怪物的子集的所有可能强度是多少，然后枚举所有能够到达的强度即可。（C++ 位图很方便）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void solve() {
    int w = io.nextInt(), f = io.nextInt(), n = io.nextInt();
    int sum = 0;
    int[] s = new int[n];
    for (int i = 0; i < n; i++) {
        s[i] = io.nextInt();
        sum += s[i];
    }
    boolean[] dp = new boolean[sum + 1];
    dp[0] = true;
    for (int i = 0; i < n; i++) {
        for (int j = sum; j >= s[i]; j--) {
            dp[j] = dp[j] || dp[j - s[i]];
        }
    }
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i <= sum; i++) {
        if (!dp[i]) continue;
        ans = Math.min(ans, Math.max((i + w - 1) / w, (sum - i + f - 1) / f));
    }
    io.println(ans);
}

The Great Equalizer

很容易就可以得出结论，设备的输出值是数组的最大值 + 排序后相邻元素的最大差值，但是不知道怎么维护。使用 C++ 的 multiset 很容易写，详细见大佬的代码。

发表更新课程 / 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 任务一也费了一番功夫，因为当时边界条件没弄清楚。

关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×