什么是對拍？

對拍是寫完代碼后，通過再另寫一篇代碼來判斷自己的代碼是否正確，是否能夠實現預期功能。

一般是寫完一篇代碼后，再另寫一篇絕對正確的代碼（但在時間空間復雜度上不一定是最優的），以及一篇隨機生成數據的代碼，然后將隨機生成的數據給到絕對正確的代碼以及需要驗證的代碼。如果兩個代碼跑出來的輸出數據一致，那么就能夠在一定程度上說明這個需要驗證代碼是正確的，而如果跑出來的結果，不一樣，那就說明這個需要驗證的代碼是錯誤的或者說是有漏洞的。接下來我們的任務就是去debug了，有需要的可以回顧我前面寫的有關“調試”的文章。

同時，也因此，我們必須保證我們寫的用來“對拍”的代碼是絕對正確的，如果這個代碼寫的都是錯誤的話，那后面自然也就沒有什么好說的了，一般情況下我們是寫一篇暴力的代碼，也就是不考慮時間復雜度與空間復雜度，只要在小范圍數據內能跑對就行。

【C語言】調試【保姆級教程】 visual stdio 2022 + Dev-c++ + vscode三種編譯器的調試方法_Autumn_goose的博客-CSDN博客

為什么要去對拍？

對拍一般有兩種用途：

一、在一定程度上驗證自己寫的代碼的正確性。一般是用在考場或者oi賽制的比賽上，也就是只能提交一份代碼的時候，那么這個時候保證自己提交的代碼的正確性就尤為重要了。

二、通過找出自己代碼的錯誤數據來尋找代碼中的錯誤。這種常用于平時的做題中，我們做題寫了一篇代碼，結果提交上去卻是錯的，然后又一下子不知道錯在哪里。這個時候我們就可以去查看題解，然后用題解的代碼進行對拍，找到那組（或者好多組）讓你代碼過不了的測試數據，然后針對測試數據的情況來有針對性的分析或快速調試自己的代碼究竟錯在哪里。

如何去對拍？

我們將從下面的三個樣例來講解如何進行對拍。

一、求和公式的對拍。

我現在想要時間復雜度\(O(1)\)的求解\(\sum_{i = 1}^{n}i\)，但是我只會用一個暴力的for循環時間復雜度\(O(n)\)的去計算，然后我腦子靈光一閃，想起了以前還給數學老師的知識，依稀記得求和公式好像是這樣\(\sum_{i = 1}^{n}i = \frac{n \times (n +1)}{2}\)，但是我不太肯定，于是決定寫一個“對拍”程序試一試。

1、于是我們先寫下求和公式的代碼，并且命名為 test.cpp ，表示這個是需要驗證的代碼。

#include<bits/stdc++.h> using namespace std;int main() {int n; cin >> n;cout << n * (n + 1) / 2 << endl;return 0; }

2、接下來再寫下暴力循環的代碼，并且命名為 bf.cpp ，bf是 brute force 也就是“暴力”的英文，表示這份代碼是用暴力求解答案的，并且要保證這篇代碼一定是要正確的。

#include<bits/stdc++.h> using namespace std;int main() {int n; cin >> n;int sum = 0;for (int i = 1; i <= n; i++) {sum += i;}cout << sum << endl;return 0; }

3、接下來再寫一篇生成隨機數據的代碼，并且命名為 data.cpp ，表示是用來生成數據的代碼。

關于這篇生成隨機數據的代碼，將會在文章的最后一部分進行大致的講解。

#include<bits/stdc++.h> using namespace std;int main() {srand(time(0) + (unsigned long long)(new char));int n = rand() % 100 + 1;cout << n << endl;return 0; }

4、然后寫如下的腳本，并且命名為 run.txt ，這個腳本是用來運行并且比較暴力代碼和需要驗證代碼的。寫完后再將其后綴名給改成 run.bat 了。然后關于這個腳本的講解也將放在本篇文章的最后一部分。

@echo offg++ bf.cpp -o bf.exe g++ test.cpp -o test.exe g++ data.cpp -o data.exe:loop data.exe > data.txt test.exe < data.txt > test.txt bf.exe < data.txt > bf.txtfc test.txt bf.txtif not errorlevel 1 goto looppause

?

?5、這里說明三個點。

一、個是上面所寫的三篇代碼和一個腳本都是要放在同一個文件夾下面的。

二、不用管我上面截圖中的后綴名為“.bin””的文件以及后綴名為“.cph”的文件夾，那個是我的 vscode 的插件弄出來的，如果大家沒有下載或使用這個插件的話，是不會出現這些文件的。同時這些文件的有無不會影響“對拍”的正常使用。

三、在運行腳本之前要把上面三篇代碼全部先提前編譯運行一遍，也就是說你的文件夾中要有三篇代碼對應的“.exe”文件。

?6、然后我們在文件夾中運行“run.bat”這個腳本，在 vscode 中如果安裝了 code runner 這個插件的話，可以直接點擊右上角的一個按鈕來運行腳本，如果沒有安裝這個插件（比如雁雁我）或者是使用其他編譯器如 dev-c 或 visual stdio 的話，那么我們就直接在文件夾中運行。

?7、運行了之后，文件夾中會多出來幾個“.txt”文件，也就是分別對應的我們的隨機生成的輸入數據，暴力代碼的輸出數據以及我們需要驗證的代碼的輸出數據。然后腳本運行出來的效果就會是下面這樣子的，在遇到兩份代碼輸出不同之前會一直跑。

?8.然后我們給代碼加點錯誤的東西，看看如果對拍出錯誤的東西的話會是一種什么樣的情況。我們給test.cpp里面的代碼加點料。然后再運行看看效果。

#include<bits/stdc++.h> using namespace std;int main() {int n; cin >> n;if (n <= 10) cout << "qiuyan666";cout << n * (n + 1) / 2 << endl;return 0; }

?9、這個時候我們就可以很直觀的看到，兩份代碼中的差異了，正確的輸出和實際輸出之間的差別，然后我們再在文件夾中打開data.txt這個，我們就能夠看到輸入數據是什么。

---

二、高精度加法\((a+ b)\)的對拍。

原題指路：791. 高精度加法 - AcWing題庫

這里介紹另一種對拍方式，其實也差不多，就是把“run.bat”這個腳本寫成代碼“run.cpp”來運行。

1、首先是我們自己寫高精度代碼，這里用的是y總的vector的板子。

#include<bits/stdc++.h> using namespace std;const int N = 1e5;vector<int> add (vector<int> &A, vector<int> &B) {vector<int> C;if(A.size() < B.size() ) return add(B, A);int t = 0;for (int i = 0; i < A.size(); i++) {t += A[i];if (i < B.size()) t += B[i];C.push_back(t % 10);t /= 10;}if (t) C.push_back(1);return C; }void solve() {string a, b; cin >> a >> b;vector<int> A, B;for (int i = a.size() - 1; i >= 0; i--) {A.push_back(a[i] - '0');}for (int i = b.size() - 1; i >= 0; i--) {B.push_back(b[i] - '0');}auto C = add(A, B);for (int i = C.size() - 1; i >= 0; i--) {cout << C[i];}cout << endl; }int main() {solve();return 0; }

2、然后是暴力的代碼：

#include<bits/stdc++.h> using namespace std;int main() {int a, b;cin >> a >> b;int c = a + b;cout << c << endl;return 0; }

3、然后是生成數據的代碼：

#include<bits/stdc++.h> using namespace std;int main() {srand(time(0) + (unsigned long long)(new char));int a = rand() % 100 + 1;int b = rand() % 100 + 1;cout << a << " " << b << endl;return 0; }

4、最后是運行比較的代碼：

#include<bits/stdc++.h> using namespace std;void solve() {while(1) {system("data.exe > data.txt");system("bf.exe < data.txt > bf.txt");system("test.exe < data.txt > test.txt");if (system("fc test.txt bf.txt")) {cout << "wrong!" << endl;break;}}system("pause"); }int main() {solve();return 0; }

5、最后的運行結果：

6、加了點料之后的運行結果：

?這個可能就對用vscode的人來說友好很多，不用去打開文件夾去運行“run.bat”腳本了，所有的操作都可以在vscode編譯器里面的界面中操作。其實對于其他編譯器整體來說都會方便很多，因為不用把“run”文件的后綴名改來改去。

---

三、dijkstra算法（最短路）的對拍。

原題指路：https://www.acwing.com/problem/content/851/

這里再介紹另一種對拍方式，和前面的也都差不多。區別就在于，在暴力和需要驗證的代碼中就已經完成了從隨機數據的輸入以及從將輸出數據輸出到對應的“.txt”文件中。

1、還是先給出自己寫的正解算法（dijkstra），這里用的仍然是y總大大的板子。

#include<bits/stdc++.h> using namespace std;//樸素dijkstra算法求最短路，適用于，邊權都是正的，稠密圖，復雜度n^2 //一開始 dis[1]=0, dis[其他]=INF //首先遍歷1~n個點， //每次確定一個點到起點的最短路 //剩下的還沒有確定的點中最小的一個點 //基于貪心，每次都找最短的路 //找到之后，就用這個點去更新其他點的最短路 //然后就一直迭代。 //這樣一直迭代n次，就找到每個點的最短路了。const int N = 520; int n, m; int g[N][N]; //鄰接矩陣 int dist[N]; //表示從i號點走到起點的當前的最短路的距離是多少 bool st[N]; //表示每個點的最短路的距離是不是已經確定了int dijkstra() {memset(dist, 0x3f, sizeof(dist));dist[1] = 0;for (int i = 0; i < n; i++) {int t = - 1;for (int j = 1; j <= n; j++) { //在所有最短距離還沒有確定的點中找到最短距離的點(所有st[]=false的點中的最短的那個)if (!st[j] && (t == -1 || dist[t] > dist[j])) { //如果當前這個點沒有遍歷過，或者是這是第一個遍歷或者是這個點的最短路更近。t = j;}}st[t] = true;for (int j = 1; j <= n; j++) {dist[j] = min(dist[j], dist[t] + g[t][j]); //用這個最短路的點去更新其他的點}}if (dist[n] == 0x3f3f3f3f) return -1; //假設不連通的話，就返回-1return dist[n]; //不然的話，就返回最短路的距離 }void solve() {cin >> n >> m;memset(g, 0x3f, sizeof(g)); //初始化鄰接矩陣while (m--) {int a, b, c;cin >> a >> b >> c;g[a][b] = min(g[a][b], c); //處理重邊，只保留長度最短的那條邊}int t = dijkstra();cout << t << endl; }int main() {solve();return 0; }

2、然后再寫出暴力算法(Floyd)。

#include<bits/stdc++.h> using namespace std;//處理多源匯最短路，時間復雜度o(n^3) //直接就是dp思想然后暴力就完事了const int INF = 1e7; const int N = 520; int n, m; int d[N][N];void floyd() {for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}}} }void solve() {cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j) d[i][j] = 0;else d[i][j] = INF;}}while (m--) {int a, b, w;cin >> a >> b >> w;d[a][b] = min(d[a][b], w);}floyd();if (d[1][n] >= INF) cout << -1 << endl;else cout << d[1][n] << endl; }int main() {solve();return 0; }

3、接著是寫生成隨機數據的代碼：

#include<bits/stdc++.h> using namespace std;void solve() {srand(time(0) + (unsigned long long)(new char));int n = rand() % 500 + 1;int m = ( rand() + rand() + rand() +rand() ) % 100000 + 1;cout << n << " " << m << endl;for (int i = 1; i <= m; i++) {int a = rand() % n + 1;int b = rand() % n + 1;int w = rand() % 10000 + 1;cout << a << " " << b << " " << w << endl;} }int main() {freopen("data.in", "w", stdout);solve();return 0; }

4、寫一個運行比較的腳本：

@echo off:loop data.exe test.exe bf.exefc test.out bf.outif not errorlevel 1 goto looppause :end

5、然后在文件夾中運行腳本，最后面對拍出來的結果如下：

?6、加了料以后的運行情況：

---

一些說明（叮囑）

①上面的三個案例其實是對應“對拍”中三種比較常見和經典的應用場景的。第一種是驗證我們的某個猜想是否正確，比如一些需要推公式或者構造或者模擬的題目，我們猜或者推了一個表達式出來，然后再小范圍數據內進行大暴力或者大模擬去對拍表達式。第二種是常見于寫高精度算法。第三種是寫完一些比較長，容易錯的代碼后，再寫一個暴力而簡單的代碼去檢查有沒有錯誤。

②暴力（bf.cpp）代碼一定要完全正確，可以很冗長或者很簡短，可以很暴力，可以不剪枝，不需要考慮時間復雜度空間復雜度。唯一要求就是絕對正確。

③對拍出錯誤后，可以去data.txt中查看這一組讓你代碼錯誤的數據是什么，然后針對這一組數據可以有針對性的分析，自己是不是邊緣數據，特殊數據，數組越界，特判，少考慮情況等等什么地方錯了。然后查看暴力出來的正確答案的輸出在bf.txt中，你的代碼跑出來的結果在test.txt中。

④所有對拍的文件都要存放在一個文件夾下！！！

⑤三份代碼 bf.cpp，test.cpp，data.cpp 都要先運行，或者說在同一個文件夾下要生成對應的 bf.exe，test.exe，data.exe 文件，之后，再去運行腳本 run.bat。不然的話是沒有結果的。（第一種寫法的話可以不用，直接保存就好，因為在腳本中寫了運行.cpp的代碼，也就是 g++ bf.cpp -o bf.exe 以及接下來的兩行代碼）。

⑥三份txt文件?data.txt，bf.txt，test.txt是不需要我們提前在文件夾中創建的，我們運行完代碼（或腳本）之后，會自動在文件夾中創建這三份txt文件，同時將數據放進這三份文件中。

⑦比如對拍發現了錯誤，我們給代碼進行了修改之后，要重新運行一遍修改完后的代碼，不能只是保存，不然的話腳本運行對拍的還是原來的代碼。

⑧對拍不出錯誤并不能保證你的代碼一定是完全正確的，可能大數據（超出暴力代碼的數據范圍）的時候，你的代碼就會出現問題，也可能會出現TLE，MLE等其他情況。

⑨用來寫腳本的語言是 Bash。

---

有關腳本的介紹

我們以第一個版本的腳本進行介紹。

@echo offg++ bf.cpp -o bf.exe g++ test.cpp -o test.exe g++ data.cpp -o data.exe:loop data.exe > data.txt test.exe < data.txt > test.txt bf.exe < data.txt > bf.txtfc test.txt bf.txtif not errorlevel 1 goto looppause

一、@echo off 的作用是關閉回顯，也就是說，如果在腳本中加入了這一行代碼的話，那么運行腳本的時候就不會把每一步操作都顯示出來，對于只查看結果的我們來說更加簡潔。

下面是刪除這一句代碼后運行的結果

二、g++ bf.cpp -o bf.exe表示的就是運行一下bf.cpp這個文件。

三、test.exe < data.txt > test.txt 的意思是，將data.txt中的內容輸入到test.exe中并運行，然后將test.exe的輸出結果返回到test.txt中。

四、fc text.txt bf.txt 表示將 text.txt 和 bf.txt 中的內容進行對比，看看是否一致。

五、loop 是循環，if not errorlevel 1 goto loop 是說，如果沒有出現錯誤（即text.txt和bf.txt中的內容一致）的話，那么就繼續循環。

---

進階腳本

從上面的解釋中其實我們是可以發現的，就是如果對拍不出錯誤的話，那么這個循環就會一直跑下去，一直循環。那么我們可不可以設定一個循環次數呢。比如只跑一百次就差不多得了，沒必要一直跑下去。

那我們就可以把腳本寫成這樣：

@echo offg++ bf.cpp -o bf.exe g++ test.cpp -o test.exe g++ data.cpp -o data.exeset /a i = 0 set /a T = 100:loop data.exe > data.txt test.exe < data.txt > test.txt bf.exe < data.txt > bf.txtfc test.txt bf.txtecho running on test %i% set /a i += 1 if %i% == %T% goto endif not errorlevel 1 goto loop:end pause

set /a T = 100 這一行代碼大家可以自行設定循環次數，比如我上面設定的就是一百次。

然后下面給出沒跑出問題和跑出問題了的兩種情況。

---

有關生成隨機數據的介紹

srand(time(0) + (unsigned long long)(new char));

這一句話是用來生成隨機數的。如果我們不加這句話，直接用下面的代碼的話

#include<bits/stdc++.h> using namespace std;int main() {int n = rand();cout << n << endl; }

我們每一次運行出來的結果都會是41，這里面就涉及到偽隨機數的知識了，大家可以去自行搜索相關資料，我就不再此贅述，大家只要記住加了上面的那一行代碼后，出來的隨機數會比較均勻。（當然還有別的高級方法出來的隨機數會更加均勻，我這篇文章的終點在于介紹如何使用對拍，重點不在生成偽隨機數上面，所以就不在這邊寫了）

另外，rand() 的范圍是 0 ~ 32767 之間，取模運算的意思是生成一個某個范圍內的數。比如 a = rand() % 100 的意思就是生成一個 0 ~ 99 之間的數。如果我們要生成 1 ~100 之間的數，那我們就在后面加一個1， a = rand() % 100 + 1。然后如果我們要隨機生成的數字會超出范圍，比如 50000，那我們就生成兩個隨機數，然后再取模，比如 a = ( rand() + rand() ) % 50000 + 1。

---

有關重定向輸入輸出的介紹

freopen("data.in", "r", stdin);freopen("bf.out", "w", stdout);

freopen("文件名", "r", stdin);表示從這個文件中讀取輸入。

freopen("文件名", "r", stdout);表示將輸出放到這個文件中。

---

$$\color{blue}{絕}\color{yellow}{域}\color{red}{殊}\color{purple}{方}\color{green}{畫}\color{gold}{秋}\color{cyan}{雁}\color{lavender}{，}\color{magenta}{笑}\color{orangered}{看}\color{springgreen}{春}\color{gray}{風}\color{aquamarine}{閱}\color{violet}{千}\color{greenyellow}{帆}\color{thistle}{。}$$

如果大家文章中存在疑問或者解釋不清楚額地方，可以在下方評論區中提問。如果我的文章中出現了什么錯誤，也煩請各位大佬指出，我馬上修改。謝謝各位！

總結

以上是生活随笔為你收集整理的【C语言】对拍【保姆级教程】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。