专栏文章

T637074 题解

__j_o_k_e_r_
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miosrl57
此快照首次捕获于
2025/12/03 00:33
3 个月前
此快照最后确认于
2025/12/03 00:33
3 个月前
查看原文
本题本来要由 xwx123456 提供一道随机化题目（原因众所周知），但 xwx123456 有其他事，改为由 _j_o_k_e_r_ 提供，仍有随机化做法，预估难度为绿。
注意到题目限制比较灵活（改了又改），很难统一构造方案，所以我们充分发扬人类智慧，用随机化，把点随机出来，但也不是乱随机，是有一定道理的随机。
前 n−1n-1 个点要求比较少，只有一个限制：总长不超过 CC。举个例子，n=3,C=12n=3,C=12，设当前路程和为 cc，如下图：
刚开始什么也没有，c=0c=0，科比从家出发。现在随机出来一个点 (3,0)(3,0)：
此时 c=(0−0)2+(3−0)2=3c=\sqrt{(0-0)^2+(3-0)^2}=3，我们再随机出来一个点 (5,0)(5,0)。
此时 c=3+(5−0)2+(3−0)2=3+34≈8.831c=3+\sqrt{(5-0)^2+(3-0)^2}=3+\sqrt{34}\approx 8.831，我们要求 C=12C=12，并没有超过，但这时候我们已经知道这样不行了。因为最后要回到原点，两点之间，线段最短，所以回到原点至少需要走 55，即最终 c≥8.831+(5−0)2+(0−0)2c \ge 8.831+\sqrt{(5-0)^2+(0-0)^2}，即 c≥13.831c \ge 13.831，这不满足 C=12C=12 的要求，所以我们重新随机一个点 (3,3)(3,3)：
此时 c=3+(3−3)2+(3−0)2=6c=3+\sqrt{(3-3)^2+(3-0)^2}=6，(3,3)(3,3) 与原点之间的距离为 (3−0)2+(3−0)2=32≈4.243\sqrt{(3-0)^2+(3-0)^2}=3\sqrt{2}\approx 4.243，最终 c≥6+4.243=10.243c \ge 6+4.243=10.243，符合要求，继续。
重点：此时已经有了 22 个点，再有 11 个点就够了，设最后一个点的坐标为 (a,b)(a,b)，倒数第二个点的坐标为 (x,y)(x,y)，dis(a,b,x,y)dis(a,b,x,y) 表示坐标系上 (a,b)(a,b) 与 (x,y)(x,y) 之间的距离，最后一个点需要满足：
C−Eps≤c+dis(x,y,a,b)+dis(a,b,0,0)≤C+EpsC-Eps \le c+dis(x,y,a,b)+dis(a,b,0,0) \le C+Eps
其中 EpsEps 为题目给的极小值 10−410^{-4}。因为 EpsEps 极小，所以我们干脆让上面的一堆等于 CC，EpsEps 的误差留给浮点数的计算。
∴c+dis(x,y,a,b)+dis(a,b,0,0)=C\therefore c+dis(x,y,a,b)+dis(a,b,0,0)=C ∴c+(a−x)2+(b−y)2+a2+b2=C\therefore c+\sqrt{(a-x)^2+(b-y)^2}+\sqrt{a^2+b^2}=C
注意到 c,C,x,yc,C,x,y 为已知数，有 a,ba,b 两个未知数，只有一个方程，所以有无数组解，我们只需要其中一组或两组（原因见下）解就够了，所以不妨令 a=0a=0，解出 bb，再令 b=0b=0，解出 aa，就有两组解了：
{a=0b=x2+y2−(C−c)22y−2(C−c)\begin{cases} a=0\\b=\dfrac{x^2+y^2-(C-c)^2}{2y-2(C-c)} \end{cases} {a=x2+y2−(C−c)22x−2(C−c)b=0\begin{cases} a=\dfrac{x^2+y^2-(C-c)^2}{2x-2(C-c)} \\b=0\end{cases}
注意到有分数，分母不能为 00，所以如果 2y−2k=02y-2k=0 就用第二组解，不然就用第一组解。
带入上面的例子 x=3,y=3,C=12,c=6x=3,y=3,C=12,c=6 得 a=0,b=3a=0,b=3：
然后就可以敲代码了：
CPP
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<random>
#include<queue>
#include<ctime>
#include<map>
#define intu unsigned long long
#define intt long long
#define dlel long double
#define dle double
using namespace std;
const int Imax=0x7fffffffL;
const long long LLmax=0x7fffffffffffffffLL;
const dle Eps=1e-4;
mt19937 _rand(time(0));
dle Mod;
int n;
dle C;
dle c;
dle a,b,x,y;
dle dis(dle x1,dle y1,dle x2,dle y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}//两点间距离
int cnt;
map<dle,map<dle,bool> > mp;//记录某个点是否走过
dle Rand(dle p)//生成[0,p] 的浮点随机数
{
	int m=_rand()%3;
	dle res=_rand()/pow(10,m); 
	return res-((int)(res/p))*p;
}
int main()
{
	scanf("%d%lf",&n,&C);
	n++;
	Mod=2*sqrt(C/3.14);//玄学？
	cnt=1;
	mp[0][0]=1;
	while(1)
	{
		if(cnt==n-1)
		{
			dle k=C-c;
			a=b=0;
			if(fabs(x-k)<=Eps) b=(x*x+y*y-k*k)/(2*y-2*k); 
			else a=(x*x+y*y-k*k)/(2*x-2*k);
			c+=dis(x,y,a,b)+dis(a,b,0,0);
			printf("%lf %lf",a,b);
			return 0;
		}
		a=b=Mod-0.001;
		while(1)
		{
			a=Rand(a-0.001);
			b=Rand(b-0.001);
			if(cnt)
			{
				if(!a&&!x)//直走或调头
				{
					a=b=Mod-0.001;
					continue;
				}
				else if(fabs(b/a-y/x)<=Eps)//直走或调头
				{
					a=b=Mod-0.001;
					continue;
				}
			}
			if(c+dis(x,y,a,b)+dis(a,b,0,0)<C&&!mp[a][b])
			{
				mp[a][b]=1;
				break;
			}
		}
		printf("%lf %lf\n",a,b);
		c+=dis(x,y,a,b);
		x=a;
		y=b;
		cnt++;
	}
	return 0;
}
当然有其它做法，你完全可以把它当数学题做，用到三角函数，比较考验思维和数学功底，但难度还是在绿左右。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...