之前的帖子似乎提到过题解中大部分都是爬山。
正经写模拟退火可能连样例都过不了。
实践发现特判掉随机到的点能产生的答案为零的情况就可以了。(为零过于离谱,干脆不跳过去)
就像这样:
void SA(){
db nx = sx,ny = sy;
for(db T = st;T >= ed;T *= dt){
db xx = nx + T * (2.0 * rand() - RAND_MAX);
db yy = ny + T * (2.0 * rand() - RAND_MAX);
int now = query(xx,yy),d = ans - now;
if(!now)continue;
if(d < 0)
sx = nx = xx,sy = ny = yy,ans = now;
else if(exp(-d / T) * RAND_MAX > rand())
nx = xx,ny = yy;
}
}