jzoj5827 [省选模拟2018.8.18]政治正确 爬山算法
程序员文章站
2024-02-12 22:46:16
...
Description
好长啊
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;
}
上一篇: jzoj5844 c 倍增