对拍器模板
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
| #include <bits/stdc++.h>
#define random(a, b) ((a)+rand()%((b)-(a)+1))
using namespace std;
void create_dataset() {
ofstream fout("input.txt");
fout.close();
}
bool work() {
create_dataset();
system("stand.exe < input.txt");
system("my.exe < input.txt");
return system("fc stand.txt my.txt");
}
void dp(int itNum) {
srand(time(nullptr));
for (int i = 1; i <= itNum; i ++ ) {
cout << "test" << i << ":\n";
if (work()) {
cout << "Wrong Answer\n";
getchar();
}
}
cout << "Done";
}
int main() {
dp(64);
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include<bits/stdc++.h>
using namespace std;
函数,变量命名等...
int main(){
freopen("input.txt", "r", stdin);
freopen("my.txt", "w", stdout);
.....
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include<bits/stdc++.h>
using namespace std;
函数,变量命名等...
int main(){
freopen("input.txt", "r", stdin);
freopen("stand.txt", "w", stdout);
.....
return 0;
}
|
关于这个ofstream fout(“input.txt”);以及fout.close()，close最好在不用了就写上以避免不必要的错误。ofstream fout() 的括号里面还可以传递其它参数，这里默认表示为：ofstream fout(“input.txt”,ios::trunc);
表示截断并覆写文件。所有可以表示的参数：
ios::app 添加到文件尾
ios::ate 把文件标志放在末尾而非起始。
ios::trunc 默认. 截断并覆写文件。
ios::nocreate 文件不存在也不创建。
ios::noreplace 文件存在则失败。
通常ios::app用的会比较多，他可以让对拍程序分开输入数据到文件
linux下的对拍
linux下的系统命令与windows的命令不太一样，所以对拍器的写法也要变一下。
其实要改的就只有work函数以及main函数，其他都不需要变
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
| #include <bits/stdc++.h>
#include <cstdlib>
#define random(a, b) ((a)+rand()%((b)-(a)+1))
using namespace std;
void create_dataset() {
ofstream fout("input.txt");
fout.close();
}
bool work() {
create_dataset();
system("./my.out");
system("./stand.out");
return system("diff my.txt stand.txt");
}
void dp(int itNum) {
srand(time(nullptr));
for (int i = 1; i <= itNum; i ++ ) {
cout << "正在运行第" << i << "组数据"<<endl;
if (work()) {
cout << "出错了"<<endl;
getchar();
}
}
cout << "Done";
}
int main() {
system("g++ my.cpp -o my.out");
system("g++ stand.cpp -o stand.out");
dp(64);
return 0;
}
|
数据生成
通常的数据生成比较容易，但是遇到一些不好处理的输入则需要模板
指定根节点的多叉树/无根树
树的生成要保证边数等于结点树减一，并且不能成环且每个点之间都要联通
输入形式形如：
5
1 2
1 3
2 4
4 5
这种可以用并查集来维护这棵树。
考虑以1为根节点，那么只要对于n到2的每一个节点i,让random(1,i-1)为它的根，可以保证这样不会成环且连通。
如果不要求一定以1为根节点,可以用random_shuffle函数获得一个随机的1~n的排列，然后对应着输出就好。
1
2
3
4
5
6
7
8
9
10
11
12
13
| void build(int n) {
for (int i = n; i >= 2; --i) {
dsu[i] = random(1, i - 1);
}
for (int i = 1; i <= n; ++i) mapp[i] = i;
random_shuffle(mapp + 1, mapp + n + 1);
fout << n << endl;
for (int i = 2; i <= n; ++i)
fout << mapp[i] << ' ' << mapp[dsu[i]] << endl;
fout.close();
}
|
形如：
9
1 3 2 4 5
2 2 3 6
3 2 7 9
4 1 8
5 0
6 0
7 0
8 0
9 0
其中2到n+1行的第一列表示第几个节点，第二列表示接来跟着的几个数的总数是所对应的相邻节点的个数。
实现的方法也很简单，第一种形式已经得到了第i个结点对应的父节点，所以可以反过来开一个set数组记录父节点对应的子节点，因为第一种生成的得到的会有重复，所以用set去重。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void create_dataset() {
ofstream fout("input.txt");
int n = random(1, 100);
fout << n << endl;
cout << n << endl;
for (int i = n; i >= 2; --i) {
son[random(1, i - 1) - 1].insert(i - 1);
}
for (int i = 0; i < n; ++i) {
fout << i << ' ';
cout << i << ' ';
fout << son[i].size() << ' ';
cout << son[i].size() << ' ';
for (int it : son[i]) {
fout << it << ' ';
cout << it << ' ';
}
cout << endl;
}
fout.close();
}
|
