蒟蒻的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 << "WAn";
            return 0;
        }
        cout << "AC!  timeused: " << ed-st << 'n';
    }
    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 << 'n';
    for(int i=1; i<=n; ++i) {
        int a = rd(1000);
        cout << a << ' ';
    }
    cout << 'n';
    int m = rd(1000);
    cout << m << 'n';
    for(int i=1; i<=m; ++i) {
        int x = rd(n), y = rd(n);
        if(x>y) swap(x,y);
        cout << x << ' ' << y << 'n';
    }
    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 << 'n';
    }
    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] << 'n';
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

文件位置展示

对拍效果展示

最后的总结

• 在本文中， 多次强调了 可能很稳的暴力程序一词， 这里再次强调。
• there有各种随机数据的生成模板以及Windows下的对拍程序， 十分值得参考