题解 P2586 【[ZJOI2008]杀蚂蚁】
前方高能预警
非战斗人员请马上撤离 QwQ
这里是当前
不用结构体内置函数最通俗易懂
码风最具强迫症
注释最为详细
最可爱（蒟蒻&&萌新预警）
的题解！！！
正文开始：
首先
显然这是一道模拟（废话）
思路也很容易想（按照题目说得一步步写就可以水过了）
生成蚂蚁-->释放信息素-->蚂蚁移动-->检查蛋糕是否被获取-->炮塔开火-->清理蚂蚁尸体-->检查游戏是否结束-->蚂蚁生长-->信息素流逝
之所以这样子设计思路是因为以下几个坑点：
1.炮塔是全体选定好各种的目标后同时射击，这意味着即使一个蚂蚁在这一秒钟被射至负血，其余炮塔当前依旧会攻击它（如果它之前被选为目标）
2.蚂蚁被卡住一次后就可以返回原路
3.判断一个蚂蚁是否被激光击中需要高中知识打几何模板
4.蚂蚁初始年龄是零
5.当蚂蚁存活时间达到5的倍数时的不正常转向是有合法的道路就走，但至少要在找到原正确方案的情况下逆时针转一次
6.蚂蚁的初始血量要用浮点数记录，因为蛋糕回血时是初始血量除2才向下取整
7.炮塔可以不开火，激光不会透过其目标
8.生成蚂蚁的条件之一是蚂蚁窝上不能有蚂蚁
9.某个蚂蚁血量为负且当前处于的位置被占用不代表它的尸体没有被处理（死亡没有被记录），因为有可能是别的蚂蚁在该点
然后我们就可以愉快的做（bei）题(xue)了~
很快你就会发现你成功的被极限数据卡住 QwQ
这里就提供两个小优化
第一个是显而易见的：当炮塔的攻击的目标不是Target时，显然该目标是离炮塔最近的，而炮塔对其的激光攻击就显然不能波及其他蚂蚁，否则其就不是最近目标
第二个是本君不同于上述两个题解的强力又易懂的优化操作（前方蒟蒻预警）
先来看一组极限数据：
n=8 m=8
s=1 d=200000 r=9
x=1 y=1
t=200000
即仅有一个攻击力无穷大的炮台于蚂蚁窝旁边，时间为200000秒
此时蚂蚁一出来就被杀死，以至于蚂蚁窝一直生产蚂蚁
如果你对蚂蚁进行的操作（留下信息素、生长、移动等）都是枚举全部的蚂蚁然后判断活着再对其操作，每次相关操作显然会超时
于是我们可以像之前的两篇题解一样维护一个仅存有活着的蚂蚁的数组
也可以定义一个变量last记录第一只活着的蚂蚁的编号，以后每次枚举都从它开始，当然这不是最优的，但是这是最容易的想到的，既然之前的蚂蚁都死了就没有必要从头枚举，于是时间复杂度大大降低~~（当然依旧可以被极为刁钻的手造200000数据卡死）
代码见下（几乎每一行都有注释，一定要愉快的AC哟~然后把这道题评为黑色）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<queue>
#define ll long long
#define N 1001003
#define inf 0x3fffffff
#define eps 1e-10
using namespace std;
ll inline read()//快读
{
ll ret=0;
char ch=getchar();
int f=1;
while(!isdigit(ch) && ch!='-')
ch=getchar();
if(ch=='-')
{
f=-1;
ch=getchar();
}
while(isdigit(ch))
{
ret=(ret<<1)+(ret<<3)+(ch^48);
ch=getchar();
}
return ret*f;
}
//Math（几何模板）（高中向量 QAQ）
struct Point
{
double x;
double y;
};
Point inline TurnPoint(double x,double y)
{
Point NewPoint;
NewPoint.x=x;
NewPoint.y=y;
return NewPoint;
}
Point operator + (Point A,Point B)
{
Point NewPoint=TurnPoint(A.x+B.x,A.y+B.y);
return NewPoint;
}
Point operator - (Point A,Point B)
{
Point NewPoint=TurnPoint(A.x-B.x,A.y-B.y);
return NewPoint;
}
int inline DoublePositive(double x)
{
if( fabs(x)<eps )
return 0;
if(x<0)
return -1;
return 1;
}
double inline Dot(Point A,Point B)
{
double sum=A.x*B.x+A.y*B.y;
return sum;
}
double inline Length(Point A)
{
double sum=sqrt( Dot(A,A) );
return sum;
}
double inline Cross(Point A,Point B)
{
double sum=A.x*B.y-A.y*B.x;
return sum;
}
double inline GetSlope(Point A)
{
double sum=A.y/A.x;
return sum;
}
double inline GetPointDistantToSegment(Point P,Point A,Point B)
{
Point Vector_1=B-A;
Point Vector_2=P-A;
Point Vector_3=P-B;
if( DoublePositive( Dot(Vector_1,Vector_2) )<0 )
return Length(Vector_2);
if( DoublePositive( Dot(Vector_1,Vector_3) )>0 )
return Length(Vector_3);
return fabs( Cross(Vector_1,Vector_2) / Length(Vector_1) );
}
//数学比NOI还要使我脱发 QAQ
int last=1;//原创重要优化 表示第一只活着的蚂蚁
int n,m;//地图的长和宽
struct Map//地图
{
int InformationSum;//地图上某点的信息素
bool used;//地图上某点有没有被占用
};
Map g[25][25];//地图数组
int EndTime;//结束时间
bool GameWin=false;//游戏是否结束
bool CakeFly=false;//蛋糕有没有不翼而飞 QwQ
int TurretSum;//炮塔数
int TurretRadius;//炮塔攻击范围
int TurretDamage;//炮塔伤害
int Target;//炮塔首选目标（拿蛋糕的哥们编号 @w@ ）
struct Turret//炮塔
{
int goal;//炮塔目标
int x;
int y;
};
Turret t[25];//炮塔数组
int BornAntSum=0;//生出的蚂蚁总数
int NowAntSum=0;//现在存活的蚂蚁数
const double AntSize=0.5;//蚂蚁的尺寸（占地半径）
struct Ant//蚂蚁
{
int x;//当前所在坐标
int y;
int old;//年龄
int level;//等级
int health;//血量
double BornHealth;//初始血量
int x_from;//上一秒所在坐标
int y_from;
bool get;//是否获得蛋糕
bool dead;//是否死亡
};
Ant a[300000];
void AntBorn()//蚂蚁的出生
{
if(NowAntSum>=6)//场上蚂蚁数不得超过6
return ;
if(g[0][0].used)//蚂蚁窝不得有蚂蚁
return ;
BornAntSum++;//生出的蚂蚁数++
NowAntSum++;//当前存活的蚂蚁数++
a[BornAntSum].x=0;//初始坐标为蚁窝
a[BornAntSum].y=0;
a[BornAntSum].x_from=99;//来着地狱（无穷远 QwQ）
a[BornAntSum].y_from=99;
g[0][0].used=true;//蚁窝已被占据
a[BornAntSum].old=0;//初始时为零岁
a[BornAntSum].level=( (BornAntSum-1)/6 )+1;//等级为之前生成的蚂蚁数/6 +1
a[BornAntSum].get=false;//初始没有蛋糕
a[BornAntSum].dead=false;//初始没死 QwQ
double Health=floor(4*pow(1.1,a[BornAntSum].level));//初始血量计算
a[BornAntSum].health=(int)Health;//血量取整
a[BornAntSum].BornHealth=Health;//初始血量记录
return ;
}
void inline ReleaseInformation()//释放信息素
{
for(int i=last;i<=BornAntSum;i++)//从第一只活着的蚂蚁开始枚举
{
if(a[i].dead)//死蚂蚁跳过
continue;
if(!a[i].get)
g[ a[i].x ][ a[i].y ].InformationSum+=2;//没蛋糕放2点
else
g[ a[i].x ][ a[i].y ].InformationSum+=5;//有蛋糕放5点
}
return ;
}
const int dx[4]={0,1,0,-1};//方向数组
const int dy[4]={1,0,-1,0};//东南西北
bool inline CheakPoint(int x,int y)//检查一个点能否放蚂蚁
{
//四种出界情况
if(x<0)
return false;
if(x>n)
return false;
if(y<0)
return false;
if(y>m)
return false;
//被占用的情况
if(g[x][y].used)
return false;
return true;
}
void inline AntMove()//蚂蚁移动
{
for(int i=last;i<=BornAntSum;i++)//同样从第一只活着的蚂蚁开始枚举
{
if(a[i].dead)//死蚂蚁跳过
continue;
int MaxInformation=-1;//能走的方向上最多的信息素
int NowDirection=-1;//不正常转向后的方向（活动时间为5的倍数）
int direction=-1;//正常情况的方向
int nowx;//要去的坐标
int nowy;
int nowd;//要走的方向
for(int j=0;j<4;j++)//四方向枚举
{
nowx=a[i].x+dx[j];//要去的坐标更新
nowy=a[i].y+dy[j];
if(!CheakPoint(nowx,nowy))
continue;//检查能否去
if(nowx==a[i].x_from && nowy==a[i].y_from)
continue;//检查是否从要去的点来
if(MaxInformation<g[nowx][nowy].InformationSum)
{
MaxInformation=g[nowx][nowy].InformationSum;
direction=j;//能走就尝试更新最多信息数与方向
}
}
if( (a[i].old+1)%5==0 && direction!=-1 )//至少原先要有方向可走
{
MaxInformation=-1;//当蚂蚁存活秒数为5的倍数就开始浪~
NowDirection=-1;//新方向
for(int j=1;j<=4;j++)//以原方向为基准逆时针旋转
{
nowd=(direction-j)%4;
if(nowd<0)//注意转了一圈的情况
nowd+=4;
nowx=a[i].x+dx[nowd];//同样应去的坐标
nowy=a[i].y+dy[nowd];
if(!CheakPoint(nowx,nowy))
continue;//同样检查是否能走
if(nowx==a[i].x_from && nowy==a[i].y_from)
continue;//同上检查是否从该点来
if(MaxInformation<g[nowx][nowy].InformationSum)
{
MaxInformation=g[nowx][nowy].InformationSum;
NowDirection=nowd;//同样更新方向和最大信息素
//事实上最大信息素的更新没多少用（只是判断该蚂蚁能否移动）
break;//转后一有合法的方向就出发
}
}
}
a[i].x_from=a[i].x;//上一秒在的坐标更新
a[i].y_from=a[i].y;//更新后蚂蚁就没有不能返回（当前）原路的限制了
if(MaxInformation==-1)
continue;//最大信息素没有被更新说明没有点可以走
if( (a[i].old+1)%5==0 )//叛逆期 QwQ
{
a[i].x+=dx[NowDirection];//立即走至该点
a[i].y+=dy[NowDirection];
g[ a[i].x_from ][ a[i].y_from ].used=false;
g[ a[i].x ][ a[i].y ].used=true;//注意占用的点要改变
}
else//正常情况下一样
{
a[i].x+=dx[direction];
a[i].y+=dy[direction];
g[ a[i].x_from ][ a[i].y_from ].used=false;
g[ a[i].x ][ a[i].y ].used=true;
}
}
return ;
}
void inline CheakCake()//检查是否有蚂蚁能拿走蛋糕
{
if(CakeFly)//如果蛋糕早就已经被拿走则返回
return ;
for(int i=last;i<=BornAntSum;i++)//枚举活着的蚂蚁
{
if(a[i].dead)//同上
continue;
if(a[i].x==n && a[i].y==m)//如果到达了有蛋糕的点
{
Target=i;//成为过街老鼠 QwQ
CakeFly=true;//前面已保证蛋糕在该点
a[i].get=true;//蚂蚁获得蛋糕
a[i].health+=(int)(a[i].BornHealth/2);//偷吃蛋糕回血
a[i].health=min((int)a[i].BornHealth,a[i].health);//注意血量不超上限
return ;
}
}
return ;
}
double inline GetDistant(int x1,int y1,int x2,int y2)//两点距离公式
{
int Sum=( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
return sqrt( (double)Sum );
}
void inline FireAnt()//二营长的意大利炮预备开火 QwQ
{
for(int i=1;i<=TurretSum;i++)//枚举每一个炮塔
{
double TargetDistant=GetDistant(t[i].x,t[i].y,a[Target].x,a[Target].y);//炮塔与首选目标的距离
//如果没有首选目标或者离首选目标太远就正常打最近的蚂蚁
if(!CakeFly || TargetDistant-(double)TurretRadius>eps)//注意实数域的计算要与极小值比较
{
double GoalDistant;//炮塔与当前目标的距离
double MinDistant=inf;//离炮塔最近的蚂蚁与炮塔的距离
for(int j=last;j<=BornAntSum;j++)//同样枚举存活的蚂蚁
{
if(a[j].dead)//同上
continue;
//与当前蚂蚁的距离计算
GoalDistant=GetDistant(t[i].x,t[i].y,a[j].x,a[j].y);
if(GoalDistant<MinDistant)//查看能否更新最近距离
{
MinDistant=GoalDistant;
t[i].goal=j;//更新最近蚂蚁作目标
}
}
if(MinDistant-(double)TurretRadius>eps)
{
//如果最近距离都不能满足就返回
t[i].goal=0;
continue;
}
//攻击最近目标
a[ t[i].goal ].health-=TurretDamage;
}
else//如果存在首选目标且能打到
{
t[i].goal=Target;//目标为首选目标
Point A=TurnPoint(a[ t[i].goal ].x,a[ t[i].goal ].y);
Point B=TurnPoint(t[i].x,t[i].y);//向量预备
for(int j=last;j<=BornAntSum;j++)//枚举活着的蚂蚁
{
if(a[j].dead)//（活着的目标都有可能被波及）
continue;
if(a[j].get)//如果是首选的目标就直接打击
{
a[j].health-=TurretDamage;
continue;
}
Point P=TurnPoint(a[j].x,a[j].y);//点预备
double NotGoalDistant=GetPointDistantToSegment(P,A,B);//点与直线的距离
if(NotGoalDistant-AntSize<eps)//如果能被激光波及到就减血
a[j].health-=TurretDamage;
}
}
}
}
void inline ClearBulletField()//清理战场
{
for(int i=last;i<=BornAntSum;i++)//枚举可能死掉的蚂蚁
{
if(a[i].health>=0)//该蚂蚁当前血量应该<0
continue;
if(!g[ a[i].x ][ a[i].y ].used)//当前应该占用一个点
continue;
if(a[i].dead)//当前应该没视作死亡
continue;
NowAntSum--;//存活蚂蚁数--
g[ a[i].x ][ a[i].y ].used=false;//不占用空间（处理尸体）
a[i].x=99;//滚去地狱
a[i].y=99;//QwQ
a[i].dead=true;//确认死亡
if(a[i].get)//如果有蛋糕
{
CakeFly=false;//把蛋糕放回去
Target=0;//首选目标死亡
}
}
}
void inline CheakGameContinue()//检查游戏是否继续
{
if(!CakeFly)//蛋糕没有被拿走则继续
return ;
for(int i=last;i<=BornAntSum;i++)//枚举可能带蛋糕回蚁窝的蚂蚁
{
if(a[i].dead)//首先它应该是活着的
continue;
if(a[i].x || a[i].y)//而且它坐标应该为（0,0）
continue;
if(!a[i].get)//而且它要有蛋糕
continue;
GameWin=true;//游戏胜利
break;
}
return ;
}
void inline AntGrow()//蚂蚁长大
{
for(int i=last;i<=BornAntSum;i++)//首先依然得活着
{
if(a[i].dead)//同上
continue;
a[i].old++;//长大
}
return ;
}
void inline InformationGone()//信息素消失
{
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(g[i][j].InformationSum)//注意要有信息素
g[i][j].InformationSum--;
}
}
return ;
}
void inline Enter()//输入
{
n=read();//读入地图大小
m=read();
TurretSum=read();//读入炮塔相关信息
TurretDamage=read();
TurretRadius=read();
for(int i=1;i<=TurretSum;i++)//读入炮塔
{
t[i].x=read();
t[i].y=read();
//记得炮塔也要占一个点
g[ t[i].x ][ t[i].y ].used=true;
}
EndTime=read();//读入结束时间
return ;
}
void inline Work()//工作
{
for(int Time=1;Time<=EndTime;Time++)//时光飞逝
{
AntBorn();//蚂蚁出生
ReleaseInformation();//释放信息素
AntMove();//蚂蚁跑路
CheakCake();//检查是否有蚂蚁能拿到蛋糕
FireAnt();//开火
ClearBulletField();//清理战场
CheakGameContinue();//检查游戏是否能继续
if(GameWin)//如果蚂蚁已经获胜
{
printf("Game over after %d seconds\n",Time);
break;
}
AntGrow();//蚂蚁生长
InformationGone();//信息素流逝
for(int i=last;i<=BornAntSum;i++)//更新第一只存活的蚂蚁
{
if(a[i].dead)
continue;
else
{
last=i;
break;
}
}
}
return ;
}
void inline Output()
{
if(!GameWin)//如果蚂蚁没有获胜
printf("The game is going on\n");
printf("%d\n",NowAntSum);//输出存活的蚂蚁数
for(int i=last;i<=BornAntSum;i++)//输出相关信息
{
if(a[i].dead)//首先蚂蚁应该是活着的
continue;
printf("%d ",a[i].old);//输出年龄
printf("%d ",a[i].level);//输出等级
printf("%d ",a[i].health);//输出血量
printf("%d ",a[i].x);//输出当前坐标
printf("%d ",a[i].y);//
printf("\n");//换行
}
return ;
}
int main()//优美的主函数 QwQ
{
/*freopen("Enter.in","r",stdin);//习惯性打开文件
freopen("Output.out","w",stdout);*/
Enter();//输入
Work();//工作
Output();//输出
return 0;//程序结束
}
后记
不喜请跳过
再过两天就是初赛，想想看，现在的自己也才不过接触oi九个月吧，希望能拿一个省一等奖就心满意足了~
这道题是我写过的代码量最大的题目了QAQ
这让我想起了我的OI之旅
虽然才刚刚起步，但是仍然困难重重
停课，熬夜，培训
我热爱这种待在机房的日子
就像我并不讨厌这道烦琐的模拟
写了许久，不止一次萌生退意
但是就像OI一样
踏上了旅途就没有退路
我们不是坚持，是实在退无可退……