以下文章专门面对 c Windos 选手使用其他语言或其他环境请另寻高明。笔者是万能头文件党非特殊情况文章里不会介绍头文件使用默认万能头。以下使用函数默认为 std 库标准函数即直接使用不加 std:: 的前缀。有相当一部分题目的样例十分寒碜有时样例全对但交上去不到 50 分。这时候我们需要自己造数据但一组组数据手动输入等输出肯定是不现实的。解决这种问题需要用到对拍。0.简述对拍是一种进行检验或调试的方法通过对比两个程序的输出来检验程序的正确性。可以将自己程序的输出与其他程序的输出进行对比从而判断自己的程序是否正确。一般我们对拍需要四个程序1待测 / 出现错误的程序sol.cpp (solution)这是准备交上去的程序已经尽量保证速度但还未测验正确性。2暴力 / 标准的程序bru.cpp (brute)这是你找的标程或是自己打的暴力速度可能不尽人意但输出保证绝对正确。3数据生成器gen.cpp (generator)这是你自己打的数据生成器通常用随机数函数生成。保证这个程序输出的都是符合题意且完美覆盖到所有边界情况的数据。4对拍脚本st.cpp (stress test)这是一个自动循环程序将执行以下操作调用 gen.cpp 生成输入将输入分别喂给 sol.cpp和 bru.cpp比较两个程序的输出是否一致若不一致保存当前输入并终止便于调试1.高质量随机数生成rand 家族首先我们把目光放在随机数生成函数上相信大家都听过rand()函数。这个函数在 Linux 环境下的随机数生成范围是而在 Windos 环境下却只有这太小了完全不够我们日常使用。不但如此rand() 即使有好种子作为生成基础但分布和周期仍不佳大量使用环境还是不推荐。srand(time(0)); // 用当前时间作为种子 int x rand() % 100; // 生成 [0, 99] 的随机整数如上为用每秒都变化不易重复的时间函数作为种子种子可以理解为每次玩 mc 输入的那个数字凭借这个种子生成地图随机数。一样的种子生成的东西就一样如果你做过随机乱搞题你应该对random_shuffle()也不陌生。它用于随机打乱一个数组同样以rand()为基底现已被时代淘汰。如今我们要达到同样的效果会使用shuffle函数配上高质量随机引擎见下文代码。高级货 MT 19937这个高质量随机引擎名为梅森旋转算法Mersenne Twister是一种广泛使用的伪随机数生成器周期为是一个梅森素数因此得名。具体使用如下#includebits/stdc.h using namespace std; #define uid uniform_int_distributionint // 这是一个 一致分布 映射函数后面经常跟着一段区间 // 用于把随机数生成器生成出大的数映射到这段区间里 // 大的数取模会有某个数字出现频率更高的情况而 uid 能保证所有数分布概率一样 // 当然你如果要 long long 的直接改类型就好就像这样 // #define uid uniform_int_distributionlong long // 这样后面跟着的区间就可以到 long long 的范围 // 不过区间常数也要是 long long 类型 // 比如这样dist(1, 1000000000000LL) int main() { // 我个人习惯关同步流不关也行关了快一点 ios::sync_with_stdio(false); cin.tie(0); // 创建一个 mt19937 类型的随机数引擎 rng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uid dist(1, 100); // 生成 [1, 100] 的随机整数严格闭区间 cout dist(rng) \n; // 以后想生成 [1, 100] 的随机整数直接调用 dist(rng) 就好 // 还需要更多范围的数 uid dist1(1, 10000); // [1, 10000] uid dist2(1, 1000000); // [1, 1000000] cout dist1(rng) \n; // 直接调用 cout dist2(rng) \n; vectorint v {1, 2, 3, 4, 5}; shuffle(v.begin(), v.end(), rng); // 用 rng 打乱 vector for (int x: v) { cout x ; } cout \n; return 0; }看起来多真正用的时候只需要记得这四句#define uid uniform_int_distributionint mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uid dist(1, 100); cout dist(rng) \n;多打几遍直到完全熟练。例题实战接下来尝试实战下以这道题为例P1141 01迷宫 - 洛谷大家可以自己先试试然后用文件输出看看生成的怎么样。这里提供标程// gen.cpp // 生成 P1141 01迷宫 的合法测试数据 // Windows 下可用 g 或 MinGW 编译运行 #include bits/stdc.h using namespace std; #define uid uniform_int_distributionint int main() { ios::sync_with_stdio(false); cin.tie(0); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uid n_dist(1, 1000); // n 范围 [1, 1000] uid m_dist(1, 100000); // m 范围 [1, 100000] // ****真正使用时可以适当缩小数据范围防止暴力程序美美卡住 *** int n n_dist(rng); int m m_dist(rng); cout n m \n; // 生成 n x n 的 01 矩阵 for (int i 1; i n; i ) { for (int j 1; j n; j ) { cout (rng() 1); // 快速生成 0 或 1 } cout \n; } // 生成 m 个查询 uid x_dist(1, n); uid y_dist(1, n); for (int i 1; i m; i ) { cout x_dist(rng) y_dist(rng) \n; } return 0; }每道题都有不同的数据生成程序 gen.cpp不过大部分都是换汤不换药。有一些特殊的比如说生成无自环、无重边的二叉树就得在 gen 里面加上一些小智慧或者算法如 vector 记录可作为父亲的点再随机选取。这些我先暂时不讲后面有时间补上。2.对拍脚本这是很关键的一步要保证你的程序能自个儿循环 or 找错对拍脚本是不能少的。你需要先将四个程序待测暴力数据生成对拍脚本全部放在同一个文件夹里。然后运行待测和暴力程序以及数据生成器保存三个 exe在上文的相同文件夹里。接下来运行这个程序// stress test /* x y将 x 作为 y 的输入 x y将 x 的输出写入 y 其中 a 是程序b 是文本 可以理解为尖尖朝哪边哪边就是被放入数据的 */ /* system 函数是一个系统调用函数 成功了会返回 0非成功返回非 0 通常是 1 */ #includebits/stdc.h using namespace std; int main() { // 这里可不能关同步流不然没缓冲看不到文字输出 int tot 0; // 计数的 // 循环持续生成测试数据并进行对拍直到发现错误 while (1) { tot ; cout Generating test case tot \n; // 这里用英文有些环境下中文会乱码 // 1. 调用数据生成器 gen.exe // 将生成的测试数据放到文件 test.in输入数据 里 system(gen test.in); // 2. 运行第一个程序sol.exe // 待测 sol 程序从 test.in 读取输入将输出放到 a.out system(sol.exe test.in a.out); // 3. 运行第二个程序bru.exe // 暴力 bru 程序从 test.in 读取输入将输出放到 b.out system(bru.exe test.in b.out); // 4. 比较两个输出文件 a.out 和 b.out 是否一致 // fc 是 Windos 自带文件比较函数 // 如果文件完全相同fc 返回 0 // 如果文件不同fc 返回非 0 值通常为 1 // system(fc a.out b.out) ! 0说明输出不一致。 if (system(fc a.out b.out nul)) { // fc 会自动输出一些东西我们这里用不到就把它放到 nul 空文件里 cout The test case tot is wrong! \n; // 要把上面这句话放在 pause 上面才能看到 system(pause); // pause 暂停程序方便你查看控制台输出的差异信息 // 立即退出对拍器 // 此时 test.in 中保存的就是导致错误的输入数据 // 可以用该数据单独调试 sol 和 bru return 0; } // 如果输出一致循环继续生成下一组测试数据 if (tot 10000) { // 拍了一万组 cout A possible solution. \n; // 可能也许大概是正确的 system(pause); return 0; } } }这个 Windows 脚本对于所有题都是适用的只要你保证在同一个文件夹、有 exe、无同名程序。3.待测程序与暴力程序这个放到后面来讲是因为比起前面两个这俩玩意是因题而异。就拿之前那道例题来说P1141 01迷宫 - 洛谷虽然聪明的同学们一看就知道是广搜 带权并查集但假设我们还没有那么聪明。傻傻的把每一个询问点都拿去广搜也就有了我们的70 分 TLE 暴力 bru 程序。时间复杂度// bru.cpp #include bits/stdc.h using namespace std; const int N 1010; const int dx[4] {0, 0, 1, -1}; const int dy[4] {1, -1, 0, 0}; char s[N]; int a[N][N]; bool v[N][N]; int n, m; int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 1; i n; i) { cin (s 1); for (int j 1; j n; j) { a[i][j] s[j] - 0; } } for (int i 1; i m; i) { int x, y; cin x y; // 每次查询清空 vis memset(v, 0, sizeof(v)); queueint Q; Q.push((x - 1) * n (y - 1)); // 0-indexed 每个点唯一编码 v[x][y] 1; int cnt 0; while (!Q.empty()) { int head Q.front(); Q.pop(); int x head / n 1; // 转回 1-indexed 行 int y head % n 1; // 转回 1-indexed 列 cnt ; for (int d 0; d 4; d) { int xx x dx[d]; int yy y dy[d]; if (xx 1 xx n yy 1 yy n !v[xx][yy]) { if (a[x][y] ! a[xx][yy]) { v[xx][yy] 1; Q.push((xx - 1) * n (yy - 1)); } } } } cout cnt \n; } return 0; }然后我们再打一个待测程序故意出错比如说点转编号时错误。以下程序通过样例但交上去 10 分时间复杂度。// sol.cpp #include bits/stdc.h using namespace std; const int N 1010; char s[N]; int a[N][N], mp[N][N]; int n, m; int siz[N * N], fa[N * N]; int findfa(int x) { if (fa[x] x) return fa[x]; return fa[x] findfa(fa[x]); } queueint Q; bool v[N * N]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; void bfs() { while (!Q.empty()) { int head Q.front(); Q.pop(); if (v[head]) continue; v[head] true; int x head / n 1, y head % n; // 如果 head 本来的点 y n那这里转编号就会错 for (int i 0; i 4; i) { int xx x dx[i]; int yy y dy[i]; if (xx 1 || xx n || yy 1 || yy n) continue; if (a[xx][yy] a[x][y]) continue; int np mp[xx][yy]; Q.push(np); int tx findfa(head); int ty findfa(np); if (tx ! ty) { fa[tx] ty; siz[ty] siz[tx]; } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 1; i n; i) { cin (s 1); for (int j 1; j n; j) { a[i][j] s[j] - 0; mp[i][j] (i - 1) * n j; // 这里 j 没有 - 1 fa[mp[i][j]] mp[i][j]; siz[mp[i][j]] 1; } } memset(v, 0, sizeof(v)); for (int i 1; i n; i) { for (int j 1; j n; j) { int id mp[i][j]; if (!v[id]) { Q.push(id); bfs(); } } } while (m--) { int x, y; cin x y; int pfa findfa(mp[x][y]); cout siz[pfa] \n; } return 0; }4.实操好啦美美开工。注意注意这里要先把 gen.cpp 的数据生成范围改小这样才方便调试uid n_dist(1, 30); // n 范围 [1, 30] uid m_dist(1, 500); // m 范围 [1, 500]不然暴力程序就会一直运行毕竟时间复杂度高出不来结果还有请事先保证sol.cpp和bru.cpp的输出格式完全一致包括换行符、空格、无多余空行否则fc可能误报错误。首先先建一个文件夹为了模仿比赛这里建在 D 盘。然后把所有程序都放进去命好名除了 st 都在 dev 里运行得到 exe点运行然后关掉黑框。搞好了就长这样现在开始运行 st.cpp会出现这样第一组就错了回到文件夹点开三个文本看看。很好找到问题修改完后再次运行出 exe运行下 st.cpp 看看。就是改了这两句27 int x head / n 1, y head % n 1; 57 mp[i][j] (i - 1) * n j - 1;然后你就会看到嘛如果你愿意等并且不怕电脑烧坏的话就可以拿到 A possible solution. 成就。参考资料常见技巧 - OI WikiDont use rand(): a guide to random number generators in C - Codeforces后记对拍是很重要的技能需要多练习。但不要每道题都盲目使用对拍进一步调试的前提是自己仔细检查每一行代码。这算是干了一件一直想干的事情希望能帮助到你。后面会在这里给一些链接作为对拍例子博客。