在Ubuntu下配合VSCode的对拍脚本

本文是两年前写的,以下程序和脚本可以在 Ubuntu 直接使用。大家可以学习对拍的实现原理,但由于年代久远,其中的实现方法还有很多改进空间,仅供参考。(潜台词:我写的都是什么垃圾代码……)

对拍

原理

对拍是算法练习中一种很常用、很有用的编程技巧,有很多种实现方法,并且脚本可以自己编写,整一套自己用得顺手的就好了,原理都是差不多的:

对拍模板

我自己习惯在 Ubuntu 下写代码,所以用了一点时间,实现了一套对拍工具,用 VS Code 自带终端就可以轻易使用,但前提是可以使用 g++ 命令。

对拍文件中有以下文件:

基础程序:

random.cpp -> data.in

sol.cpp -> data.out

bf.cpp -> data.ans

check.cpp

控制脚本:

op.sh

mr.sh

test.sh

run.sh

ga.sh

ac.sh

数据文件:

三个data开头的文件

data.in

data.out

data.ans

数据生成器random.cpp

#include <cstdlib>
#include <ctime>
#include <stdio.h>

int random(int n){
    return (long long)rand() * rand() % n;
}

int main(){
    freopen("data.in","w",stdout);
    srand((unsigned)time(0));

    //在这里写程序,利用random()生成各种随机数
    //后面会有各种类型的随机数模板代码
    //往下看

    return 0;
}

暴力程序bf.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const double eps = 1e-5;
const int INF = (int)1e9;
const ll MAXN = 1e5 + 10, MOD = 1e9 + 7;
#define PI acos(-1)



int main(){
    freopen("data.in","r",stdin);
    freopen("data.ans","w",stdout);

    //像平常一样编程即可,不需要在意效率,只需要保证能输出正确结果
    //当然输出的时候也要保证格式的正确性
	//上面两句freopen语句是为了从data.in读入数据
    //并让输出的数据写入data.ans中
    
    return 0;
}

准备上交的程序sol.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const double eps = 1e-5;
const int INF = (int)1e9;
const ll MAXN = 1e5 + 10, MOD = 1e9 + 7;
#define PI acos(-1)



int main(){
    // ios::sync_with_stdio(false);
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);

    //上面两句freopen语句是为了从data.in读入数据
    //并让输出的数据写入data.out中

    //system("pause");
    return 0;
}

接下来是对拍程序,用脚本文件也可以写,但用 C++ 的话,可以获取更精确的时间以及其它信息。

对拍程序check.cpp

#include <cstdio>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(){
    //若需要改变测试次数,修改T的范围即可
    for (int T = 1; T <= 1000; T++){
        //执行random文件
        system("./random");
        //记时并执行准备上交的程序
        double st = clock();
        system("./sol");
        double ed = clock();
        //执行暴力程序
        system("./bf");
        //检验两个程序输出的结果是否相同
        if (system("diff data.out data.ans")){
            printf("Wrong Answer\n");
            return 0;
        }
        else{
            printf("Accepted, Case: %d, Time:%.0lfms.\n", T, ed - st);
        }
    }
    return 0;
}

脚本文件最常用的是op.sh,用于查看输出内容、调试程序。

g++开头的代码是编译对应的文件,并生成可执行文件,非常重要,一定要有可执行文件才能在终端中执行。

另外,.sh脚本程序的运行方式是在终端输入bash xxx.sh

g++ sol.cpp -o sol
./sol < data.in > data.out
cat data.out
echo ""

然后是mr.sh,用于测试写好的数据生成器,在终端运行后直接在终端显示出生成的数据,可以查看是否符合标准。

g++ random.cpp -o random
./random > data.in
cat data.in
echo ""

test.sh这个文件顾名思义就是一个测试文件,专门用来比对题目的样例输入输出,首先在把题目样例输入复制到data.in中,然后把样例输出复制到data.out下,运行即可。

g++ sol.cpp -o sol
./sol < data.in > data.out
diff data.out data.ans
if [[ $? = 0 ]];then
    echo "Accepted"
fi

run.sh这个文件不调用随机生成数据的程序,是单次检查,自己手动输入数据,然后分别运行暴力程序和待上交的程序,比对输出结果。

手动输入的方式是,打开data.in,然后按照格式输入,或者直接复制样例过来,如何运行run.sh即可,若输出结果没问题,则会显示Accepted,很爽,否则显示正确的和错误的输出对比。

这个程序如果不熟悉的话,可能会和上一个test.sh脚本混淆,其实区别在于test.sh中,我已经知道了输入和正确的输出,但run.sh我只有输入,并不知道正确的输出。

这个脚本可以配合mr.sh使用。

g++ sol.cpp -o sol
g++ bf.cpp -o bf
./bf < data.in > data.ans
./sol < data.in > data.out
diff data.out data.ans
if [[ $? = 0 ]];then
    echo "Accepted"
fi

ga.sh脚本只运行暴力程序,得到正确的结果。

这个脚本也可以配合mr.sh使用。

g++ bf.cpp -o bf
./bf < data.in > data.ans
cat data.ans
echo ""

ac.sh文件是完整的对拍脚本,通过调用check.cpp,所有文件都按照要求执行。

g++ sol.cpp -o sol
g++ bf.cpp -o bf
g++ random.cpp -o random
g++ check.cpp -o check
./check

最后是三个data文件

data.in是输入算法程序的输入,也就是随机数据生成程序的输出。

data.out是待上交文件的输出。

data.ans是暴力程序的输出。

对比是对比data.outdata.ans的内容。

使用方法

尽管在上面已经提到了部分文件的用法,但这里还是来一个小小的总结吧。

首先在sol.cpp中写好自己的算法程序。

如果只是想看程序的输出,或者在中间输出某些变量,可以调用op.sh,可以将输出显示在终端上,因为这套程序并没有配置调试环境,所以用输出变量的方式 DeBug 是挺好的方法。

如果是测试题目中给出的样例:把输入样例复制到data.in,样例输出复制到data.ans,然后运行test.sh,看结果,样例过不了那就不用往下了。

如果发现有问题,但代码看起来又找不到什么错误,就在bf.cpp中写一个保证正确的程序,可以不关心运行效率,接下来可以正式使用对拍。

如果要自己手动输入数据对拍,可以在data.in中输入要程序的输入样例,接着运行run.sh

如果要自动生成数据对拍,则先要设计一个随机数据生成器,注意输出格式也要一致,然后可以运行mr.sh查看生成的数据是否符合要求。确认无误后运行ac.sh,默认生成 1000 组数据,若要修改则在check.cpp中修改$T$的取值范围。

test.shrun.sh的区别在于前者没有调用暴力程序,使用的是用户手动输出的结果来验证,后者使用的正确结果是用暴力程序生成的。另外,若要重新生成一次性的随机数据,可以调用mr.sh

如果只想生成一些保证正确的结果,可以调用ga.sh输入可以手动输入或者生成随机数。

.sh脚本文件中的diff命令有很多选项,diff -w可以忽略空格进行比较,更多用法可以查资料。

其实暴力程序不一定是自己手写的暴力,在练习的时候,可以把别人的AC代码放到bf.cpp里面去。

提交sol.cpp时要将文件输入输出的两条语句注释掉,或者使用自定义宏将其包含,使得语句在 OJ 上不运行。

命名方法

  • sol.cpp意为solution
  • bf.cpp意为brute force
  • random.cpp意为生成随机数
  • check.cpp意为检测程序
  • op.sh意为output
  • mr.sh意为make random,生成随机数
  • test.sh意为刚刚写完程序,测试一下样例
  • run.sh意为写好了暴力程序,对拍一下
  • ga.sh意为get answer
  • ac.sh意为一定会AC的
  • data.in意为输入
  • data.out意为输出
  • data.ans意为answer,也就是这里面放一定是正确的

文件名都可以改,写出来只是为了让逻辑更清楚。

每个脚本的开头都不一样,在终端中使用TAB键可以自动补全。

2赞

Random 对拍有一个极大的问题就是无法生成如树、图等关系型数据以及计算几何的数据,现场赛需要对拍验证的话还是需要着重锻炼对边界条件数据的敏感性。
如果是平时训练需要对拍的话,可以用洛谷家的 CYaRon 做对拍器。
当然用这玩意出数据也是巨方便的。

1赞

CYaRon天下第一!

1赞

活捉水水人一枚

粤 ICP 备 2020080455 号