考场上手捏数据的小寄巧

发布时间 2023-12-31 21:43:11作者: Piggy424008

前言

大家都打过 CF,而对于 CF 特殊的赛制,大家也有所耳闻。其中最激动人心的环节也就是 Hack 环节了。其实赛时捏数据,也无非就是对着自己的代码定向爆破罢了。

  • 多捏边界条件,例如询问总是询问修改的边界,再或者题目中某操作可能的特殊性质。
  • 多捏特殊的图,有的图因为其特殊的性质,对复杂度检验很有帮助。例如,点分治写没写对可以用一条长链来卡,如果每次选择的并非重心,很可能会卡成 \(O(n^2)\)
  • 枚举所有情况的全排列,有些题的所有情况可以归类为几个小情况,对这几个小情况分别造一组数据以期望卡掉自己的做法。
  • 对使用的算法爆破,部分算法的正确性可能依赖于数据随机或数据有特殊性质。考虑这样的情况,然后造特殊数据并观察代码的时间是否爆炸。
  • 卡掉珂朵莉树目前似乎是共识。事实上,只要每个点颜色相同,珂朵莉树就会跑的飞慢。
  • 面对自己的 hash 使劲卡。在 OI 赛制下虽然不用担心随机数造成的影响,但是考虑您的哈希函数写的是否过弱。蒟蒻 vpNOI2022 时因为这个挂了 32pts。(注:可以双哈希)
  • 多造一些权值较大的数据,期望自己的程序爆 int 甚至 long long。
  • 对于时间复杂度为玄学的代码,思考此程序在什么情况下可能跑的最慢,然后捏一组这样的数据即可。
  • 没有思路的时候,可以写个 gen 一直 gen 小数据,拍个几万组。

感觉捏数据这件事情很玄学捏