对拍 。。。

本蒟蒻在zxp大佬的指导下学习了对拍

好像没什么好记的， 那就走下形式， 放一下模板吧！

对拍要有四个程序

分别是

1. rd(求随机数据的)
2. std(用万能算法暴力求出的真确答案)
3. my(自己的程序求出的答案)
4. compare(比较std和my)

• 本题以 洛谷 P1115 最大子段和为例
• 为了保证阅读效率，减少了一些不重要的函数，如read（)...

---

---

rd

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
int rd(int L,int R) {
	return rand()%(R-L+1) + L;
}
int a[N];
int main()
{
	srand((unsigned)time(0));
	int n = 1e4;
	for(int i=1;i<=n;++i) a[i] = rd(-1e5,1e5);
	printf("%d\n",n);
	for(int i=1;i<=n;++i) printf("%d ",a[i]);
	cout << endl;
	return 0;
}

---

std

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
int a[N],sum[N];
signed main()
{
	int n = read();
	for(int i=1;i<=n;++i) a[i] = read();
	for(int i=1;i<=n;++i) sum[i] = sum[i-1] + a[i];
	int ans = -INF;
	for(int l=1;l<=n;++l) {
		for(int r=l;r<=n;++r) {
			int s = sum[r] - sum[l-1];
			ans = max(ans, s);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

---

my

#include<bits/stdc++.h>
using namespace std;
int N = 2e5+7;
int n;
int a[N];
signed main()
{
	n = read();
	for(int i=1;i<=n;++i) a[i] = read();
	int ans = -INF, cnt = 0, res = 0;
	for(int i=1;i<=n;++i) {
		res += a[i]; ++cnt;
		if(cnt > 0) ans = max(ans, res);
		if(res < 0) res = 0, cnt = 0;
	}
	printf("%lld\n",ans);
	return 0;
}

---

compare

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define y1 zzzzzzzzz
#define INF 0x3f3f3f3f
using namespace std;
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch = getchar(); }
	while(ch>='0'&&ch<='9') { x = (x<<3)+(x<<1)+(ch^48); ch = getchar(); }
	return x * f;
}
int main()
{
	while(true) {
		system("rd.exe > rd.txt");
        //把 rd.exe得出的随机数载入rd.txt
		system("my.exe < rd.txt > x.txt");
		system("std.exe < rd.txt > y.txt");
        //把使用 rd.txt 为输入数据的 my.exe 的输出结果载入x.txt 
        //把使用 rd.txt 为输入数据的 std.exe 的输出结果载入x.txt 
		if(system("fc x.txt y.txt")) break;//若x.txt和y.txt相同，就返回0 
	}
	return 0;
}

---

以上就是全部内容,相信众为访客可轻易理解...

若有不妥之处,请私信我，我尽量及时改正。

若有错误之处,请私聊 zxp大佬，我还会改正。