蒟蒻的sb对拍方法
今天就 CCF Online測試 了， 于是花了點時間復習下對拍。
對拍的目的：確保程序的正確性。
適用場景： 暴力容易寫， 高效算法難調。
例子：
給定 (n) 個數(a_1 dots a_n)， (m) 次詢問給定 (x、y (保證 x leq y))， 求 (sum_{i=x}^y a_i)。
數據范圍輸入輸出格式什么雜七雜八的先不管。
重要的是， 已經寫出了比較牛逼的高分程序， 但是很慌，覺得很不穩， 就想人工測試下程序的正確性（不是靜態查錯法）。
如此， 就需要人造些（比較強的）測試數據。
一組測試數據要有輸入和正確輸出， 輸入自然是用輸入數據生成器來造， 輸出就要寫似乎絕對正確的程序跑出來。
這是“對拍”中最為核心的程序。
由于我將對拍所用到的程序都放在了一個文件夾里， 所以下面的運行才這么簡單qwq（沒寫路徑）
#include<bits/stdc++.h>
using namespace std;
int main()
{
//xx.exe 是 xx.cpp 編譯出來的可執行程序
//rand 是輸入數據生成器， 生成的輸入數據保存在 test.in 里
//sol 是不穩程序， 輸出數據保存在 solans.out 里
//bf 是可能很穩的暴力程序， 輸出數據保存在 bfans.out 里
for(int i=1; i<=100; ++i) {
system("rand.exe");
double st = time(0);
system("sol.exe");
double ed = time(0);
system("bf.exe");
if(system("fc solans.out bfans.out")) {
cout << "WA
";
return 0;
}
cout << "AC! timeused: " << ed-st << '
';
}
return 0;
}
給出此題的輸入數據生成器和暴力。（實際上， 這倆加起來似乎才算數據生成器）。
//輸入數據生成器
//rand.cpp
#include<bits/stdc++.h>
using namespace std;
int rd(int n) { // 1 ~ n
return rand() % n + 1;
}
int main()
{
freopen("test.in","w",stdout);
srand((unsigned)time(0));
int n = rd(1000);
cout << n << '
';
for(int i=1; i<=n; ++i) {
int a = rd(1000);
cout << a << ' ';
}
cout << '
';
int m = rd(1000);
cout << m << '
';
for(int i=1; i<=m; ++i) {
int x = rd(n), y = rd(n);
if(x>y) swap(x,y);
cout << x << ' ' << y << '
';
}
fclose(stdin);
fclose(stdout);
return 0;
}
//似乎絕對正確的暴力
//bf.cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int n, a[maxn];
int main()
{
freopen("test.in","r",stdin);
freopen("bfans.out","w",stdout);
cin >> n;
for(int i=1; i<=n; ++i) {
scanf("%d", &a[i]);
}
int m; cin >> m; while(m--) {
int x, y; scanf("%d%d", &x,&y);
int ans = 0;
for(int i=x; i<=y; ++i) ans += a[i];
cout << ans << '
';
}
fclose(stdin);
fclose(stdout);
return 0;
}
以下是神奇的被測程序
//不穩的被測程序
//col.cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int n, a[maxn];
int main()
{
freopen("test.in","r",stdin);
freopen("solans.out","w",stdout);
cin >> n;
for(int i=1; i<=n; ++i) {
scanf("%d", &a[i]);
a[i] += a[i-1];
}
int m; cin >> m; while(m--) {
int x, y; scanf("%d%d", &x,&y);
cout << a[y] - a[x-1] << '
';
}
fclose(stdin);
fclose(stdout);
return 0;
}
文件位置展示
對拍效果展示
最后的總結
在本文中， 多次強調了 可能很穩的暴力程序一詞， 這里再次強調。
there有各種隨機數據的生成模板以及Windows下的對拍程序， 十分值得參考
總結
