欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

jzoj5827 [省选模拟2018.8.18]政治正确 爬山算法

程序员文章站 2024-02-12 22:46:16
...

Description


好长啊
jzoj5827 [省选模拟2018.8.18]政治正确 爬山算法
jzoj5827 [省选模拟2018.8.18]政治正确 爬山算法
jzoj5827 [省选模拟2018.8.18]政治正确 爬山算法
jzoj5827 [省选模拟2018.8.18]政治正确 爬山算法

Solution


这道题看起来就像是退火
膜一波题解:

           NOI2010出现了一道穷凶极恶的题,叫成长快乐。
           这道题类似于成长快乐,但是更简单一点。该题使用模拟退火或者爬山等算法是可以得到很高的分数的,同时只需 要一点小小的手段就可以轻松得到满分。
           我们需要小化一个长相奇怪的函数。搞清楚这个函数究竟在描述什么也许要点时间,如果没有因为题面太恶心而 放弃的话,我们不难发现,这个函数可以看成 维空间中有 个点和一个球壳,我们要在球壳内部找到一个点,使 得所有点和球壳给这个点施加的影响总和小。
           实际上这个总影响一定可以小化为0的。下面将证明这一点。
           所有点和球壳给空间中任意一点的影响可以看成是力,因为公式中对于每个政治问题的影响可以看成是力正交分解 后在每个正交基上的分量。同时,这样的力一定是保守力,即选择相同的起点和重点,无论通过什么路线移动这个 点,该点受外力做功相同,因此整个立场是保守力场。所以我们可以想象出这个空间中的势能的分布。并且我们知 道,靠近球壳的地方势能区域正无穷,政客代表的点势能也趋近正无穷。所以假设你在球壳内随便放入一个小球, 小球会沿着势能下降快的方向加速。终,由于阻力的作用,小球会停在某个势能的极小值处,而这个地方的受 力一定为0,可以想象出,球壳内至少存在一个这样的点。
           小球的滚动可以当做就是爬山算法的过程,因此,我们在爬山时不需要再枚举怎样更改政治主张,而是直接沿着受 影响的反方向成比例改变政治主张,这个方向一定是优的,沿着这个方向走,终我们将会达到受影响为0的 点。 

考虑到一定存在一条通往最优解的路径,因此我们爬山就可以

Code


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

const int N=200005;
const double eps=0.00001;

int n,m;

struct pos {
    double a[11];
    pos operator +(pos b) {
        pos c;
        rep(i,1,m) c.a[i]=b.a[i]+a[i];
        return c;
    }
} now,prt,p[N];

double v[N],d[N],f[N][11],ans=10000.0;

 double get() {
    return (double)(rand()%10000)*0.0001;
}

 double calc(pos x) {
    double ret=0,g=0;
    rep(i,1,m) g+=x.a[i]*x.a[i];
    if (!g||g-1>eps) return ans;
    rep(j,1,n) {
        d[j]=0;
        rep(i,1,m) d[j]+=(p[j].a[i]-x.a[i])*(p[j].a[i]-x.a[i]);
    }
    rep(j,1,n) rep(i,1,m) {
        f[j][i]=v[j]*(p[j].a[i]-x.a[i])/d[j];
    }
    rep(i,1,m) {
        double tmp=x.a[i]/(1-g);
        rep(j,1,n) tmp+=f[j][i];
        ret+=fabs(tmp);
    }
    if (ret<ans) {
        ans=ret; prt=x;
    }
    return ret;
}

pos gen(pos now,double t) {
    pos ret;
    rep(i,1,m) ret.a[i]=now.a[i]+(rand()*2-1)*t;
    return ret;
}

void solve() {
    double t=900.0; now=prt;
    double rec=calc(now);
    while (t>0.001) {
        pos tar=gen(now,t);
        double tmp=calc(tar);
        double delta=rec-tmp;
        if (delta>0) {
            now=tar;
            rec=tmp;
        }
        t*=0.8;
    }
}

int main(void) {
    freopen("politics.in","r",stdin);
    freopen("politics.out","w",stdout);
    srand(19260817);
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%lf",&v[i]);
    rep(i,1,n) rep(j,1,m) {
        scanf("%lf",&p[i].a[j]);
    }
    ans=calc(prt);
    solve();
    rep(i,1,m) printf("%.5lf ", prt.a[i]);
    return 0;
}
相关标签: jzoj