NOIP/CSP算法竞赛对拍四步曲(windows + NOILinux2.0环境)详细举例_csp 对拍

0.对拍四步曲详解

所谓对拍是指用一个一定正确但会超时的暴力算法(brute force，简称xxx.bf.cpp)生成一组.in — .ans数据，去检验另一种不会超时，但有可能会出错的"高效"代码(简称xxx.cpp, 生成.out数据), 然后写一个compare.cpp程序去自动对比.ans文件和.out文件，一般对比10000次左右，要么全部AC, 要么.ans 和.out不相同，结合此时的.in文件再修改xxx.cpp，直到完全正确。

对拍四步曲:

1. 运行random.cpp随机生成符合输入格式的.in文件
2. 运行"朴素解法"xxx.bf.cpp生成.ans文件
3. 运行"高效正解"xxx.cpp生成.out文件
4. 运行"对拍程序"compare.cpp自动对比.out 文件和 .ans文件

1.来,偷袭(sneak.cpp)—2020年小学组

【问题描述】 叶子是一只时间观念很强的小狮子。它会在 t 时刻发出第一声怒吼。接着每隔 s 秒，它会发出两声怒吼，时间间隔为 1 秒。形式化的来说，叶子会在以下时刻发出怒吼：t, t + s, t + s + 1, t + 2s, t + 2s + 1 …
小林非常喜欢动物，他想在 x 时刻去摸叶子， 但是在狮子怒吼的时候去摸它是一件非常危险的事情。所以他想请你告诉他在 x 时刻，叶子会不会怒吼。

【输入格式】 输入文件名为 sneak.in。
输入共 1 行，只包含 3 个整数 t，s 和 x。分别表示叶子第1次怒吼的时间、间隔和摸叶子的时刻。

【输出格式】 输出文件名为 sneak.out。
输出共 1 行，如果叶子会在 x 时刻怒吼，则输出 “YES”, 否则输出 “NO”。（输出不包含引号）

【样例输入1】3 10 4
【样例输出1】NO

【样例输入2】3 10 3
【样例输出2】YES

【数据范围】对 100% 的数据， 0 ≤ t, x ≤ 10⁹，2 ≤ s ≤ 10⁹

1.1.第一步生成.in文件：产生随机数据的 random.cpp

#include<bits/stdc++.h>
using namespace std;

int random(int n) {
	return (long long) rand() * rand() % n;
}

int main() {
	freopen("sneak.in", "w", stdout);
	srand(time(0));
	
	int n = 1e9;   // 一般为了便于自己验证答案，尽量生成小点的数据

	int t, s, x;

	t = random(n);

	while (true) {
		s = random(n);
		if (2 <= s) break;
	}

	x = random(n);

	cout << t << ' ' << s << ' ' << x << endl;
	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

1.2.第二步生成.ans文件—朴素算法 (枚举, sneak.bf.cpp) O(n）

• 利用一个循环，暴力枚举[t, x]范围内所有叶子怒吼时间点
• 时间复杂度为 O(n)，观察数据范围不难发现，此算法会超时

#include<bits/stdc++.h>
using namespace std;

int main() {
	freopen("sneak.in", "r", stdin);
	freopen("sneak.ans", "w", stdout);
	
	int t, s, x;
	cin >> t >> s >> x;
	if (t == x) {
		cout << "YES" << endl;
		return 0;
	}
	
	for (int i = t + s;  ; i += s) {
		if (i == x || i + 1 == x) {
			cout << "YES" << endl;
			return 0;
		}
		if (i > x) break;
	}
	
	cout << "NO" << endl;
	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

1.3.第三步生成.out文件—高效正解 (数学，sneak.cpp) O(1）

• 观察叶子怒吼时间点不难发现：所有怒吼时间点-t后为 0 s s+1 2s 2s+1 3s … 规律不言而喻，但要注意 t + 1时刻的特判
• 由于只需要一个if语句，时间复杂度为O(1)

#include<bits/stdc++.h>
using namespace std;

int main() {
	freopen("sneak.in", "r", stdin);
	freopen("sneak.out", "w", stdout);

	int t , s , x ;
	cin >> t >> s >> x ;

	t = x - t;

	if (t % s == 0 || t % s == 1 && t != 1) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}
	
	return 0 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.4.第四步—开始对拍(自动对比.ans与.out)

1. 自动对比的compare.cpp(windows环境)：

#include<bits/stdc++.h>
using namespace std;

int main() {
	for (int T = 1; T <= 10000; ++T) {
		system("C:\\random.exe");
		system("C:\\sneak.bf.exe");
		system("C:\\sneak.exe");

		if (system("fc C:\\sneak.out C:\\sneak.ans")) {
			cout << "WA" << endl;
			return 0;
		} else {
			cout << "AC, 测试点#" << T << endl;
		}
	}
	
	return 0 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2. 自动对比的compare.sh(NOILinux2.0环境)：

#! /bin/bash
g++ random.cpp -o random
g++ sneak.bf.cpp -o bf
g++ sneak.cpp -o sol

for i in {1..10000}
do
	./random
	./bf
	./sol
	
	if diff ./sneak.ans ./sneak.out
	then
		printf "AC "
	else 
		echo "WA"
		exit 0
	fi
done
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.小聪明(clever.cpp)—2020年小学组

【问题描述】 叶子是一个有强迫症的人，他只喜欢有限的东西。所以他想请你帮他判断一下一个分数是无限小数还是有限小数。

【输入格式】 输入文件名为 clever.in。
输入共若干行，第1行只包含1个整数 n 表示有 n 个提问。接下来 n 行每行包含两个整数 p 和 q。

【输出文件】 输出文件名为 clever.out。
输出共若干行，如果 p / q 为有限小数，则输出"Finite"，否则输出 “Infinite” ( 输出不包含引号 )。

【样例输入】
1
4 12

【样例输出】Infinite

【数据范围】 对于 100%的数据，1 ≤ n ≤ 10⁶，1 ≤ p，q ≤ 10¹⁸

2.1.第一步生成.in文件：产生随机数据的 random.cpp

#include<bits/stdc++.h>
using namespace std;

int random(int n) {
	return (long long) rand() * rand() % n;
}

int main() {
	freopen("clever.in", "w", stdout);
	srand(time(0));
	
	int  n, m = 150, p, q;   // 这题一定要将数据变小一点，否则很难验证
	n =  random(5) + 1;
	
	cout << n << endl;

	while (n --) {
		 p = random(m);
		 
		 while (true) {
		 	q = random(m);
		 	if (q) break;
		 }	
			
		 cout << p << ' ' << q << endl;
	}
	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

2.2.第二步生成.ans文件—朴素算法 (模拟, clever.bf.cpp) O(10³*n）

• 模拟小学除法竖式运算，统计小数的位数 cnt。
• 若小数位数超过1000位，则可以看成无限(在数学上不严谨，但更符合实际)
• 观察数据，若统计1000位小数，则总计算量10⁹，易超时。若统计100位又感觉不保险(实际评测时100位完全能AC了)。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

bool isuit(LL p, LL q) {
	p = p % q;
	int cnt = 0;
	while (p != 0) {
		p = p * 10 % q;
		cnt ++;
		if (cnt > 1000) return false;
	}
	return cnt <= 1000;
}

int main() {
	freopen("clever.in", "r", stdin);
	freopen("clever.ans", "w", stdout);
	int n;
	cin >> n;
	
	LL p, q;
	while (n --) {
		cin >> p >> q;
		if(isuit(p, q)) {
			cout << "Finite" << endl;
		} else {
			cout << "Infinite" << endl;
		}
	}

	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

2.3.第三步生成.out文件—高效正解 (数学，clever.cpp) O(n）

• 首先约掉分子p和分母q的共同部分，即p和q的最大公约数gcd(p, q)
• 由于只判断是否无限，因此小数的位数只要有限次就好。也就是说分子p可以一直p = p *10，每乘一次10就相当于小数多一位。而10 = 2 * 5, 所以约万分的分母剩下的 2 和 5 也可以删掉。
• 分母 q 去掉和分子共同部分，以及若干个2和5后，如果还不等于 1，那么就是无限小数了。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

LL gcd(LL a, LL b) {
	LL t;
	while (a % b != 0) {
		t = a % b;
		a = b;
		b = t;
	}
	return b;
}
int main() {
	freopen("clever.in", "r", stdin);
	freopen("clever.out", "w", stdout);

	int n;
	cin >> n;

	LL p, q;
	while (n --) {
		cin >> p >> q;

		q /= gcd(p, q);
		while (q % 2 == 0) q /= 2;
		while (q % 5 == 0) q /= 5;

		if(q == 1) {
			cout << "Finite" << endl;
		} else {
			cout << "Infinite" << endl;
		}
	}
	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

2.4.第四步—开始对拍(NOILinux2.0环境下自动对比.ans与.out)

#! /bin/bash
g++ random.cpp -o random
g++ sneak.bf.cpp -o bf
g++ sneak.cpp -o sol

for i in {1..10000}
do
	./random
	./bf
	./sol
	
	if diff ./sneak.ans ./sneak.out
	then
		printf "AC "
	else 
		echo "WA"
		exit 0
	fi
done
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.铺设道路(road.cpp)—2018年提高组

【问题描述】 春春是一名道路工程师，负责铺设一条长度为 n 的道路。铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区域，一开始，第 i 块区域下陷的深度为 d_i 。
春春每天可以选择一段连续区间 [L, R]，填充这段区间中的每块区域，让其下陷深度减少 1。在选择区间时，需要保证区间内的每块区域在填充前下陷深度均不为 0 。春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为 0 。

【输入文件】输入文件名为 road.in。
输入文件包含 2 行，第 1 行包含一个整数 n，表示道路的长度。 第 2 行包含 n 个整数，相邻两数间用一个空格隔开，第 i 个整数为 d_i 。

【输出文件】输出文件名为 road.out。输出文件仅包含 1 个整数，即最少需要多少天才能完成任务。

【样例输入】
6
4 3 2 5 3 5

【样例输出】 9

【样例说明】 一种可行的最佳方案是，依次选择：
[1 , 6]、[1 , 6]、[1 , 2]、[1 , 1]、[4 , 6]、[4 , 4]、[4 , 4]、[6 , 6]、[6 , 6]。

【数据范围】 对于 30% 的数据，1 ≤ n ≤ 10；对于 100% 的数据，1 ≤ n ≤ 100000 , 0 ≤ d_i ≤ 10000。

3.1.第一步生成.in文件：产生随机数据的 random.cpp

#include<bits/stdc++.h>
using namespace std;

int random(int n) {
	return (long long) rand() * rand() % n;
}

int main() {
	freopen("sneak.in", "w", stdout);
	srand(time(0));
	
	int n = 1e9;   // 一般为了便于自己验证答案，尽量生成小点的数据

	int t, s, x;

	t = random(n);

	while (true) {
		s = random(n);
		if (2 <= s) break;
	}

	x = random(n);

	cout << t << ' ' << s << ' ' << x << endl;
	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

3.2.第二步生成.ans文件—朴素算法 (模拟, clever.bf.cpp) O(10³*n）

• 模拟小学除法竖式运算，统计小数的位数 cnt。
• 若小数位数超过1000位，则可以看成无限(在数学上不严谨，但更符合实际)
• 观察数据，若统计1000位小数，则总计算量10⁹，易超时。若统计100位又感觉不保险(实际评测时100位完全能AC了)。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

bool isuit(LL p, LL q) {
	p = p % q;
	int cnt = 0;
	while (p != 0) {
		p = p * 10 % q;
		cnt ++;
		if (cnt > 1000) return false;
	}
	return cnt <= 1000;
}

int main() {
	freopen("clever.in", "r", stdin);
	freopen("clever.ans", "w", stdout);
	int n;
	cin >> n;
	
	LL p, q;
	while (n --) {
		cin >> p >> q;
		if(isuit(p, q)) {
			cout << "Finite" << endl;
		} else {
			cout << "Infinite" << endl;
		}
	}

	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

3.3.第三步生成.out文件—高效正解 (数学，sneak.cpp) O(1）

• 观察叶子怒吼时间点不难发现：所有怒吼时间点-t后为 0 s s+1 2s 2s+1 3s … 规律不言而喻，但要注意 t + 1时刻的特判
• 由于只需要一个if语句，时间复杂度为O(1)

#include<bits/stdc++.h>
using namespace std;

int main() {
	freopen("sneak.in", "r", stdin);
	freopen("sneak.out", "w", stdout);

	int t , s , x ;
	cin >> t >> s >> x ;

	t = x - t;

	if (t % s == 0 || t % s == 1 && t != 1) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}
	
	return 0 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.4.第四步—开始对拍(NOILinux2.0环境下自动对比.ans与.out)

#! /bin/bash
g++ random.cpp -o random
g++ sneak.bf.cpp -o bf
g++ sneak.cpp -o sol

for i in {1..10000}
do
	./random
	./bf
	./sol
	
	if diff ./sneak.ans ./sneak.out
	then
		printf "AC "
	else 
		echo "WA"
		exit 0
	fi
done
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4.火星人(martian.cpp)—2004年普及组

【问题描述】 人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的：首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。火星人用一种非常简单的方式来表示数字 — 掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为 1, 2, 3, ⋯⋯ 。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指 ― 拇指、食指、中指、无名指和小指分别编号为 1, 2, 3, 4 和 5，当它们按正常顺序排列时，形成了 5 位数 12345，当你交换无名指和小指的位置时，会形成 5 位数 12354，当你把五个手指的顺序完全颠倒时，会形成 54321，在所有能够形成的 120 个 5 位数中，12345 最小，它表示 1；12354 第二小，它表示 2；54321 最大，它表示 120。下表展示了只有 3 根手指时能够形成的 6 个 3 位数和它们代表的数字：

​ 现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

【输入格式】 输入文件名为 martian.in。
输入文件包含 3 行：第 1 行包含 1 个正整数 N，表示火星人手指的数目。第 2 行是 1 个正整数 M，表示要加上去的小整数。下 1 行是 1 到 N 这 N 个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

【输出文件】 输出文件名为 martian.out。
输出文件共 1 行包含 N 个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。

【样例输入】
5
3
1 2 3 4 5

【样例输出】1 2 4 5 3

【数据范围】
对于 30% 的数据，N ≤ 15。
对于 60% 的数据，N ≤ 50。
对于 100% 的数据，N ≤ 10000， M ≤ 100。

4.1.第一步生成.in文件：产生随机数据的 random.cpp

#include<bits/stdc++.h>
using namespace std;

int random(int n) {
	return (long long) rand() * rand() % n;
}

int main() {
	freopen("sneak.in", "w", stdout);
	srand(time(0));
	
	int n = 1e9;   // 一般为了便于自己验证答案，尽量生成小点的数据

	int t, s, x;

	t = random(n);

	while (true) {
		s = random(n);
		if (2 <= s) break;
	}

	x = random(n);

	cout << t << ' ' << s << ' ' << x << endl;
	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

4.2.第二步生成.ans文件—朴素算法 (模拟, clever.bf.cpp) O(10³*n）

• 模拟小学除法竖式运算，统计小数的位数 cnt。
• 若小数位数超过1000位，则可以看成无限(在数学上不严谨，但更符合实际)
• 观察数据，若统计1000位小数，则总计算量10⁹，易超时。若统计100位又感觉不保险(实际评测时100位完全能AC了)。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

bool isuit(LL p, LL q) {
	p = p % q;
	int cnt = 0;
	while (p != 0) {
		p = p * 10 % q;
		cnt ++;
		if (cnt > 1000) return false;
	}
	return cnt <= 1000;
}

int main() {
	freopen("clever.in", "r", stdin);
	freopen("clever.ans", "w", stdout);
	int n;
	cin >> n;
	
	LL p, q;
	while (n --) {
		cin >> p >> q;
		if(isuit(p, q)) {
			cout << "Finite" << endl;
		} else {
			cout << "Infinite" << endl;
		}
	}

	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

4.3.第三步生成.out文件—高效正解 (数学，sneak.cpp) O(1）

• 观察叶子怒吼时间点不难发现：所有怒吼时间点-t后为 0 s s+1 2s 2s+1 3s … 规律不言而喻，但要注意 t + 1时刻的特判
• 由于只需要一个if语句，时间复杂度为O(1)

#include<bits/stdc++.h>
using namespace std;

int main() {
	freopen("sneak.in", "r", stdin);
	freopen("sneak.out", "w", stdout);

	int t , s , x ;
	cin >> t >> s >> x ;

	t = x - t;

	if (t % s == 0 || t % s == 1 && t != 1) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}
	
	return 0 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.4.第四步—开始对拍(NOILinux2.0环境下自动对比.ans与.out)

#! /bin/bash
g++ random.cpp -o random
g++ sneak.bf.cpp -o bf
g++ sneak.cpp -o sol

for i in {1..10000}
do
	./random
	./bf
	./sol
	
	if diff ./sneak.ans ./sneak.out
	then
		printf "AC "
	else 
		echo "WA"
		exit 0
	fi
done
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19