题解：UVA1476 Error Curves 使用 SA 解决

· · 题解

我们来分析一下这个题。

就这么说，虽然你能够用这个那个数学方法来证明出这是一个单峰函数，但是很多时候如果没有“三分”这个标签，你压根就想不出来这道题是单峰函数。

所以我们可以用模拟退火来解决这道题（调参调了一天）。

这道题因为较为简单，所以可以设置较为激进的降温策略。初始温度设置一个最平常的 4000 就可以了。

其他的就跟 SA 的模板是差不多的了。

AC 代码：

#include <bits/stdc++.h>
using namespace std;
const double down=0.9943; // 可以设置激进一点的降温速度
int n;
struct node{
    double x,y,w;
}a[10005];
double dx,now;
double energy(double x)
{
    double tot=-1e20; // 注意 f(x) 可能为负数
    for(int i=1; i<=n; i++)
    {
        tot=max(tot,a[i].x*x*x+a[i].y*x+a[i].w);
    }
    return tot;
}
void SA()
{
    double t=4000;
    while(t>1e-17)
    {
        double tx=dx+(rand()*2-RAND_MAX)*t;
        if(tx<0) tx=(rand()%100);
        if(tx>1000) tx=(1000);

        double temp=energy(tx);
        double delte=temp-now;
        if(delte<0)
        {
            dx=tx;
            now=temp;
          }
        else if(exp(-delte/t)*RAND_MAX>rand())
        {
            dx=tx;
        }
        t*=down;
    }
}
void sjk()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].w;
    }
    dx=500;
    now=energy(dx);
    SA();
    cout<<fixed<<setprecision(4)<<energy(dx)<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--) sjk();
    return 0;
}

但是我们悲催的发现，只有吸氧可以过这个代码，不然只有 50 分。

怎么办！

打正解？No way！

温度？3000 就够！

降温速度？0.885 就行

ACcode（不吸氧）：

#include <bits/stdc++.h>
using namespace std;
const double down=0.885;
int n;
struct node{
    int  x,y,w;
}a[10005];
double dx,now;
double energy(double x)
{
    double tot=-1e20;
    for(int i=1; i<=n; i++)
    {
        tot=max(tot,a[i].x*x*x+a[i].y*x+a[i].w);
    }
    return tot;
}
void SA()
{
    double t=3000;
    while(t>1e-17)
    {
        double tx=dx+(rand()*2-RAND_MAX)*t;
        if(tx<0) tx=0;
        if(tx>1000) tx=(1000);

        double temp=energy(tx);
        double delte=temp-now;
        if(delte<0)
        {
            dx=tx;
            now=temp;
          }
        else if(exp(-delte/t)*RAND_MAX>rand())
        {
            dx=tx;
        }
        t*=down;
    }
}
void sjk()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].w;
    }
    dx=500;
    now=energy(dx);
    SA();
    cout<<fixed<<setprecision(4)<<energy(dx)<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--) sjk();
    return 0;
}

最后，让我们以一段有趣的笑话来结尾吧

一段 模拟退火

一台 电脑

一个夜晚

一个又 WA 又 TLE 的记录

管理员大大求通过 QAQ