对拍杂谈
0 前言
关于对拍,一句话描述清楚它的重要性:相当于数学中的验算。
我们oi中不能只凭感觉来判断一个程序的正确性,而要靠对拍来确定程序正确性。
当然,对拍过了也不能说明你的程序就一定正确,毕竟数据是你自己造的,暴力也是你自己写的,如果你没有考虑清楚,那么你的对拍其实是白费力气。
1 对拍的结构
对拍之前,我们要先了解一下对拍的结构。
对拍由以下几个程序构成:正解、暴力、随机数据生成器、拍子
正解就是你写的不确定正确性,但是时空复杂度符合题目要求的预备正解
暴力要特殊说明一下,暴力程序可以很慢,但是一定要保证绝对正确(甚至可以指数复杂度)
拍子就是将几个程序放在一起疯狂运行,然后判断你的正解答案和暴力的答案是否相同,从而达到判断正确性的效果。
2 暴力
先说暴力,刚才提到了暴力要绝对正确,因为如果你的暴力不能保证正确,那你的整个拍子就白写了。
我曾经遇到过一种情况,就是写了拍子,然后暴力程序的核心思路和正解相同,只是改了正解的其中一部分地方,也就相当于这个暴力只检查了改动的一部分的正确性,后来拍了半个小时,都没有问题,交上去 50 。
所以不要贪时间复杂度,怎么正确怎么来,当然如果有一个时间复杂度更优的也能保证绝对正确,那么当然是选更优的。
3 随机数据生成器
这个主要是一些板子,以及一些语法问题。
3.1 随机函数
这里为了保证随机数质量,我使用 mt19937
来生成随机数
mt19937
会返回一个无符号整数,范围是 \(0 \sim 2^{32} - 1\)。
mt19937_64
返回一个无符号整形,范围是 \(0 \sim 2^{64} - 1\)。
3.2 在一秒内生成多组数据
我们平常使用随机数据种子一般会设为 time0 ,但这样实际上有些缺点,因为如果你快速运行这个程序,就会发现其在一秒内生成的数据是相同的。
什么,你不信?我们写个程序验证一下。
random.cpp
#include <iostream>
#include <algorithm>
#include <random>using namespace std;int main () {mt19937 rng (time (0));cout << rng () << endl;return 0;
}
ts.cpp
#include <iostream>
#include <algorithm>using namespace std;int main () {double st = clock ();while (true) {system ("./random");double now = clock ();if ((now - st) / 1000 > 0.5) break;}cout << (clock () - st) / 1000 << "ms" << endl;return 0;
}
直接看运行 ts.cpp 的结果
现在信了吧,所以如果我们用 time0 做种子,在高速生成随机数据的时候会出现很多随机数据,试想一秒只能跑一组同样的随机数据,效率太低。
怎么解决,我们动态读入种子,保证每次的种子不同,这样就能够保证随机数据的强度。
random.cpp
#include <iostream>
#include <algorithm>
#include <random>using namespace std;// 生成一个无符号整数 0 ~ 2^32 - 1
mt19937 rng;int main () {int sd;freopen ("seed.txt", "r", stdin);cin >> sd;rng.seed (sd);cout << rng () << endl;freopen ("seed.txt", "w", stdout);cout << (int)rng () << endl;return 0;
}
再次运行 ts.cpp ,看看结果