跳转至

前三题的 Debug 提示

关于 1299~1301，笔者收集了来自 AI 班 2021 级同学的反馈，相关的额外 debug 提示如下。

1299. Closest pair

  • 使用 long long 或者 long double，double 或者 int 精度不够。
  • 如果使用 int 存储输入数据，需要在乘法前转成 long long 进行运算。
  • 由于维护的答案是平方，需要注意在求中间的条的时候，应该使用平方和平方比，或者绝对者和根号下的平方比。如果比较错了，那么条中会有很多额外点：在后面两重循环里，使用超过距离 break 的方法会超时，使用控制点数的方法会答案错误。
  • 递归里开数组时，开为 \(r - l + 1\)；申请 n 次 \(O(n)\) 的数组大小会导致超时。在写算法题的时候，可以大胆使用全局 / static 数组，这在写算法问题的时候并不是一种不好的习惯。特别是，分治需要临时数组时，你可以发现一个全局或者 static 数组能够每部分被完全利用，比每次申请内存反而更整洁。
  • 递归里循环时，需要仔细检查是否只操作了区间内的数，如 \([l, r]\)，而不是 \([1, n]\) 或者 \([1, r]\)。
  • 传值时，注意传的数组（指针）或者 vector 的引用，直接传 vector 会导致复制数据时超时，使用数组时需要注意不要在有其他内容的数组上写入。
  • 如果你手写的快速排序，那么有可能在各种奇怪的边界写挂：没有办法处理排好序的数组（比如选择第一个或者最后一个作为 pivot），没有办法处理全部一样的数组（比如 partition 的时候没有处理好导致返回数组头 / 尾），建议是写 merge sort 或者调用 std::sort。

1300. k-th Smallest Number

  • 随机快速选择比 median of medians 实践下快特别多。
  • 使用 rand() 时，注意 Windows 和 Linux 下存在差距：windows 的 RAND_MAX 是 \(2^{15}-1\)；而 Linux 是 \(2^{31}-1\)。OJ 是 Linux。
    • Windows 下对两个随机数拼接形成大随机数的做法，可能导致 OJ 上出现负数。
    • 可以考虑使用 <random> 库中的随机数生成器（如 mt19937），来保证跨平台可用。
  • 如果你的分数低于排序后输出第 k 大，考虑可能实现成平方了。
  • 如果实现 median of medians 因为实现常数导致超时常数，可以考虑：
    • 减少内存复制与使用：
      • 设置好 basic case （如 \(n \leq 5\)）；
      • 在原地排序五个数（例如 sort(a + i, a + i + 5) 取 a[i + 2]，而不是复制出来）；
      • 本题存在不需要临时数组的写法，且通常是最快的。如果使用了临时数组 / vector，可以尝试复用，或在无需使用时释放掉。
      • vector 可能会比数组慢一点，但是通常没有太大影响。如果实在遇到瓶颈，先考虑减少 push_back 操作，再考虑换成数组。
    • 实在不行可以开读入优化从输入时间偷几十毫秒来通过。
    • 本题时限已经从 1 秒扩大至 1.5 秒，大部分超时 Median of Medians 提交已经满足时限了。
    • 你可以在 1793 测试翻倍时限。

1301. Bubbling bubbles

  • 仔细读题，确定题目到底问的是什么。
  • 实现归并排序时用指针的下标计算贡献，把贡献算到正确的元素上，同时记得每种情况想清楚对答案的贡献是多少。
  • 复制数组时，如果你信息维护在数组里随着元素移动的话，一定要保证移动是正确的。

Todo

美化本页。