作为一名OIer，我们都会参加各种各样的比赛或者模拟赛，然而并不是每次都能很完美地想到正解，但是打暴力混的那点分又远远不够，怎么办呢？
于是我在这里简单的讲几种骗分的算法，适用于最优化问题。
这种问题通常是让我们求解某个情景下的最优状态，方法也主要有两种：爬山和模拟退火。
爬山
这个算法……名字很奇怪，不过倒是一个贴切的比喻，我们可以把它比喻成一个失忆的攀登者在爬一座云雾缭绕的山，他不知道最高的峰在哪里，只能看清离自己很近的地方，所以他会尽可能往高处爬，爬到他周围的位置都比他目前所在的位置低，他就认为他爬到山顶了。
然而我们仔细一想，不对啊，这有可能是局部最优，不一定就是全局最优啊。这句话是没错，但是由于单次爬山的复杂度并不高，所以可以多次重复。每次随机选取一个起点，爬到不能爬为止，在多次爬山得到的值中选取最小的那一个，这样就有很大的几率能得到全局最优。实在过不了的调调参就过去了（滑稽
例题：Luogu P1337 【JSOI2004】平衡点 / 吊打XXX
这道题大概是一个挺经典的爬山/退火练习题吧，就是找到一个(x,y)，使$\sum ^{n}_{i=1}{\sqrt {(x_i-x)^2+(y_i-y)^2}*w_i}$最小。
基础思路就是每次随机一个起点，枚举四个方向，如果更优就接受，同时每次减小步数。然后调调参，卡卡精就过去了。
特别说明：如果不确定需要爬多少次可以尽可能开大，然后利用卡时在超时之前退出。
以下是代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
using namespace std;
const int N=2000000+110;
const int MAXN=50;
const double eps=1e-6;
il int read()
{
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
int n;
double ans=inf,X,Y;
struct hole
{
double x,y;
int weight;
};
hole A[N];
il double dis(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
il double get_weight(double x,double y)
{
double ret=0;
for(ri i=1;i<=n;i++)
ret+=dis(x,y,A[i].x,A[i].y)*A[i].weight;
return ret;
}
int main()
{
int t=clock();
srand((unsigned)time(NULL));
n=read();
for(ri i=1;i<=n;i++)
{
scanf("%lf%lf",&A[i].x,&A[i].y);
A[i].weight=read();
}
for(ri i=1;i<=5000;i++)
{
if(clock()-t>950000)
break;
double x=-10000+rand()%20000,y=-10000+rand()%20000;
double step=1000,k=get_weight(x,y);
while(step>eps)
{
double xi,yi;
for(ri i=1;i<=4;i++)
{
if(i==1)
xi=x+step,yi=y;
else if(i==2)
xi=x-step,yi=y;
else if(i==3)
xi=x,yi=y+step;
else if(i==4)
xi=x,yi=y-step;
double now=get_weight(xi,yi);
if(now<k)
x=xi,y=yi,k=now;
}
step=step*0.921;
}
if(k<ans)
X=x,Y=y,ans=k;
}
printf("%.3lf %.3lf",X,Y);
return 0;
}
模拟退火
就像字面上描述的那样，这个算法是对金属退火的模拟。
对于这个算法呢，如果说爬山中的那个攀登者是神志清晰的，那么这里面的那个攀登者就喝醉了酒。由于他神志不清，所以有一定的概率会往更低的方向爬，并且随着时间的推移，酒力逐渐消退，这个概率会越来越小。这样就有一定的概率跳出局部最优的陷阱，达到全局最优。
然而由于并不一定是全局最优，所以与爬山类似，需要做多次（不过好像并不是特别需要调参
这道题其实也比较基础，基本思路就是每次随机一个分组，然后降温过程中每次随机一个元素，将其放入和最小的组里，看结果是否更优。如果更优则接受，反之则以一定概率接受。
以下是代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using namespace std;
const int N=100000+110;
const ll inf=1ll<<50;
const int MAXN=110;
const double eps=1e-6;
const double deltaT=0.9;
il int read()
{
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
int n,m;
int a[MAXN],bel[MAXN],sum[MAXN];
double ave,ans=inf;
il void SimulatedAnnealing()
{
memset(sum,0,sizeof(sum));
double now=0,T=1926;
for(ri i=1;i<=n;i++)
{
bel[i]=1+rand()%m;
sum[bel[i]]+=a[i];
}
for(ri i=1;i<=m;i++)
now+=sqr(sum[i]-ave);
while(T>eps)
{
int P=min_element(sum+1,sum+1+m)-sum;
int X=1+rand()%n;
double pre=now;
now-=(sqr(sum[bel[X]]-ave)+sqr(sum[P]-ave));
sum[bel[X]]-=a[X];
sum[P]+=a[X];
now+=(sqr(sum[bel[X]]-ave)+sqr(sum[P]-ave));
if(now<pre||(exp((now-pre)/T)*RAND_MAX<rand()))
bel[X]=P;
else
now=pre,sum[bel[X]]+=a[X],sum[P]-=a[X];
T*=deltaT;
}
if(now<ans)
ans=now;
}
int main()
{
srand((unsigned)time(NULL));
n=read(),m=read();
for(ri i=1;i<=n;i++)
{
a[i]=read();
ave+=a[i];
}
ave/=m;
for(ri i=1;i<=1000;i++)
SimulatedAnnealing();
printf("%.2lf",sqrt(ans/m));
return 0;
}
到这里就基本讲完了，其他的这类算法还有蚁群、遗传等，不过由于不常用，这里就不讲了QwQ