今天學長來講了一下對拍,我來整理一下
啥是對拍
首先,對拍是幹啥的呢??
對拍,主要是用于在考試或者比賽時的驗證,可以通過自己針對性的資料找出程式的錯誤之處。可以将你打的程式與寫的暴力程式比較,驗證自己算法或猜想的正确性,也可以在做題時放背景運作,用于檢測代碼是否存在錯誤。
比如你在做一道題,你會寫暴力,也會寫正解,你正解的答案不一定是對的,但是你确定暴力的答案一定是對的,這個時候你就可以打一個對拍程式,用對拍程式驗證你寫的正解的正确性(同理你也可以打兩個暴力驗證一下暴力的正确性)
咋實作對拍
那麼我們需要準備的程式有幾個呢?
- 一定正确的暴力程式(baoli.cpp)
- 等待驗證的“正解”(std.cpp)
- 生成資料的程式(rand.cpp)
- 對拍,檢查的程式(checker.bat)
然後我們運作baoli.cpp,std.cpp,得到兩個exe檔案,再建立一個a.in檔案,作為它們共同的檔案輸入源。準備好這7個檔案後,我們運作checker.bat,即可進行對拍。
代碼是啥
(下面我們以洛谷3378的程式為例)
這裡是傳送門qwq
注:代碼均來自attack,有些注釋來自搜尋
baoli.cpp與std.cpp
這倆東東就需要按題目的要求來編寫了
但我們一定要保證baoli.cpp是答案一定正确的暴力程式,同時std.cpp就是待驗證的程式。有一個要求就是輸入檔案需要相同,這裡使用freopen
檔案名可以由自己決定,但兩個cpp檔案的輸入檔案必須相同
baoli.cpp
//暴力寫法
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N;
int st[MAXN], l, r;
int main() {
freopen("a.in", "r", stdin);
N = read();
l = 1; r = 0;
while(N--) {
int opt = read();
if(opt == 1) {
int x = read();
st[++r] = x;
} else if(opt == 2){
sort(st + l, st + r + 1);
printf("%d\n", st[l]);
} else {
sort(st + l, st + r + 1);
l++;
}
}
return 0;
}
std.cpp
//使用優先隊列
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N;
priority_queue<int, vector<int>, greater<int> >q;
int main() {
freopen("a.in", "r", stdin);
N = read();
int tot = 0;
while(N--) {//O(n)
int opt = read();
if(opt == 1) {
int x = read();
q.push(x);
tot++;
} else if(opt == 2){
if(tot == 0) {
puts("gg");
return 0;
}
printf("%d\n", q.top());
} else {
if(tot == 0) {
puts("gg");
return 0;
}
q.pop();
}
}
return 0;
}
rand.cpp
rand.cpp就是生成資料的程式,生成資料的方法有很多,這裡就不細說了,上代碼
#include<bits/stdc++.h>
#include<ctime>
using namespace std;
int rnd() {
return rand() << 15 | rand();
}
int tot;
int main() {
freopen("a.in", "w", stdout);
srand((unsigned)time(0));
int N = (rand() % 30) + 1;//[1, 30]
cout << N << '\n';
while(N--) {
int opt = rand() % 3 + 1;//[1, 3]
if(opt == 3 && tot == 0) opt = 1;
if(opt == 2 && tot == 0) opt = 1;
cout << opt << ' ';
if(opt == 1) {
int x = rnd();
cout << x << '\n';
tot++;
} else if(opt == 2){
cout << '\n';
} else {
tot--;
cout << '\n';
}
}
return 0;
}
freopen函數中的檔案名可以自己定,但需要與baoli.cpp和std.cpp的檔案輸入名相同(在示例中,fopen函數的檔案名必須為a.in)
checker.bat
其實我們并非隻能用checker.bat,也可以直接編寫cpp檔案,若想了解的去網上搜一下,這裡就不寫了
下面的是.bat檔案的編寫,檔案名因程式而異
baoli.exe > b.out 指的是baoli.exe運作之後生成b.out檔案
同理std.exe > c.out 指的是std.exe運作之後生成c.out檔案
然後是進行對比,看有沒有差别兩檔案的内容有差别就會自動停止
:loop
rand.exe
baoli.exe > b.out
std.exe > c.out
fc b.out c.out
if not errorlevel 1 goto loop
pause
下面看一下運作圖
在運作過程中,如果沒有錯誤,對拍會自動進行,可以放在背景運作,如果出現錯誤,對拍會自動停止,按ctrl+c退出,然後你就可以在資料生成的輸出源中找到使你程式出錯的那一組資料(在示例中即為a.in)
這樣對拍就完成啦!
轉載不必聯系作者,但請聲明出處