算法竞赛：对拍 | Jiely 的博客

对拍的形式就是就是通过与暴力算法去验证自己的算法的可行性，是否存在边界问题没有考虑，找出 Hack 数据

对拍#

1. 文件结构#

1
duipai/
2
├── gen.cpp
3
├── std.cpp
4
├── solve.cpp
5
└── duipai.cpp

2. 数据生成器#

2.1 生成整数#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
mt19937 rng(
5
    chrono::steady_clock::now().time_since_epoch().count()
6
);
7

8
int rnd(int l, int r) {
9
    return uniform_int_distribution<int>(l, r)(rng);
10
}
11

12
int main() {
13
    int n = rnd(1, 10);
14

15
    cout << n << endl;
16

17
    for (int i = 1; i <= n; i++) {
18
        cout << rnd(-100, 100) << " ";
19
    }
20

21
    cout << endl;
22

23
    return 0;
24
}

2.2 生成浮点数#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
mt19937 rng(
5
    chrono::steady_clock::now().time_since_epoch().count()
6
);
7

8
double rnd(double l, double r) {
9
    return uniform_real_distribution<double>(l, r)(rng);
10
}
11

12
int main() {
13
    int n = 10;
14

15
    cout << n << endl;
16

17
    cout << fixed << setprecision(6);
18

19
    for (int i = 1; i <= n; i++) {
20
        cout << rnd(-100.0, 100.0) << " ";
21
    }
22

23
    cout << endl;
24

25
    return 0;
26
}

2.3 同时生成整数和浮点数#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
mt19937 rng(
5
    chrono::steady_clock::now().time_since_epoch().count()
6
);
7

8
int rndInt(int l, int r) {
9
    return uniform_int_distribution<int>(l, r)(rng);
10
}
11

12
double rndDouble(double l, double r) {
13
    return uniform_real_distribution<double>(l, r)(rng);
14
}
15

16
int main() {
17
    int n = rndInt(1, 10);
18

19
    cout << n << endl;
20

21
    for (int i = 1; i <= n; i++) {
22
        cout << rndInt(-100, 100) << " ";
23
    }
24

25
    cout << endl;
26

27
    cout << fixed << setprecision(6);
28

29
    for (int i = 1; i <= n; i++) {
30
        cout << rndDouble(-100.0, 100.0) << " ";
31
    }
32

33
    cout << endl;
34

35
    return 0;
36
}

3. Windows 对拍#

3.1 编译#

1
g++ gen.cpp -std=c++17 -O2 -o gen.exe
2
g++ std.cpp -std=c++17 -O2 -o std.exe
3
g++ solve.cpp -std=c++17 -O2 -o solve.exe
4
g++ duipai.cpp -std=c++17 -O2 -o duipai.exe

3.2 duipai.cpp#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main() {
5
    int cnt = 0;
6

7
    while (true) {
8
        cnt++;
9

10
        system("gen.exe > test.in");
11

12
        system("std.exe < test.in > std.out");
13
        system("solve.exe < test.in > solve.out");
14

15
        if (system("fc std.out solve.out > nul")) {
16
            cout << "\nWrong Answer!" << endl;
17
            cout << "Test: " << cnt << endl;
18

19
            cout << "\nInput:" << endl;
20
            system("type test.in");
21

22
            cout << "\nStandard Output:" << endl;
23
            system("type std.out");
24

25
            cout << "\nYour Output:" << endl;
26
            system("type solve.out");
27

28
            break;
29
        }
30

31
        cout << "Accepted: " << cnt << "\r";
32
    }
33

34
    return 0;
35
}

运行：

1
duipai.exe

4. Linux 对拍#

4.1 编译#

1
g++ gen.cpp -std=c++17 -O2 -o gen
2
g++ std.cpp -std=c++17 -O2 -o std
3
g++ solve.cpp -std=c++17 -O2 -o solve
4
g++ duipai.cpp -std=c++17 -O2 -o duipai

4.2 duipai.cpp#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main() {
5
    int cnt = 0;
6

7
    while (true) {
8
        cnt++;
9

10
        system("./gen > test.in");
11

12
        system("./std < test.in > std.out");
13
        system("./solve < test.in > solve.out");
14

15
        if (system("diff std.out solve.out > /dev/null")) {
16
            cout << "\nWrong Answer!" << endl;
17
            cout << "Test: " << cnt << endl;
18

19
            cout << "\nInput:" << endl;
20
            system("cat test.in");
21

22
            cout << "\nStandard Output:" << endl;
23
            system("cat std.out");
24

25
            cout << "\nYour Output:" << endl;
26
            system("cat solve.out");
27

28
            break;
29
        }
30

31
        cout << "Accepted: " << cnt << "\r";
32
    }
33

34
    return 0;
35
}

运行：

1
./duipai

5. 常用命令#

Windows#

1
gen.exe > test.in
2
std.exe < test.in > std.out
3
solve.exe < test.in > solve.out
4
fc std.out solve.out

Linux#

1
./gen > test.in
2
./std < test.in > std.out
3
./solve < test.in > solve.out
4
diff std.out solve.out

6. 浮点数对拍#

浮点数不要直接比较文件，使用误差判断：

1
double a, b;
2

3
if (fabs(a - b) > 1e-6) {
4
    cout << "Wrong Answer" << endl;
5
}

常用：

1
bool equal(double a, double b) {
2
    return fabs(a - b) <= 1e-6;
3
}

对拍#

1. 文件结构#

2. 数据生成器#

2.1 生成整数#

2.2 生成浮点数#

2.3 同时生成整数和浮点数#

3. Windows 对拍#

3.1 编译#

3.2 duipai.cpp#

4. Linux 对拍#

4.1 编译#

4.2 duipai.cpp#

5. 常用命令#

Windows#

Linux#

6. 浮点数对拍#

评论