正解又不会写，又懒得去想
只好每次考试大大暴力，维持一下生活了 ----------------------- P1337 [JSOI2004]平衡点 / 吊打XXX
题目描述
有n个重物，每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞，然后系在一起。图中X处就是公共的绳结。假设绳子是完全弹性的（不会造成能量损失），桌子足够高（因而重物不会垂到地上），且忽略所有的摩擦。
问绳结X最终平衡于何处。
注意：桌面上的洞都比绳结X小得多，所以即使某个重物特别重，绳结X也不可能穿过桌面上的洞掉下来，最多是卡在某个洞口处。
这道题，是一道模你模拟退火的板子题
我一开始看这个算法，是拒绝的。你不能叫我玄学就玄学。
然鹅这是玄学的特技，是特技的玄学。对于搜索偏分还是很好用的
提醒：公式不要死磕
exp是计算自然对数次方的函数
参数是个玄学的东西，要不断地摸索和联系
解不一定是最优，但时间复杂度低
算法大概：
从当前状态通过一个不断缩减的步长转移到下一个状态
然后计算待转移状态的优劣程度，这个优劣程度就是能量
然后比当前状态优的话，就贪心的进行转移
不优的话，就根据那个鬼的公式。算概率转移
假ac代码：
#include#include #include #include #include #include const int maxn=10100;const double eps=1e-14;struct node{ int x,y; int w;};node pos[maxn];int n;double anx,any;double calc(double x,double y){ double res=0; for(int i=1;i<=n;i++) { double px=x-pos[i].x; double py=y-pos[i].y; res+=sqrt(px*px+py*py)*pos[i].w; } return res;}void simulate(){ double t=250; while(t>eps) { double nowx=anx+((rand()<<1)-RAND_MAX)*t; double nowy=any+((rand()<<1)-RAND_MAX)*t; double delta_E=calc(nowx,nowy)-calc(anx,any); if(delta_E<0) anx=nowx,any=nowy; else if(exp(-delta_E/t)*RAND_MAX>rand()) anx=nowx,any=nowy; t=t*0.997; }}int main(){ srand(脸); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&pos[i].x,&pos[i].y,&pos[i].w); anx+=pos[i].x; any+=pos[i].y; } anx=1.0*anx/n; any=1.0*any/n; simulate(); printf("%.3lf %.3lf",anx,any);}
模拟退火对于我这种noip狗肯定是不会考
但是多一个偏分的技巧不是很好吗
随机化
随机化运用在搜索中，枚举中。在运行次数足够多的情况下，可以有效避免贪心的错误，即使使用了贪心
07年noip的宝藏。
就可以使用这种方法骗分。
运行一次prim的时间很短，我们可以多次运行
我们在使用优先队列选边时，可以rand出一个概率来
然后再根据概率加进我们的生成树中去