OI赛制下的技巧——对拍
Charles_with_wkc
·
2024-09-15 13:26:26
·
算法·理论
什么是对拍
众所周知，OI 赛制每道题提交之后都没有任何反馈，并且只有 1 到 2 个输入输出样例，而样例自测通过也并不代表满分，经常会有样例过了可只有几十分的情况，所以我们需要测试更多的样例以检验正确率。
这个时候我们可以适当引入对拍技巧！
对拍怎么写
首先需要一个你已经写好的，准备提交的标准源程序，其次再写一个暴力程序暴力程序实现的功能和标准源程序实现的功能是一样的，只不过暴力算法好写，正确率
也更高，再接下来写一个随机数据生成程序，将随机产生的数据分别输入到标准源程序和暴力程序，多次对比两个程序的输出，观察正确率。
比如一般 DP 题目的对应的暴力程序就是搜索算法了，所以这里我们将以 01背包 的实现为例。
自定义输入文件，自定义标准源程序对应的输出文件，自定义暴力程序对应的输出文件。
//标准源程序：01dp.cpp
#include
using namespace std;
const int N = 1e5 + 10;
int m, n;
int c[N], w[N], dp[N];
int main() {
freopen("input.in", "r", stdin);
freopen("output1.out", "w", stdout);
cin >> m >> n;
for (int i = 1; i <= n; i++) cin >> w[i] >> c[i];
for (int i = 1; i <= n; i++)
for (int j = m; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
cout << dp[m] << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
暴力程序：01dfs.cpp
#include
using namespace std;
const int N = 1e5 + 10;
int m, n;
int c[N], w[N];
bool vis[N];
int maxValue;
void dfs(int Value, int V, int dep) {
if (V < 0) return;
maxValue = max(maxValue, Value);
if (dep == n + 1) return;
// 随机数生成程序：randData.cpp
// 最终运行randData.cpp即可测试标准程序的大概正确率了（当然了，要保证暴力程序是对的）！
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
vis[i] = 1;
dfs(Value + w[i], V - c[i], dep + 1);
vis[i] = 0;
}
}
}
int main() {
freopen("input.in", "r", stdin);
freopen("output2.out", "w", stdout);
cin >> m >> n;
for (int i = 1; i <= n; i++) cin >> c[i] >> w[i];
dfs(0, m, 1);
cout << maxValue << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
//随机数生成程序：randData.cpp
#include
using namespace std;
void data() {
ofstream fout("input.in");//将数据录入到input文件
int m = rand() % 200;
int n = rand() % 10;
fout << m << " " << n << endl;
int c, w;
while (n--) {
c = rand() % 11 + 1, w = rand() % 11 + 1;
fout << c << " " << w << endl;
}
fout.close();
}
bool test() {
data();//生成数据
system("01dp.exe");//运行待测程序
system("01dfs.exe");//运行评测程序
return !system("fc output1.out output2.out");//比对这俩的输出是否一样
}
int main() {
srand((int)time(0));
for (int i = 1; i <= 100; i++) {//测100次
if (!test()) break;
}
return 0;
}
最终运行随机生成数生成代码即可测试标准程序的大概正确率了。当然了，要保证暴力程序是对的！