ACM比賽常用技巧

本文介紹ACM程序的常用技巧，包括計算程序的運行時間，以及利用隨機生成數據多次對拍。本文介紹的方法均分在Windows下和Linux下。

同時發布在 https://cfhm.github.io/

例題說明

本篇博客均以下面的例題來說明代碼的用法。

題目描述：給出n個數字，找出第一個不小於k的數字，如果不存在輸出-1

輸入：第一行兩個整數n,k，接下來n個整數a[i]， (1 <= n <= 1e3, 1 <= k, a[i] <= 1e9)

計算程序運行時間

寫在程序中的計算時間的方法

#include <bits/stdc++.h> using namespace std; int main() { #ifndef ONLINE_JUDGE long _begin_time = clock(); #endif int n, k; scanf("%d%d", &n, &k); vector<int> vec; for (int i = 0; i < n; ++i) { int tmp; scanf("%d", &tmp); vec.push_back(tmp); } sort(vec.begin(), vec.end()); int pos = lower_bound(vec.begin(), vec.end(), k) - vec.begin(); int ans = pos == vec.size() ? -1 : vec[pos]; printf("%d
", ans); #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms
", _end_time - _begin_time); #endif return 0; }

此時的運行腳本如下（windows環境 .bat文件）

@echo off cd C:Users anghDesktopff cpp g++ ff.cpp -o ff -static -std=c++14 -O2 ff <in.txt >out.txt

運行結果如下圖1

[1] 左側panel為輸入，右側為輸出

其中用了檢測ONLINE_JUDGE這個宏的方法，可以保證在提交時不會因為忘記注釋這個而WA一發。

在運行腳本中檢測

代碼如下：

#include <bits/stdc++.h> using namespace std; int main() { int n, k; scanf("%d%d", &n, &k); vector<int> vec; for (int i = 0; i < n; ++i) { int tmp; scanf("%d", &tmp); vec.push_back(tmp); } sort(vec.begin(), vec.end()); int pos = lower_bound(vec.begin(), vec.end(), k) - vec.begin(); int ans = pos == vec.size() ? -1 : vec[pos]; printf("%d
", ans); return 0; }

Windows 10 環境下

運行腳本如下：

@echo off cd C:Users anghDesktopff cpp "replace to your project folder g++ ff.cpp -o ff -static -std=c++14 -O2 "your cpp file set begin = %time% call :time2sec %begin% set t1=%ns% ff <in.txt >out.txt "your executable & input & output file set end = %time% call :time2sec %end% set t2=%ns% set /a tdiff=%t2% - %t1% echo run time = %tdiff% ms :time2sec set tt=%1 set hh=%tt:~0,2% set mm=%tt:~3,2% set ss=%tt:~6,2% set ms=%tt:~9,2% set /a ns=((%hh%*60+%mm%)*60+%ss%)*1000+%ms%

運行結果如下圖：

Linux 環境下

運行腳本如下：

#!/bin/bash g++ ff.cpp -o ff -std=c++11 -static -O2 -w time -p ./ff <in.txt

運行結果如下圖：

其中 real 表示總運行時間，user和sys分別表示cpu在用戶態和核心態的運行時間。

腳本和cpp文件在同一級目錄下。

生成隨機數據並對拍

這是兩個關聯的行為，要不斷的生成數據，分別執行你自己的代碼，以及暴力的對拍程序或者標程，然後對比兩個文件的異同。

本次要被對拍的代碼如下：

#include <bits/stdc++.h> using namespace std; int main() { int n, k; scanf("%d%d", &n, &k); vector<int> vec; for (int i = 0; i < n; ++i) { int tmp; scanf("%d", &tmp); vec.push_back(tmp); } sort(vec.begin(), vec.end()); int pos = lower_bound(vec.begin(), vec.end(), k) - vec.begin(); int ans = pos == vec.size() ? -1 : vec[pos]; printf("%d
", ans); return 0; }

將要執行的標準程序如下：

#include <bits/stdc++.h> using namespace std; int main() { int n, k; scanf("%d%d", &n, &k); vector<int> vec; for (int i = 0; i < n; ++i) { int tmp; scanf("%d", &tmp); vec.push_back(tmp); } int diff = INT_MAX; int ans = -1; for (auto v : vec) { if (v >= k) { if (v - k < diff) { ans = v; diff = v - k; } } } printf("%d
", ans); return 0; }

生成隨機數據的程序如下：

#include <bits/stdc++.h> using namespace std; typedef long long ll; int myrand(int mod) { return ((ll)rand()<<32^(ll)rand()<<16^rand())%mod; } #define random(a, b)((a) + myrand((b) - (a) + 1)) //Integer[a,b] int main(int argc, char *argv[]) { stringstream ss; int seed = time(NULL); if (argc) { ss << argv[1]; ss >> seed; } srand(seed); int n = random(1, 1000); int k = random(1, 1000); assert(1 <= n && n <= 1000); assert(1 <= k && k <= 1000); printf("%d %d
", n, k); for (int i = 0; i < n; i++) { int tmp = random(1, 1000000000); printf("%d%c", tmp, "
"[i == n - 1]); } return 0; }

• assert很重要
• rand函數是從2017年多校的標程扒下來的，解決了普通rand範圍小的問題
• 輸入可以帶一個參數來初始化種子，具體見腳本

Windows下的測試腳本如下：

@echo off cd C:Users anghDesktopff cpp g++ ff.cpp -o ff -std=c++11 -static -O2 g++ rand.cpp -o rand -std=c++11 -static -O2 g++ std.cpp -o std -std=c++11 -static -O2 for /l %%i in (1, 1, 10) do ( rand %random% >in.txt ff <in.txt >out.txt std <in.txt >stdout.txt fc out.txt stdout.txt if errorlevel 1 ( echo WA goto END ) ) echo AC :END

其中，測試正確時結果如下：

用下面這個錯誤的程序對拍：

#include <bits/stdc++.h> using namespace std; int main() { int n, k; scanf("%d%d", &n, &k); vector<int> vec; for (int i = 0; i < n; ++i) { int tmp; scanf("%d", &tmp); vec.push_back(tmp); } int diff = INT_MAX; int ans = -1; for (auto v : vec) { if (v >= k) { if (v - k < diff) { ans = v; // diff = v - k; } } } printf("%d
", ans); return 0; }

結果如下：

Linux下的測試腳本如下：

#!/bin/bash g++ ff.cpp -o ff -std=c++11 -static -O2 -w g++ rand.cpp -o rand -std=c++11 -static -O2 g++ std.cpp -o std -std=c++11 -static -O2 -w while true; do ./rand > in.txt ./ff < in.txt > out.txt ./std < in.txt > stdout.txt if diff stdout.txt out.txt; then printf "AC
" else printf "WA
" exit 0 fi done

正確時會一直輸出AC，直到出現WA，樣例結果如下：