Java算法竞赛对拍笔记

一、对拍概述

对拍是一种检测代码错误的方法，主要通过对比两个程序的输出结果来实现。
包含以下几个关键部分：

暴力程序：正确但低效的算法，通常采用完全搜索等方式。
待测程序：优化后的算法，需要验证其正确性。
数据生成器：随机生成符合要求的测试数据。
对拍脚本：自动运行并比较两个程序的输出结果。

二、对拍步骤与组件

1. 数据生成器（Maker）

作用：生成符合输入格式的随机测试数据。
示例代码（Java）：

import java.io.*;
import java.util.Random;

public class Maker {
    public static void main(String[] args) {
        try (PrintWriter out = new PrintWriter("input.txt")) {
            Random rnd = new Random();
            int n = rnd.nextInt(10) + 1; // 随机生成测试数据
            int m = rnd.nextInt(100);
            out.println(n + " " + m);
            for (int i = 0; i < n; i++) {
                out.println(rnd.nextInt(100) + " " + rnd.nextInt(100));
            }
        }
    }
}

2. 暴力程序（Brute Force）

作用：使用简单但正确的算法生成答案。
示例代码（Java）：

import java.io.*;
import java.util.*;

public class Brute {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(new File("input.txt"));
        PrintWriter out = new PrintWriter("brute.out");
        int n = in.nextInt();
        int m = in.nextInt();
        // 示例：0-1背包暴力解法（枚举所有可能）
        int[] w = new int[n];
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = in.nextInt();
            c[i] = in.nextInt();
        }
        int max = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            int weight = 0, cost = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    weight += w[i];
                    cost += c[i];
                }
            }
            if (weight <= m && cost > max) {
                max = cost;
            }
        }
        out.println(max);
        out.close();
    }
}

3. 待测程序（Solution）

作用：实现优化算法，需与暴力程序结果一致。
示例代码（Java）：

import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(new File("input.txt"));
        PrintWriter out = new PrintWriter("solution.out");
        int n = in.nextInt();
        int m = in.nextInt();
        // 示例：0-1背包动态规划解法
        int[] w = new int[n];
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = in.nextInt();
            c[i] = in.nextInt();
        }
        int[] dp = new int[m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= w[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - w[i]] + c[i]);
            }
        }
        out.println(dp[m]);
        out.close();
    }
}

4. 对拍脚本

作用：自动运行生成器、暴力程序、待测程序，并比较输出结果。
Windows批处理脚本示例：

@echo off
:loop
echo 正在生成数据...
javac Maker.java
java Maker > input.txt
echo 正在运行暴力程序...
javac Brute.java
java Brute < input.txt > brute.out
echo 正在运行待测程序...
javac Solution.java
java Solution < input.txt > solution.out
echo 正在比较结果...
fc brute.out solution.out
if errorlevel 1 (
    echo 出错！请检查代码！
    pause
    exit
)
echo 测试通过，继续下一轮...
goto loop

Linux Bash脚本示例：

#!/bin/bash
while true; do
    # 生成数据
    javac Maker.java && java Maker > input.txt
    # 运行暴力程序
    javac Brute.java && java Brute < input.txt > brute.out
    # 运行待测程序
    javac Solution.java && java Solution < input.txt > solution.out
    # 比较结果
    diff brute.out solution.out
    if [ $? -ne 0 ]; then
        echo "Error! 请检查代码！"
        exit 1
    else
        echo "AC! 继续测试..."
    fi
done

三、注意事项

输入输出一致性：
- 确保所有程序的输入输出格式一致（如空格、换行符）。
- 使用 System.in 和 System.out 以便重定向，或手动读写文件。
数据覆盖：
- 数据生成器需覆盖边界条件（如最大值、最小值、极端情况）。
程序效率：
- 暴力程序可能在大数据时超时，可限制生成数据规模。
错误处理：
- 检查程序是否崩溃或输出异常（如 NullPointerException）。
环境配置：
- 确保 Java 环境变量正确，路径无误。
- 在 Linux 下给脚本执行权限：chmod +x script.sh。