题解 P2571 【[SCOI2010]传送带】

XZYQvQ · 2018-03-27 22:22:04 · 题解

//安利一下自己的博客啦：http://www.k-xzy.xyz/archives/4979

Ps：几万年前退役的我看了看评论发现居然还有人看这篇文章，并且提出博客地址有误的问题。啊，确实如此，我退役当天博客就关闭啦，但是我的一位好心的同学 Remmina 要走了网站数据并且一直当自己的博客开着，我的文章也都能在里面找到，地址是 https://www.mina.moe。因此这篇文章也可以在https://www.mina.moe/archives/4979上找到。在此也特别感谢 Remmina 同学，也感谢各位耐心阅读一个早就凉透的OIer在最美好的时光写下的这篇“不务正业”的文章。

1. 题目

传送门=￣ω￣=

2. 题解

网上基本上所有Dalao都是写的“三分套三分”Orz

（好像WJMZBMR写的是模拟退火，为啥我一开始写模拟退火挂了呢QvQ可能我太弱了）

先讲下这题吧。

首先lxhgww的路径一定是从A点上传送带AB，走x个单位时间(0\leq x\leq \frac{AB}{P})，再下AB传送带，徒步走上CD传送带（不一定是在C点上传送带），走y个单位时间到达D点(0\leq y\leq \frac{CD}{Q})

设用时为f(x,y)（x,y的意义见上文）

则：

设f1(t)表示从A点出发，沿着AB走t个单位时间后到达的坐标。

设f2(t)表示从D点出发，沿着DC走t个单位时间后到达的坐标。

那么：

（dis表示求两点之间的欧几里得距离）

好的，现在这个问题已经转化为了求一个二元函数的最小值

可以把函数放到三维空间里看成一个物体，要在一个矩形区域内找物体的最低点。

。。。

写挂模拟退火以后我就写了个粒子群优化算法。。。

这算法真NB啊，什么数学推导都不需要，完全把函数当做随机函数看都能过掉！

这个算法是模仿生物（鸟类）捕食的过程。把一堆粒子随机撒在函数定义域内，然后每次找出所有粒子中所在位置对应的函数值最优的粒子，并且让大家都尽量向这里加速。

每个粒子都是有自己的惯性的，这样可以增加随机性，以免卡在局部最优解导致答案错误。

总之就是模拟真实的自然界啦。。。

具体很难说清楚，可以去网上搜一下这个算法，很玄妙的QvQ

但是好像网上很少有（或者说可能根本没有）把粒子群优化算法这种人工智能算法应用于OI竞赛的，所以这里发一下代码，里面会写上注释的，还是看代码比较好懂=。=（其实是手缝针啦打字有点不舒服）

另外实验结果表明，粒子群算法更注重粒子个数。。。像我一开始那样开20个粒子就冲上去爆〇的做法真的不可取QvQ

代码：

#include <bits/stdc++.h>

#define BS (505)//粒子数组大小
#define eps (1e-8)

using namespace std;

const int cnt = 500;//粒子个数

struct vec//向量
{
    double x, y;
    vec operator + (const vec oth) const
    {
        return (vec){x + oth.x, y + oth.y};
    }
    vec operator - (const vec oth) const
    {
        return (vec){x - oth.x, y - oth.y};
    }
    vec operator * (const double d) const
    {
        return (vec){x * d, y * d};
    }
    vec operator / (const double d) const
    {
        return (vec){x / d, y / d};
    }
};

vec A, B, C, D, P1, P2;

double P, Q, R, rx, ry;

vec f1(double x) {return A + P1 * x;}//和上文定义的f1意义相同

vec f2(double x) {return D + P2 * x;}//和上文定义的f2意义相同

double Squ(double a) {return a * a;}

double dis(vec a, vec b)//求a,b的欧几里得距离
{
    return sqrt(Squ(a.x - b.x) + Squ(a.y - b.y));
}

double f(double x, double y)//和上文定义的f意义相同
{
    return x + y + dis(f1(x), f2(y)) / R;
}

double Rand() {return (double)rand() / RAND_MAX;}//返回一个[0,1]的随机实数

struct Bird {double vx, vy, x, y, f, pb, pbx, pby;} b[BS];//粒子们

//vx,vy是速度向量，x,y是位置向量，f是当前位置的函数值，pb是该粒子历史最优值

double w = 1, gb = 1e233, gbx, gby;

//w是精度权重， gb是全局目前最优值， gbx,gby是取到全局最优值时的自变量x,y

void Update(int a)//更新粒子a的状态，这里具体原理请见算法实现原理
{
    b[a].vx = b[a].vx * w + Rand() * w * (gbx + b[a].pbx - b[a].x * 2);
    b[a].vy = b[a].vy * w + Rand() * w * (gby + b[a].pby - b[a].y * 2);
    //b[a].v * w是因为有惯性，另外的项则是尽量像更优解靠近
    b[a].x += b[a].vx, b[a].y += b[a].vy;//更新位置向量
    //下面4行是防止粒子出界，出界则反弹回来（这里我没在网上找到相关资料介绍如何处理出界，所以是自己YY的）
    if (b[a].x < 0) b[a].x = 0, b[a].vx = -b[a].vx;
    if (b[a].y < 0) b[a].y = 0, b[a].vy = -b[a].vy;
    if (b[a].x > rx) b[a].x = rx, b[a].vx = -b[a].vx;
    if (b[a].y > ry) b[a].y = ry, b[a].vy = -b[a].vy;
    b[a].f = f(b[a].x, b[a].y);//计算当前位置函数值
    if (b[a].f < b[a].pb)//更新局部最优解
        b[a].pbx = b[a].x, b[a].pby = b[a].y, b[a].pb = b[a].f;
}

int main(int argc, char const* argv[])
{
    scanf("%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y), P1 = B - A;
    scanf("%lf%lf%lf%lf", &C.x, &C.y, &D.x, &D.y), P2 = C - D;
    scanf("%lf%lf%lf", &P, &Q, &R), srand(P + Q + R);
    rx = dis(B, A) / P, ry = dis(D, C) / Q;
    if (!rx) P1.x = P1.y = 0; else P1 = P1 / rx;//特判传送带是一个点的情况
    if (!ry) P2.x = P2.y = 0; else P2 = P2 / ry;
    for (int i = 1; i <= cnt; i += 1)//随机撒点
    {
        b[i].x = b[i].pbx = Rand() * rx, b[i].y = b[i].pby = Rand() * ry;
        b[i].f = b[i].pb = f(b[i].x, b[i].y);
        b[i].vx = b[i].vy = 0;
        if (gb > b[i].pb) gbx = b[i].pbx, gby = b[i].pby, gb = b[i].pb;
    }
    for (int p = 1; p <= 900; p += 1, w *= 0.99)//迭代900次，0.99的900次方已经对答案无影响
        for (int i = 1; i <= cnt; i += 1)
            if (Update(i), gb > b[i].pb)
                gbx = b[i].pbx, gby = b[i].pby, gb = b[i].pb;//更新全局最优解
    printf("%.2f\n", gb);
    return 0;
}