登录
← 返回首页 | 代码片段 › 1 基础算法 › 1.4 对拍 › 对拍 / 搜索
JSON MD

1.4 对拍

data fu
25 行
CPP JSON
【data】 随机数据生成器模板,用于对拍测试的输入生成。 核心函数: LL fu(无参数) — 核心算法函数 LL Rand(LL L,LL R) — 核心算法函数 说明:freopen("data.in","w",stdout); 适用场景:程序正确性验证(与暴力程序对比测试)
C++ 24 行 CPP
#include<bits/stdc++.h>
#define LL long long
#define Re register LL
using namespace std;
const LL inf=1000,N=20;
LL vis[inf+5];char A[N+5],B[N+5];
inline LL fu(){return rand()%2?-1:1;}
inline LL Rand(LL L,LL R){
	LL a=R-L+1;
	LL b=(LL)rand()*rand()%a+1;
	b=b*rand()%a+1;
	b=b*rand()%a+1;
	b=b*rand()%a+1;
	b=b*rand()%a+1;
	return L+b-1;
}
LL lo[N],tp[N];
int main(){
//	freopen("data.in","w",stdout);
	srand(time(0));
	Re n=rand()%N+1;
	printf("%lld 0\n",n);
	for(Re i=1;i<=n;++i)printf("%lld ",Rand(1,inf));
}
myprogram sakura
42 行
CPP JSON
【myprogram】 待测程序模板,与标准程序对拍验证正确性。 核心函数: void in(Re &x) — 核心算法函数 void sakura(无参数) — 后缀数组 核心结构体:QAQ0 关键配置: N=5e5+3 适用场景:程序正确性验证(与暴力程序对比测试)
C++ 41 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3;
const LL inf=4e18+5;
int n,opt,A[N],B[N];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct QAQ0{
	int x;LL g[N],S[N],dp[N];
	inline void sakura(){
		for(Re i=1;i<=n;++i)in(x),S[i]=S[i-1]+x,dp[i]=inf;
		dp[0]=0,g[0]=S[0];
		for(Re i=1,p=0;i<=n;++i){
			while(p+1<i&&2*S[p+1]-g[p+1]<=S[i])++p;
			dp[i]=dp[p]+(S[i]-S[p])*(S[i]-S[p]),g[i]=S[p];
//			printf("i=%d, p=%d\n",i,p);
//			for(Re j=0;j<=p;++j)
//				if(dp[i]>=(tmp=dp[j]+(S[i]-S[j])*(S[i]-S[j])))
//					dp[i]=tmp,g[i]=S[j];
		}
//		for(Re i=0;i<=n;++i)printf("dp[%d]=%lld\n",i,dp[i]);
		printf("%lld\n",dp[n]);
	}
}T0;
int main(){
//	freopen("456.txt","r",stdin);
	in(n),in(opt);
	if(n<=5000)T0.sakura();
	fclose(stdin);
	fclose(stdout);
	return 0;
}
std sakura
39 行
CPP JSON
【std】 标准程序(标程/暴力程序)模板,用作对拍的正确性基准。 核心函数: void in(Re &x) — 核心算法函数 void sakura(无参数) — 后缀数组 核心结构体:QAQ0 关键配置: N=5e5+3 说明:for(Re i=0;i<=n;++i)printf("dp[%d]=%lld\n",i,dp[i]);;freopen("456.txt","r",stdin); 适用场景:程序正确性验证(与暴力程序对比测试)
C++ 38 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3;
const LL inf=4e18+5;
int n,opt,A[N],B[N];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct QAQ0{
	int x,g[N];LL tmp,S[N],dp[N];
	inline void sakura(){
		for(Re i=1;i<=n;++i)in(x),S[i]=S[i-1]+x,dp[i]=inf;
		dp[0]=0,g[0]=0;
		for(Re i=1,p=0;i<=n;/*printf("i=%d, p=%d\n",i,p),*/++i)
			for(Re j=0;j<i;++j)
				if(S[i]-S[j]>=S[j]-S[g[j]]&&dp[i]>=(tmp=dp[j]+(S[i]-S[j])*(S[i]-S[j])))
					dp[i]=tmp,g[i]=j,p=j;
//		for(Re i=0;i<=n;++i)printf("dp[%d]=%lld\n",i,dp[i]);
		printf("%lld\n",dp[n]);
	}
}T0;
int main(){
//	freopen("456.txt","r",stdin);
	in(n),in(opt);
	if(n<=5000)T0.sakura();
	fclose(stdin);
	fclose(stdout);
	return 0;
}
对拍 system
21 行
CPP JSON
【对拍】 对拍(程序正确性测试)相关模板。 说明:break; 适用场景:程序正确性验证(与暴力程序对比测试)
C++ 20 行 CPP
#include<bits/stdc++.h>
#include<windows.h>
#define Re register int 
using namespace std;
int main(){
	Re sec=0.1,HYJ=0;// 随机数据生成时间,大约每0.1秒一次 
	sec*=1e3;
    while(1){
    	printf("第 %d 组数据:\n",++HYJ);
        system("data.exe>data.in");// 随机数据生成到文件 
        system("std.exe<data.in>std.out");// 运行标准程序 
        system("myprogram.exe<data.in>my.out");// 运行自己的程序(可能全WA但能跑通的程序)
        if(system("fc std.out my.out")){// 比较输出文件,fc比较文本文件不同返回1
            system("pause");
			printf("[corrupted string]");
            //break; 
        }
        Sleep(sec);
    }
}
已复制