publicstaticvoidsolve() { intn= io.nextInt(), m = io.nextInt(); Strings= io.next(), t = io.next(); intans=0; for (inti=0; i < n; i++) { if (s.charAt(i) != t.charAt(i)) { ans |= 2; } if (s.charAt(i) != t.charAt(m - n + i)) { ans |= 1; } } io.println(ans); }
#!/bin/bash make b_plus_tree_printer -j$(nproc) { echo 2 3; echo i 1; echo i 2; echo g my-tree.txt; echo q; } | ./bin/b_plus_tree_printer
在生成文件时可能会报 [b_plus_tree.cpp:356:Draw] WARN - Drawing an empty tree 错误,原因是我们没有实现 b_plus_tree.cpp 中的 IsEmpty 函数。
补充
① 如何使用 upper_bound 和 lower_bound(Java 选手表示踩了很多坑),可以看看 cppreference 的示例代码,尤其注意 lambda 表达式的使用(参数顺序,以及大小的比较)。
② 测试时忽略 iterators 的测试。
③ GetValue 注意特判根节点是否存在,否则可能引发空指针异常(依赖于 BufferPoolManager 的实现)。
Task #2b - B+Tree Deletions
实现
① 删除操作可以分为两种情况,相邻节点重新分配和相邻节点合并。进一步可以划分为操作当前节点的左节点,还是右节点。需要注意的是,我们只有对相同父节点的两个子节点执行上述操作,一个非根节点必定有一个同父的左节点或右节点。(如果不这样限制,实现起来会很麻烦,需要找到最近公共祖先,做键值的替换。)为了能够获取左右节点的页面,我们在从上到下找 key 对应的页面时,可以同时保存左右页面的 page_id。
② 重新分配操作,需要区分左右。如果从右节点取,则需要更新右节点对应父节点中的 key;如果从左节点取,则需要更新当前节点对应父节点中的 key。操作完可以直接返回。
③ 合并操作同理,只不过不是更新,而是删除对应父节点中的 key(递归删除)。注意,如果合并叶子节点,需要同时更新 next_page_id_。(合并之后右侧的页面永远都不会被使用,或许需要对其执行 DeletePage 操作,在 DeletePage 之前需要 Drop/Unpin 页面。有个疑问,DeletePage 之前 Drop 之后,如果有线程 Fetch,那么删除页面的操作就会失败。)
#!/bin/bash make b_plus_tree_insert_test b_plus_tree_sequential_scale_test b_plus_tree_delete_test b_plus_tree_concurrent_test -j$(nproc) ./test/b_plus_tree_insert_test ./test/b_plus_tree_sequential_scale_test ./test/b_plus_tree_delete_test ./test/b_plus_tree_concurrent_test make format make check-lint make check-clang-tidy-p2 make submit-p2
publicstaticvoidsolve() { intn= io.nextInt(), k = io.nextInt(), x = io.nextInt(); if (n < k || x < k - 1) io.println(-1); else io.println((k - 1) * k / 2 + (n - k) * (x == k ? k - 1 : x)); }
publicstaticvoidsolve() { intn= io.nextInt(), m = io.nextInt(); inta=0; for (inti=0; i < n; i++) { a ^= io.nextInt(); } intb=0; for (inti=0; i < m; i++) { b |= io.nextInt(); } intmin= a, max = a; if (n % 2 == 0) { min = a ^ (a & b); } else { max = a | b; } io.println(min + " " + max); }
voidsolve(){ int n; cin >> n; vector<int> c(n); for (int i = 0; i < n; i++) { cin >> c[i]; } int k; cin >> k; for (int i = n - 2; i >= 0; i--) { c[i] = min(c[i], c[i + 1]); } int m = k; for (int i = 0; i < n; i++) { int x = i == 0 ? c[i] : c[i] - c[i - 1]; if (x != 0) m = min(m, k / x); k -= x * m; cout << m << " \n"[i == n - 1]; } }