对拍器模板

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 > stand.txt");
//system("my.exe < input.txt > my.txt");
	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
//测试的代码，命名为my
#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
//正确的代码，命名为stand
#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);//生成一颗以1为根节点的树
	}
	//以上为以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;
	//生成一棵以0为根节点的树
	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();
}