题解 P5544 【[JSOI2016]炸弹攻击1】

太菜，只会随机化算法。并不理解模拟退火玄学转移的$\exp$，于是就写了简短的爬山算法。 首先选一个点$A$，随机选一个在这个点周围的点$B$，如果点 B 的答案优于点 A，则转移。可以看出越到了后面我们的点 A 就越接近答案，所以我们在后期更新的幅度就比较小了。 至于如何实现的话，我们可以借鉴$\text{模拟退火}$，设定初始温度，温度越高，点 B 的期望距离就和点 A 越远。每次操作后进行降温，温度太低就终止。 具体看[luogu日报](https://www.luogu.com.cn/blog/Darth-Che/mu-ni-tui-huo-xue-xi-bi-ji) 所以其实爬山算法就是没有玄学转移的模拟退火 大体就是这样，随机化~~乱搞~~算法人人都会，需要一些技巧。 1. c++11/14/17 + O2 或者是rp。 2. 爬山算法可能会被限制在一个局部最优解上。不慌，跑上个几~~百千万~~遍爬山，每次的初始点随机乱搞，取最大值。对于此题来说 3. 由于算法复杂度玄学，我们采用卡时的方法来完成第二步。只要不到时限，我们就一直跑爬山。 4. 调参数，降温系数0.997左右，初始温度和最终温度随缘吧。 5. 攒rp，多做好事，做一个善良，温柔，好脾气的OIer。rp好了，啥优化也不加，直接AC。 此题比较模板，直接套用上述内容。 code: ``` //我已经尽力了，此代码在无优化时也能拿到不错的分数(80+) #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <cstdlib> #include <queue> #include <ctime> using namespace std; const int N = 2000; double bx[N] , by[N] ,r[N] , p[N] , q[N] ; int n , m;double R; double sumx , sumy; double dist(double x1 , double y1 , double x2 , double y2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 -y2) * (y1 - y2)); } int qsum(double x , double y) {//炸弹放在此处 int cnt = 0 ; double dis = R;//炸弹最大半径 for(int i = 1; i <= n; i++) dis = min(dis , dist(x , y , bx[i] , by[i]) - (double)r[i]);//炸弹在不能碰到建筑 // cout << dis << endl; for(int i = 1; i <= m; i++) if(dist(x , y , p[i] , q[i]) <= dis)cnt++; //是否能炸到敌人 return cnt; } double ans , ansx , ansy , deltaT , T , Te; double nowx , nowy; void mount(double x , double y) {//爪巴山，此参数每次时间大概要50-75ms nowx = x, nowy = y;//当前解 T = 100000; Te = 1e-10;//初始温度 deltaT = 0.996;//降温系数 while(T > Te) { double sx = nowx + (rand()<<1 - RAND_MAX)*T; double sy = nowy + (rand()<<1 - RAND_MAX)*T; //扰动后的点，可以看出T越大，sx，sy和nowx ,nowy差距就越远 int nowans = qsum(sx , sy); if(nowans > ans) {//比当前解要优 ansx = sx;ansy = sy;//全局最优 nowx = sx; nowy = sy; ans = nowans;//全局最优 } T *= deltaT;//降温 } } void work() { scanf("%d%d%lf" , &n , &m ,&R); ansx = 0; ansy = 0; sumx = sumy = 0; for(int i = 1; i <= n; i++) scanf("%lf%lf%lf" , &bx[i] , &by[i] , &r[i]); for(int i = 1; i <= m; i++) scanf("%lf%lf" , &p[i] , &q[i]) ,sumx += p[i],sumy += q[i]; ansx = sumx/m;ansy = sumy/m; // cout << ansx << endl; ans = qsum(ansx , ansy); // cout << ans << endl; //先弄个初始解 //如果当前时间在0.9s以下，就继续跑模拟退火。 while ((double)clock()/CLOCKS_PER_SEC < 0.9)//先随机找几个点，乱搞一下 mount(sumx * (double(rand()/RAND_MAX)) , sumy * (double(rand()/RAND_MAX))); //观察函数的图像，如果最优答案都比较接近，可以替换成下面的代码 /* while ((double)clock()/CLOCKS_PER_SEC < 0.9) mount(ansx , ansy);在最优解的基础上找到答案*/ printf("%.0lf\n" , ans); } int main() { srand(time(0)); work(); return 0; } /* _ooOoo_ o8888888o 88" . "88 (| -_- |) O\ = /O ____/`---'\____ .' \\| |// `. / \\||| : |||// \ / _||||| -:- |||||- \ | | \\\ - /// | | | \_| ''\---/'' | | \ .-\__ `-` ___/-. / ___`. .' /--.--\ `. . __ ."" '< `.___\_<|>_/___.' >'"". | | : ` - `.;`\ _ /`;.`/ - ` : | | \ \ `-. \_ __\ /__ _/ .-` / / ======`-.____`-.___\_____/___.-`____.-'====== `=---=' ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 佛祖保佑 铁定AC */ ```