Mohen's Blog

旧的不去新的不来

C++对拍

发表于 更新于 分类于
本文字数： 1.5k 阅读时长 ≈ 5 分钟

对拍

  1. 关于对拍:

对拍是一个检验你的暴力程序是否正确的东西，在考场上十分有用！(而且很好打)

它可以让你认为的标准正确程序和你的暴力程序一起读入一些值并输出这些值，再比较异同

  1. 对拍程序

    直接上代码:
    1
    2
    3
    4
    5
    6
    7
    :loop   //循环
    gen.exe>in.txt    //gen为生成随机数的程序，生成随机数输入进in.txt
    check.exe<in.txt>out1.txt   //check为你的暴力程序 从in读入输出进out
    mine.exe<in.txt>out2.txt    //mine是你认为的正确程序
    fc out1.txt out2.txt      //比较两个程序输出的异同
    if not errorlevel 1 goto loop    //如果找不出异同(也就是两个程序输出一样)就继续下次循环
    pause     //如果不同就暂停
    只需把上述代码复制进新建文本文档中**(将”//“的注释删去)**，再将后缀改为.bat即可！

  2. 使用对拍

首先你得先有一道题
比如这道：

【题目描述】

给定一个长度为 n 的序列 a[n]，和 q 个修改每个修改给定 l, r, k，代表将 a[l],a[l+1], …,a[r] 全部加上 k。最后输出整个序列。

【输入格式】

第 1 行一个整数 n

第 2 行 n 个数表示初始序列 a

第 3 行一个整数 q 表示询问个数

第 4 行到第 q + 3 行每行三个整数 l, r, k 描述一个修改。

【输出格式】

一行 n 个整数表示最终的序列。

【样例输入】 

1
2
3
4
5
6
5
1 2 3 4 5
3
1 3 1
2 4 -3
1 5 2

【样例输出】

1
4 2 3 3 7

【数据范围】

1
2
3
对于 30%的数据：n≤5000, q≤5000
对于 60%的数据：n≤100000,q≤100000
对于 100%的数据：n≤3000000, q≤3000000
先做一个生成随机数的程序(gen.cpp)
让你的程序自动生成符合条件的样例
如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
long long a[30001];
int main(){
	srand(time(0));   //一定要有这一行 定义随机种子
	int l,n,temp,tt;
	l=rand()%30000+1;  //随机生成1-30001的值
	cout<<l<<endl;    //按题目输出
	for(int i=1;i<=l;++i){
		a[i]=rand()%30000+1;   //随机生成1-30001的值
		cout<<a[i]<<' ';   //输出
	}
	cout<<endl;
	n=rand()%30000+1;  //随机生成1-30001的值
	cout<<n<<endl;    //输出
	for(int i=1;i<=n;++i){
		temp=rand()%l+1;
		tt=rand()%l+1;
		if(temp>tt)    //按题目要求从l到r
			swap(temp,tt);  //所以temp必须小于tt
		cout<<temp<<' ';  //输出
		cout<<tt<<' ';
		cout<<rand()%30000<<' '; 
		cout<<endl;
	}
	
}
急急忙忙打的，有点乱。。。
然后再做一个暴力(check.cpp)和一个你认为的正确算法(mine.cpp)
如下：

暴力算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
namespace IO {    //这一段是快读快写(这题数据比较大)

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template <typename T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read()) x = (x + (x << 2) << 1) + (c ^ '0');
    iosig ? x = -x : 0;
}

inline void read(char &c) {
    while (c = read(), isspace(c))
        ;
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1)
        ;
    if (c == -1) {
        *buf = 0;
        return -1;
    }
    do
        buf[s++] = c;
    while (c = read(), !isspace(c) && c != -1);
    buf[s] = 0;
    return s;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template <typename T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        x < 0 ? (print('-'), x = -x) : 0;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
}
using namespace IO;
long long a[3000001];
int main(){
	long long n,q,l,r,k,i,temp;
	read(n);
	for(i=1;i<=n;++i){
		read(temp);
		a[i]=temp;
	}
	read(q);
	for(i=1;i<=q;++i){
		read(l);
		read(r);
		read(k);
		for(;l<=r;++l){
			a[l]+=k;	
		}
	}
	for(i=1;i<=n;++i){
		print(a[i]);
		print(' ');
	}
	
	flush();
	return 0;
}

标准算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <set>
#include <queue>
#include <ctime>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template <typename T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read()) x = (x + (x << 2) << 1) + (c ^ '0');
    iosig ? x = -x : 0;
}

inline void read(char &c) {
    while (c = read(), isspace(c))
        ;
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1)
        ;
    if (c == -1) {
        *buf = 0;
        return -1;
    }
    do
        buf[s++] = c;
    while (c = read(), !isspace(c) && c != -1);
    buf[s] = 0;
    return s;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template <typename T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        x < 0 ? (print('-'), x = -x) : 0;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
}

using namespace IO;

const int MAXN = 3000000 + 11;

int n, q, l, r;
long long k;
long long a[MAXN];

int main() {
	read(n);
	for (int i = 1; i <= n; ++i) read(a[i]);
	for (int i = n; i >= 1; --i) a[i] -= a[i - 1];
	read(q);
	for (int i = 1; i <= q; ++i) {
		read(l), read(r), read(k);
		a[l] += k, a[r + 1] -= k;
	}
	for (int i = 1; i <= n; ++i) a[i] += a[i - 1], print(a[i]), print(' ');
	flush();
	return 0;
}
最后将check,mine,gen都编译为exe放入对拍所在的文件夹中，并运行对拍.bat
注意：用标准输入输出！不要用文件输入输出(freopen等)！
如图：

out1，out2 ，in 都是对拍程序自动生成的，out1是check程序的输出，out2是mine程序的输出，in是gen生成的随机样例，也是两个程序出现不同时的那个输入！(所以不同时可以复制in中的数据来调试程序)
当你两个程序输出的结果都一样时，你的对拍程序应该是一直循环的！

接着你就可以调大数据范围继续拍，直到达到题目给的数据范围！

以上就是对拍的全部内容！

-------------本文结束，感谢您的阅读-------------