L2 对拍

目录

• 代码实现
  • 0. 数据生成器 (gen.cpp)
  • 1. 暴力算法 (vio.cpp)
  • 2. 数学算法 (test.cpp)
  • 3. 对拍程序 (check.cpp)
• 注意
• 参考

此篇blog讲解对拍的实现与技巧

代码实现

（本文以求两数的最小公倍数为例）

0. 数据生成器 (gen.cpp)

(code):

#include<iostream>
#include<cstdlib>
#include<Windows.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    srand(GetTickCount());
    cout << (rand() >> 8) << (rand() >> 8);
}

1. 暴力算法 (vio.cpp)

(code):

#include<iostream>
#include<algorithm>
using namespace std;
int a, b;
int main(){
    ios::sync_with_stdio(false);
    cin >> a >> b;
    for(int i = max(a, b); i <= a * b; ++i)
        if(!(i % a || i % b)){
            cout << i;
            return 0;
        }
}

2. 数学算法 (test.cpp)

(code):

#include<iostream>
using namespace std;
inline int gcd(int a, int b){
    return b ? a : gcd(b, a % b);
}
int a, b;
int main(){
    ios::sync_with_stdio(false);
    cin >> a >> b;
    cout << a * b / gcd(a, b);
}

3. 对拍程序 (check.cpp)

(code):

#include<iostream>
#include<Windows.h>
using namespace std;
const int T=114;
int main(){
    /*由于使用Dev-cpp导致环境变量未配置等问题，不建议比赛中在对拍程序内编译，应提前编译好后运行对拍程序
    system("g++ gen.cpp -o gen.exe -g -Wall");
    system("g++ vio.cpp -o vio.exe -g -Wall");
    system("g++ test.cpp -o test.exe -g -Wall");
    */
    for(int i = 1; i <= T; ++i){
        system("gen.exe > sample.txt");
        system("vio.exe < sample.txt > vio.txt");
        system("test.exe < sample.txt > test.txt");
        cout << "#" << i << ":
";
        if(system("fc vio.txt test.txt")){
            cout << "Error on #" << i << "!
";
            return 0;
        }
    }
    cout << "No error!
";
}

注意

1. 由于使用Dev-cpp导致环境变量未配置等问题，不建议比赛中在对拍程序内编译，应提前编译好后运行对拍程序
2. 对拍只能保证正确性，不能保证最优性，即只能保证答案正确
3. 在家做题可以贴一个题解，答案正确就行
4. 编数据时最好不要用原题数据，暴力会卡死，毕竟只是保证正确性，数据小一点就好

参考

• 对拍详解_Njhemu的博客-CSDN博客