充满mo力的mo拟退火恒WA2,3,8,9 60pts玄关
查看原帖
充满mo力的mo拟退火恒WA2,3,8,9 60pts玄关
160150
WxjzKK楼主2023/9/12 21:08
//【模板】模拟退火 
#include<bits/stdc++.h>
#define MAXN 15
using namespace std;
inline void read(int &n){
	int s=0,t=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') t=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=(s<<3)+(s<<1)+(c^48);c=getchar();
	}
	n=s*t;
}
inline void put(int n){
	if(n<0){
		putchar('-');n=-n;
	}
	if(n<10){
		putchar(n+48);return;
	}
	put(n/10);
	putchar(n%10+48);
}
int n;
double answ,pos[MAXN][MAXN],ans[MAXN],dans[MAXN],dis[MAXN];
inline double calc(double a[]){
	double res=0,sum=0;
	for(register int i=0;i<=n;++i){
		dis[i]=0;
		for(register int j=1;j<=n;++j){
			double dpos=pos[i][j]-a[j];
			dis[i]+=dpos*dpos;
		}
		//dis[i]=sqrt(dis[i]);
      //这里也不知道为什么,本来求距离要开根号,但是开了根号之后,充满mo力的mo拟退火就会跑到绝对值非常巨大的值,非常的充满mo力
		sum+=dis[i];
	}
	sum/=(n+1);
	for(register int i=0;i<=n;++i){
		double dpos=(sum-dis[i]);
		res+=dpos*dpos;
	}
	res/=(n+1);res=sqrt(res);
	return res;
}
inline void SA(){
	for(register double t=3000;t>1e-15;t*=0.995){
		for(register int i=1;i<=n;++i) dans[i]=ans[i]+(rand()*2-RAND_MAX)*t;
		double dw=calc(dans),d=dw-answ;
		if(d<0){
			for(register int i=1;i<=n;++i) ans[i]=dans[i];
			answ=dw;
		}
		else if(exp(-d/t)*RAND_MAX>rand()){
			for(register int i=1;i<=n;++i) ans[i]=dans[i];
			answ=dw;
		}
	}
}
int main(){
	srand(time(NULL));
	read(n);
	for(register int i=0;i<=n;++i)
		for(register int j=1;j<=n;++j){
			scanf("%lf",&pos[i][j]);ans[j]+=pos[i][j];
		}
	for(register int i=1;i<=n;++i) ans[i]/=(n+1);
	answ=calc(ans);
	SA();SA();SA();SA();
	for(register int i=1;i<=n;++i) printf("%.3lf ",ans[i]);
	putchar('\n');
	return 0;
}

2023/9/12 21:08
加载中...