CF175E Power Defence

题意

一个塔防游戏：给定一个无限长的数轴，一个无限血的敌人要从正无穷走到负无穷。你的任务是放置三种塔，包含两种攻击塔和一种寒冰塔，使得敌人受到的伤害最大。

其中，每种塔的攻击半径可能不同，每种攻击塔的攻击力也可能不同。而寒冰塔没有攻击力，它的作用是使范围内敌人的速度减速，即一段区间若有(k)个寒冰塔覆盖，敌人速度变为(frac{1}{k+1})。

敌人初始速度为1格每秒，攻击塔的伤害值也是以秒计算的。

思路

首先有几个基本结论：

若没有寒冰塔，整场游戏答案固定。
若有寒冰塔，让所有塔挤在一起必不会更劣。这里对挤在一起的定义是：所有塔至少有一端上下对齐，且左右两端距离最大不超过(lceil frac{n}{2} ceil)。
寒冰塔的能力实际上是将范围内基础伤害增加一倍。注意这里的伤害是忽略其他寒冰塔效果的。

发现序列长度很短，排列的方式也很有限，于是我们就有了一个大胆的想法：模拟退火。

然后便是裸的模拟退火算法：随机出来两个位置进行交换，统计答案，若答案大于当前答案，接受之；否则以当前温度的概率接受之。参数调整得好的话多做几次便可。

然后是统计答案。我有一个(n^2)的想法：扫描序列，每扫到一个寒冰塔就再次扫描整个序列的攻击塔，计算出两个塔间相交的范围乘上该塔攻击力加入答案即可，当然最后别忘了加上不计算寒冰塔的基础伤害。正确性也显然，因为显然寒冰塔的贡献是可以对于每个其他攻击塔单独计算的。

具体实现我耍了个小聪明：将所有炮塔放进一个数组中，这样交换的时候就不用分上下位置了。统计答案的时候计算出该塔的实际位置就行。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
#include<ctime>
#define T 10000
#define eps 0.99
#define kb 1.38e-23
#define endt 1e-12
#define INF 1e19
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=45;
	int n1,n2,n3,d1,d2,n,a[maxn],m;
	double r1,r2,r3,res,ans;
	inline double getsum(){
		double sum=0;
		for(int i=1;i<=n;i++){
			if(a[i]!=3)continue;
			int x=i;
			if(x>m)x-=m;
			double L3=x-r3,R3=x+r3;
			for(int j=1;j<=n;j++){
				if(a[j]==3)continue;
				int y=j,t=a[j];
				if(y>m)y-=m;
				if(t==1){
					double L1=y-r1,R1=y+r1;
					sum+=max(0.0,d1*(min(R1,R3)-max(L1,L3)));
				}else if(t==2){
					double L2=y-r2,R2=y+r2;
					sum+=max(0.0,d2*(min(R2,R3)-max(L2,L3)));
				}
			}
		}
		return res+sum;
	}
	inline void solve()
	{
		double t=T;
		double ans=0;
		while(t>endt)
		{
			int xx=rand()%n+1,yy=rand()%n+1;
			while(a[xx]==a[yy])xx=rand()%n+1,yy=rand()%n+1;
			swap(a[xx],a[yy]);
			double zp=getsum();
			if(zp>ans){
				ans=zp;
				star::ans=max(star::ans,ans);
			}else if(rand()<exp((ans-zp)/t/kb) * RAND_MAX)swap(a[xx],a[yy]);
			else ans=zp;
			t*=eps;
		}
	}
	inline void work(){
		n1=read(),n2=read(),n3=read();
		r1=read();
		r1=sqrt(r1*r1-1);
		r2=read();
		r2=sqrt(r2*r2-1);
		r3=read();
		r3=sqrt(r3*r3-1);
		d1=read(),d2=read();
		res=2*n1*r1*d1+2*n2*r2*d2;
		if(n3==0)return (void)printf("%.10lf",res);
		n=n1+n2+n3;
		for(int i=1;i<=n;i++)
			if(n1) a[i]=1,n1--;
			else if(n2) a[i]=2,n2--;
			else if(n3) a[i]=3,n3--;
		m=n/2+1;
		n=m*2;
		random_shuffle(a+1,a+1+n);
		srand(time(0));
//		while((double)clock()/CLOCKS_PER_SEC<2.7)
		for(int i=1;i<=100;i++)
			solve();
		printf("%.10lf
",ans);
	}
}
signed main(){
	star::work();
	return 0;
}

总结

这题正解是DP，爆搜也能过。

codeforces的题目，如果我现场写模拟退火的话一定当场去世。毕竟我因为一些奇怪的原因交了好多回。

~~所以骗骗分还是可以的~~

by ysr

UPD:2020.12.29

发现这个好像是个爬山