对拍

发表于 | | 阅读次数:
字数统计: 1k | 阅读时长 ≈ 4

简介

对拍是一种对学竞赛的同学非常有用的debug技能。在做题时，你肯定会遇到这样的情况：

？？？我不是过了样例吗？？？为什么WA了2个点？？？代码好像没什么问题啊？？？辣鸡评测姬

这个时候你就需要对拍来调试程序了。

对拍，说白了就是拿一个输入数据分别让你写的程序和标程（暴力程序）跑一遍，比较输出的数据。
对拍一般有以下3个步骤：

  1. 生成一组输入数据
  2. 把这组数据分别让两个程序运行一遍，生成输出数据
  3. 比较两组输出数据

那么实现对拍，我们需要：

  • 你的程序
  • 标程
  • 数据生成器
  • 对拍脚本（批处理脚本）

如果你懒得看下面的内容可以直接在GitHub下载程序。

本文仅适用于Windows系统（虽然考试大多在Linux上）。

批处理脚本

假设你已经写好了一个数据生成器并编译成了rand.exe，那么我们可以把它的输出重定向到文件std.in：

1
rand.exe > std.in

当然你也可以直接在源码里重定向输入输出流，不过这样比较麻烦，所以一般不采用这种做法。

输入重定向也类似，假设my.exe是你的程序，std.exe是标程：

1
2
my.exe < std.in
std.exe < std.in

然后再把输出重定向到文件里：

1
2
my.exe < std.in > my.out
std.exe < std.in > std.out

接下来就是比较了，Windows自带一个fc命令，用于比较两个文件：

1
fc my.out std.out /n

当两个文件有差异时，会显示不同处附近的几行文本。/n参数会显示行号。

这样我们就可以写出一个对拍脚本了：

1
2
3
4
5
6
7
8
9
@echo off
:loop
    rand.exe > std.in
    my.exe < std.in > my.out
    std.exe < std.in > std.out
    fc my.out std.out /n
    if not errorlevel 1 goto loop
    pause
    goto loop

@echo off的作用是关掉输入显示；
:loop的作用与C中的goto类似，标号loop；
errorlevel是上一个命令的返回值，fc在文件相同时会返回0，不同时返回1，因此if not errorlevel 1 goto loop的意思是：如果fc返回的不是1，就跳转到loop（相当于循环）；
一旦返回值为1，脚本就会以pause命令暂停，让你可以看数据；
最后goto loop，继续循环。

把这个脚本命名为check.bat，可以直接运行。

新鲜的炒栗

比如P1001 A+B Problem这道难题，我们先写出标程：

1
2
3
4
5
6
7
8
#include <iostream>

int main() {
    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << std::endl;
    return 0;
}

这是不确定对不对的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>

int main() {
    int a, b, sum = 0, carry = 0;
    std::cin >> a >> b;
    do {
        sum = a ^ b;
        carry = (a & b) << 1;
        a = sum;
        b = carry;
    }
    while (carry);
    std::cout << sum << std::endl;
    return 0;
}

数据生成器怎么写呢？
头文件stdlib.h中有一个rand()函数，可以生成0到RAND_MAX之间的一个随机整数，RAND_MAX定义在stdlib.h中，其值为2147483647。
由于题目要求有负数，因此可以再生成一个随机数来设置符号：

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <cstdlib>

int main() {
    const int p = 1000000000;
    int a = rand() % p, b = rand() % p;
    a = (rand() % 2 == 0 ? -a : a), b = (rand() % 2 == 0 ? -b : b);
    std::cout << a << " " << b << std::endl;
    return 0;
}

但是，上面的程序重新运行后生成的随机数相同，因为随机数种子相同，因此我们需要用srand()函数设置种子。
一般都使用time(NULL)的返回值作为种子（对于C++ 11，建议使用time(nullptr)），time()函数包含在time.h头文件中：

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <cstdlib>
#include <ctime>

int main() {
    const int p = 1000000000;
    srand(time(nullptr));
    int a = rand() % p, b = rand() % p;
    a = (rand() % 2 == 0 ? -a : a), b = (rand() % 2 == 0 ? -b : b);
    std::cout << a << " " << b << std::endl;
    return 0;
}

0%