对拍
原理
对拍是算法练习中一种很常用、很有用的编程技巧,有很多种实现方法,并且脚本可以自己编写,整一套自己用得顺手的就好了,原理都是差不多的:
对拍模板
我自己习惯在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++
开头的代码是编译对应的文件,并生成可执行文件,非常重要,一定要有可执行文件才能在终端中执行,即使不用VS Code,用其它的编辑器,也一样要生成,在Window下生成的是.exe
文件。
另外,.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.out
和data.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.sh
和run.sh
的区别在于前者没有调用暴力程序,使用的是用户手动输出的结果来验证,后者使用的正确结果是用暴力程序生成的。另外,若要重新生成一次性的随机数据,可以调用mr.sh
。
如果只想生成一些保证正确的结果,可以调用ga.sh
输入可以手动输入或者生成随机数。
.sh
脚本文件中的diff
命令有很多选项,diff -w
可以忽略空格进行比较,更多用法可以查资料。
其实暴力程序不一定是自己手写的暴力,在练习的时候,可以把别人的AC代码放到bf.cpp
里面去。
命名方法
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
键可以自动补全。
非常感谢!!!
非常感谢awa
虽然我已经开始终端直接 fc 了环境换得频繁之后就懒得配了,越简单越好hhh