ACM比赛常用技巧

本文介绍ACM程序的常用技巧，包括计算程序的运行时间，以及利用随机生成数据多次对拍。本文介绍的方法均分在Windows下和Linux下。

例题说明

本篇博客均以下面的例题来说明代码的用法。

题目描述：给出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\n", ans);
#ifndef ONLINE_JUDGE
    long _end_time = clock();
    printf("time = %ld ms\n", _end_time - _begin_time);
#endif
	return 0;
}

此时的运行脚本如下（windows环境 .bat文件）

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

运行结果如下图^[1]

其中用了检测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\n", ans);
    return 0;
}

Windows 10 环境下

运行脚本如下：

@echo off
cd C:\Users\tangh\Desktop\ff 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 环境下

运行脚本如下：

1
2
3

#!/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\n", 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\n", 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 <= n && k <= 1000);
    printf("%d %d\n", n, k);
    for (int i = 0; i < n; i++) {
        int tmp = random(1, 1000000000);
        printf("%d%c", tmp, " \n"[i == n - 1]);
    }
    return 0;
}

assert很重要
rand函数是从2017年多校的标程扒下来的，解决了普通rand范围小的问题
输入可以带一个参数来初始化种子，具体见脚本

Windows下的测试脚本如下：

@echo off
cd C:\Users\tangh\Desktop\ff 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\n", 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\n" 
    else 
        printf "WA\n" 
        exit 0 
    fi 
done

正确时会一直输出AC，直到出现WA，样例结果如下：

1.左侧panel为输入，右侧为输出 ↩