适用条件
当你是和我一样水平较弱的选手,完全不会这题的正解,同时考场上其他题该暴力的暴力,该正解的正解都写完了,还有一段时间,准备颓扫雷或者纸牌啥的的时候,就可以尝试乱搞骗分。说不定能利用这点时间多骗一些分,甚至进队。
1.保证复杂度,骗正确性
说白了,就是在不超时的情况下尽可能让答案正确的可能性更大。
最常见的例子就是模拟退火,在达到一个时间之前一直跑。
分两步:
1.想一个正确性不对或者大概是对的但是不会证明的做法。
2.在时限的范围内,尽可能增加其正确性。
例:
首先,想一个正确性不对的做法:
首先,模数差不多不会选一个小的数。
看到这道题,自然想到[链接登录后可见]。这个题有两种可能,一个是用第三大数模大数,一个是用最大数模次大数。
自然想到这题差不多是两个数加起来接近模数或者一个略小于模数一个略大于模数。因为模数不会小,所以这两个数差不多也不会小。
那么选较大的几个数暴力枚举就可以骗分了。
那么选几个数呢,这时候就是第二条了。
这样做的复杂度是 $x^ 3$,$x$ 为你选数的个数。显然,$x$ 越大,正确率越高,但是为了保证不超时,$x$ 可以选择 $300-500$ 左右。
虽然根据[链接登录后可见],$x=6$ 即可通过,但是考场不知道的情况还是我这样比较稳妥,更可能骗到更多分。
首先,想一个正确性不对的做法,根据思维能力有各种正确率不同的方法。不管你只想到[链接登录后可见]还是直接双指针。
然后第二步,尽可能增加其正确性。首先,你可以在数据较小的时候直接跑之前写好的 40 分暴力。其次,你如果想到多种乱搞,可以取最小值。
2.保证正确性,骗复杂度
这个,也就是俗称 $n^ 2$ 过百万的一种可能方法。
分两步:
1.想一个复杂度不对或者大概是对的但是不会证明的做法。
2.在答案正确的范围内,尽可能优化其效率。
例:
首先 $q^ 2$ 暴力模拟很显然,每次增加或者减少一个战士。
然后剪枝优化。
在数据水的情况下,加入一个新的或者减少一个对最终的温度差不多只是微调。变化不会太大。
从上次的答案开始,暴力移动温度找最大值,就可以通过了。
当你写完暴力和骗分的时候,考完心态会很好。因为你写的暴力,所以几乎不会挂,你写的骗分,得分还有可能比期望高,静静地看着大家挂分,自己却得分比期望高,岂不美哉?