Warning: session_start(): open(/tmp/sess_f8fd1bbdc7958d5639212772119ddcf4, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: mkdir(): No space left on device in /data/wiki/lib/plugins/dw2pdf/vendor/mpdf/mpdf/src/Cache.php on line 19
Temporary files directory "/data/wiki/data/tmp/dwpdf/753/" is not writable

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:no_morning_training:weekly:week8 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:no_morning_training:weekly:week8

2020/07/18--2020/07/24


团队训练

暂无


王瑞琦

比赛

专题

冯宇扬

没有

常程

比赛

没有

专题

这一周在刷AC自动机的题来着,所以没有新的东西


本周推荐

王瑞琦

翻出来以前写的一道模拟退火入门题,温习了一下。

来源

洛谷P1337:平衡点

标签

模拟退火,数学

题意

给出桌面上n个洞的坐标,n个重物系绳分别穿过n个洞,求绳结最后的平衡位置。

题解

绳结平衡,即所受n个力达到平衡。
而当绳结处于一个非平衡点时,其所受合力方向必指向最后的平衡点,因此我们将绳结向该方向移动一段距离。
循环上述过程,每次移动的距离逐渐减少,最终绳结将“逼近”最后的平衡点。

代码

代码

#include <stdio.h>
#include <math.h>
#define abs(x) ((x) >= 0 ? (x) : (-(x)))
#define true 1
#define false 0
 
int main()
{
	int a[34][1001]={0};
	int n;
	int XF=true, YF=true;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d%d%d",&a[1][i],&a[2][i],&a[3][i]);
	double t=5000,tx,ty;
	double x=1,y=1;
	while (true)
	{
		tx=x;
		ty=y;
		double lx=0,ly=0,dist;
		for (int i=1;i<=n;i++)
		{
			dist=sqrt((a[2][i]-y)*(a[2][i]-y)+(a[1][i]-x)*(a[1][i]-x));
			if (dist==0) continue;
			lx=lx+a[3][i]/dist*(a[1][i]-x);
			ly=ly+a[3][i]/dist*(a[2][i]-y);
 
		}
		dist=sqrt(lx*lx+ly*ly);
		x=x+t/dist*lx;
		y=y+t/dist*ly;
		if (abs(tx-x)<0.00001&&abs( ty - y)<0.00001) break;
		if ((XF!=(x>tx))||(YF!=(y>ty))){
			XF=1-(x>tx);
			YF=1-(y>ty);
			t=t*0.9;
		}
	}
	printf("%.3lf %.3lf",x,y);
	getchar();
	getchar();
	return 0;
}

comment

比较入门的一道题,复习的时候却调了好久=。=
关于模拟退火还在学习当中…

冯宇扬

本周完全摸鱼

常程

推荐一道AC自动机的题吧 文本生成器

2020-2021/teams/no_morning_training/weekly/week8.1595583106.txt.gz · 最后更改: 2020/07/24 17:31 由 发源于