网站设计公司有用吗,wordpress 页面文件,网站开发流程的认识,百度资源平台链接提交正解又不会写#xff0c;又懒得去想 只好每次考试大大暴力#xff0c;维持一下生活了 ----------------------- P1337 [JSOI2004]平衡点 / 吊打XXX 题目描述 有n个重物#xff0c;每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞#xff0c;然后系在一起。… 正解又不会写又懒得去想 只好每次考试大大暴力维持一下生活了 ----------------------- P1337 [JSOI2004]平衡点 / 吊打XXX 题目描述 有n个重物每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞然后系在一起。图中X处就是公共的绳结。假设绳子是完全弹性的不会造成能量损失桌子足够高因而重物不会垂到地上且忽略所有的摩擦。 问绳结X最终平衡于何处。 注意桌面上的洞都比绳结X小得多所以即使某个重物特别重绳结X也不可能穿过桌面上的洞掉下来最多是卡在某个洞口处。 这道题是一道模你模拟退火的板子题 我是看这个大佬看懂的 我一开始看这个算法是拒绝的。你不能叫我玄学就玄学。 然鹅这是玄学的特技是特技的玄学。对于搜索偏分还是很好用的 提醒公式不要死磕 exp是计算自然对数次方的函数 参数是个玄学的东西要不断地摸索和联系 解不一定是最优但时间复杂度低 算法大概 从当前状态通过一个不断缩减的步长转移到下一个状态 然后计算待转移状态的优劣程度这个优劣程度就是能量 然后比当前状态优的话就贪心的进行转移 不优的话就根据那个鬼的公式。算概率转移 假ac代码 #includecstdio
#includeiostream
#includealgorithm
#includecstdlib
#includectime
#includecmath
const int maxn10100;
const double eps1e-14;
struct node
{int x,y;int w;
};
node pos[maxn];
int n;
double anx,any;
double calc(double x,double y)
{double res0;for(int i1;in;i){double pxx-pos[i].x;double pyy-pos[i].y;ressqrt(px*pxpy*py)*pos[i].w;}return res;
}
void simulate()
{double t250;while(teps){double nowxanx((rand()1)-RAND_MAX)*t;double nowyany((rand()1)-RAND_MAX)*t;double delta_Ecalc(nowx,nowy)-calc(anx,any);if(delta_E0)anxnowx,anynowy;else if(exp(-delta_E/t)*RAND_MAXrand())anxnowx,anynowy;tt*0.997;}
}
int main()
{srand(脸);scanf(%d,n);for(int i1;in;i){scanf(%d%d%d,pos[i].x,pos[i].y,pos[i].w);anxpos[i].x;anypos[i].y;}anx1.0*anx/n;any1.0*any/n;simulate();printf(%.3lf %.3lf,anx,any);
} 模拟退火对于我这种noip狗肯定是不会考 但是多一个偏分的技巧不是很好吗 随机化 随机化运用在搜索中枚举中。在运行次数足够多的情况下可以有效避免贪心的错误即使使用了贪心 07年noip的宝藏。 就可以使用这种方法骗分。 运行一次prim的时间很短我们可以多次运行 我们在使用优先队列选边时可以rand出一个概率来 然后再根据概率加进我们的生成树中去 转载于:https://www.cnblogs.com/Lance1ot/p/9495457.html
