随机函数
应该很简单，介绍三个最常用的。
-
rand()，会返回一个在 $[0,r]$ 内的随机整数。$r$ 为RAND_MAX，标准库中的宏，在 Windows 下取 $2^{15}-1$，在 Linux 下取 $2^{31}-1$。rand()效率较低。可使用
srand(seed)做种。配合time(0)。 -
mt19937，可用于快速生成高质量的在 $\left[0,2^{32}-1\right]$ 范围内的随机整数，返回值为unsigned int。定义方式：
1 2
#include<random> mt19937 Rand(time(0));
之后直接调用
Rand()生成整数即可，定义时填入的time(0)是为了做种。关于
mt19937_64mt19937_64是 $64$ 位的mt19937的实现，可生成 $\left[0,2^{64}-1\right]$ 范围内的整数，返回unsigned long long。 -
shuffle，用于随机打乱序列，时间复杂度 $\mathcal O(n)$。1
shuffle(a+1,a+n+1,Rand);
其中
Rand为随机数生成函数，推荐mt19937。
爬山算法
也称「梯度下降」。
考虑当前状态 $x$，$x$ 可以转移到一个新的状态 $y$，如果说 $y$ 的答案优于 $x$，则保留 $y$，否则保持 $x$ 不变。其实爬山算法就是贪心算法，最终会找到一个局部最优解。
因此当且仅当原问题单峰时，爬山算法可以保证得到正解。而你使用爬山算法，往往是因为你不会利用单峰的性质。
爬山算法引入温度参数，用于确定单次状态偏移量的大小。温度参数逐渐下降，偏移量也逐渐变小，最终趋近于最优解。降温参数接近于 $1$。具体而言，设温度参数 $t$、降温参数 $d$，则每次更新状态后令 $t\leftarrow dt$。同时，根据 $t$ 的大小来确定偏移量的大小。
luogu P1337 [JSOI2004] 平衡点 / 吊打XXX
即求 $n$ 个点的带权类费马点。
几何题，或者物理题。可以使用力的分解、正交分解或势能分析来解决。
计算合力方向，运用爬山算法向该方向偏移即可。
调参与卡时
爬山算法在降温参数过大时，可能会因为运行次数过多而超时。这时就需要修改降温参数以使得程序能够在限定时间内完成，即调参。
但是在有些时候，你可以通过在快要超时时输出当前最优解，称之为卡时。
注意：降温参数过低可能导致爬山算法答案错误。
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
constexpr const int N=1000;
constexpr const double eps=1e-6;
struct node{
int x,y,w;
}a[N+1];
int n;
double dist(pair<double,double>a,pair<double,double>b){
return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
void move(double &x0,double &y0,double op){
double deltaX=0,deltaY=0;
for(int i=1;i<=n;i++){
double d=dist({x0,y0},{a[i].x,a[i].y});
if(d==0){
continue;
}
deltaX+=a[i].w*(a[i].x-x0)/d;
deltaY+=a[i].w*(a[i].y-y0)/d;
}
double d=sqrt(deltaX*deltaX+deltaY*deltaY);
if(d==0){
return;
}
x0+=op*deltaX/d;
y0+=op*deltaY/d;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y>>a[i].w;
}
double x0=0,y0=0,op=10000*sqrt(2);
while(op>eps){
move(x0,y0,op);
op*=0.9;
}
cout<<fixed<<setprecision(3)<<x0<<' '<<y0<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
# 模拟退火
> Simulated Annealing，也称 SA 算法。
考虑爬山算法可能会陷入某个局部最优解中无法跳出，因此便有了**模拟退火**。模拟退火会**以一定概率跳出局部最优解**，从而寻找可能的全局最优解。
关于退火
退火是一种金属热处理工艺，指的是将金属缓慢加热到一定温度，保持足够时间，然后以适宜速度冷却。目的是降低硬度，改善切削加工性；消除残余应力，稳定尺寸，减少变形与裂纹倾向；细化晶粒，调整组织，消除组织缺陷。准确的说，退火是一种对材料的热处理工艺，包括金属材料、非金属材料。而且新材料的退火目的也与传统金属退火存在异同。
显然这一段都没什么用。
模拟退火引入温度参数，模拟金属退火的过程。虽然我并不觉得有什么联系。
参考代码
```cpp //#include<bits/stdc++.h> #include-
#include
