考场上手捏数据的小寄巧

Piggy343288 · 2023-05-31 15:02:05 · 个人记录

前言

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

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

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