题解 P2586 【[ZJOI2008]杀蚂蚁】
打个广告此处观感更佳
NOIP考前想练一下码力就挑了一道不算非常难的大模拟来写了一下。
首先，因为此题题面过长就不放题目
原题请去Link
ps：因为一开始打的代码非常丑，还很繁复所以部分借鉴了一下黄学长的写法见谅。我的代码也是对着黄学长的std步步输出才调出来的，因为一些很智障的错误调了一年。。。
代码又臭又长注意
不过此题解不压行，思路清晰好评！
坑点
- 原题描述如下
“ 激光塔有个比较奇怪的特性：它在选定了打击目标后， 只要目标在其射程内，塔到目标蚂蚁圆心的连线上的所有蚂蚁
（这里“被打到”的判定变成了表示激光的线段与表示蚂蚁的圆有公共 点）都会被打到并损d格血， 但激光不会穿透它的打击目标打到后面的蚂蚁。 ”
这里就可以清晰的发现这里不仅是要判断直线和圆有没有交点，而是要判断线段和圆是否有焦点
所以这里的判断函数一定要写对否则会调一年，就像我
-
注意先判断蚂蚁死了没有，先更新状态再judge是否成功。
-
蚂蚁年龄一开始是0，而存活时间一开始的就是1。
-
所有的炮是同时开炮，所以要先统计一边每个炮台的target再统一扣血。
-
题目中的坐标不是平面直角坐标系中的坐标，是广义OI理解中的行列。。我就写反了。。
-
蚂蚁半径是0.5不是1！！注意
相信注意到这些地方会使你的代码形成更加清晰，这可是血的教训
题解
现在开始放题解。
首先我们看一下美观的主工作函数，
这部分代表了我写题的思路和流程，
下面就按照这些函数的排列顺序依依讲解每个步骤们也是严格按照题目描述来的
int work()
{
birth();
leave();
Move();
take_cake();
attack();
kill();
if(check_win())return 1;
End();
return 0;
}基本变量
先把每个变量列出来方便理解
int n,m,s,H,T,total;
//total场上总蚂蚁的个数，H 炮台伤害——>harm
bool cake_taken=0;//蛋糕现在是否被拿走
double R;//R 炮台射程半径，防止掉精度
int mp[9][9],vis[9][9];//信息素，记录障碍物
int dy1[]={1,0,-1,0},dx1[]={0,1,0,-1};//顺时针
int dy2[]={1,0,-1,0},dx2[]={0,-1,0,1};//逆时针
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct ant
{
int x,y,age,hp,rk,sur;//坐标，年龄，血量，级别,存活时间
int pre_x,pre_y;//上一秒所在的坐标
double mx;//最大血量上限
bool cake=0,live=0;//是否拿着蛋糕，是否活着
}a[100];
struct point
{
double x,y;
};
bool cmp_age(ant A,ant B)
{
return A.age>B.age;
}
struct turret//炮台
{
int x,y;
}t[100];出生
birth函数比较简单，注意每个数值要赋清楚
还有就是存储蚂蚁的方式选择，这是非常重要的！！因为选择方式不当可能会造成写代码很大的困扰。
例如我之前就是每次把死的蚂蚁sort到数组最后，再下一次出生蚂蚁的时候就直接覆盖掉
然而这样会出一些奇怪的问题，对于cnt的控制就有些奇怪的细节。。。反正调了很久没有A
于是后来就换成了每次找到一只死蚂蚁就直接覆盖，所有操作都只针对活着的蚂蚁操作而不是前cnt个这样的，毕竟场上最多也就6只蚂蚁，复杂度不用担心。。
void birth()
{
if(vis[0][0])return;
for(int i=1;i<=6;i++)
if(!a[i].live)
{
int l=total/6+1;
a[i].x=a[i].y=a[i].pre_x=a[i].pre_y=0;
a[i].age=0;a[i].rk=l;
a[i].mx=(4*pow(1.1,l));
a[i].hp=(int)(4*pow(1.1,l));
a[i].sur=1;a[i].cake=0;a[i].live=1;
vis[0][0]=1;
total++;
break;
}
}就不解释了
留标
这个很简单不解释，走流程
void leave()
{
for(int i=1;i<=6;i++)
if(a[i].live)//每个操作都要判断死活注意。。
{
if(!a[i].cake)mp[a[i].x][a[i].y]+=2;
else mp[a[i].x][a[i].y]+=5;
}
}移动
这是非常麻烦的一个函数，思路一定要清晰，否则非常惨痛。
想了解移动是否正确可以调BZOJ第4组数据，这个是没有攻击操作的，纯移动。数据哪来的？大家都心知肚明就不说了。。
思路整理
-
枚举方向时按顺时针直接写好，这样就不用多次判断
-
先扫遍找到信息素最大的一个方向，（不用管有没有多个相同的，因为顺时针枚举相当于已经筛过一遍）
-
再判断时间是否为5的倍数，是就再进行逆时针筛选操作
-
注意清零之前的标记，处理pre_x,pre_y
代码
int c(int x)
{
switch(x)
{
case 0:return 0;
case 1:return 3;
case 2:return 2;
case 3:return 1;
}
}
void update(int tx,int ty,int k)
{
a[k].pre_x=a[k].x;a[k].pre_y=a[k].y;
vis[a[k].x][a[k].y]=0;
a[k].x=tx;a[k].y=ty;
vis[tx][ty]=1;
}
bool judge(int tx,int ty,int i)
{
if(tx<0||ty<0||tx>n||ty>m||vis[tx][ty]||(tx==a[i].pre_x&&ty==a[i].pre_y))return 1;
else return 0;
}
void Move()
{
sort(a+1,a+7,cmp_age);
for(int i=1;i<=6;i++)
{
if(!a[i].live)continue;
int max_val=-(1<<30);
int choose_dirtion=-1;
for(int j=0;j<4;j++)
{
int tx=a[i].x+dx1[j],ty=a[i].y+dy1[j];
if(judge(tx,ty,i))continue;
max_val=max(max_val,mp[tx][ty]);//找最大值
}
for(int j=0;j<4;j++)
{
int tx=a[i].x+dx1[j],ty=a[i].y+dy1[j];
if(judge(tx,ty,i))continue;
if(max_val==mp[tx][ty]){choose_dirtion=j;break;}//找到最优方向
}
if(choose_dirtion!=-1)
{
if(a[i].sur%5==0)//时间是否为5的倍数
{
int change=c(choose_dirtion)+1;//暴力打表转换
for(int k=change;k;k++)
{
int j=k%4;
if(k==change+4)break;
int tx=dx2[j]+a[i].x;
int ty=dy2[j]+a[i].y;
if(judge(tx,ty,i))continue;
update(tx,ty,i);
break;
}
}
else//不是直接处理
{
int tx=a[i].x+dx1[choose_dirtion],ty=a[i].y+dy1[choose_dirtion];
update(tx,ty,i);
}
}
else
a[i].pre_x=a[i].x,a[i].pre_y=a[i].y;
}
}拿物
先注意判断此时是否有蛋糕，且这只蚂蚁是否活着就行。
void take_cake()
{
if(!cake_taken)
for(int i=1;i<=6;i++)
if(a[i].live)
if(a[i].x==n&&a[i].y==m)
{
a[i].cake=1;
a[i].hp=min((int)a[i].mx,a[i].hp+(int)a[i].mx/2);//防止掉精度
cake_taken=1;
return;
}
}攻击
这又是本题的一个大难点，又很多细节特别是对线段与直线是否有交点的判断。
思路整理
-
先按年龄sort一遍
-
先扫一遍判断是否可以攻击目标，不行再根据距离远近选择一个最终目标
-
只有打拿蛋糕的蚂蚁是才会有躺枪的情况，我只写了判断线段两点都在圆外的情况，避免麻烦
关于如何判断交点的问题。
可以看这篇BLOG
因为这道题只存在两点都在圆外的情况（只算躺枪），所以首先求出直线表达式，用
用公式算出点到直线的距离
当且仅当
最后判断时再线段上而不是在延长线上有交点，利用线段两个端点与圆心构成的三角形是否是锐角三角形即可。
令端点
则
满足