灭鼠行动 题解
灭鼠行动
前言
-
只能保证此题解中的代码能通过本题的所有数据，不保证一定能通过所有符合题目给出条件的数据。
实在不想调了。 -
另一份题解中的数据生成器是错的，会给出一些不合法的地图。（比如地图中有 \(17\) 和 \(25\) 之类的数）
-
本题数据水，一些有比较大的错误的代码也能过。（我的代码没加下文中的第二条细节的特判也能过）
-
我把我的代码和另一份题解中的代码放在一起拍了 \(1000\) 组数据，总共出现了十来组不一样的答案，原因主要在昏迷结束后同一位置的老鼠是否能立刻繁殖的问题上，两份代码不一样（我的代码允许，另一份代码会先移动），此处存疑。
思路分析
按照题意模拟即可。
主要看代码。
亿些细节
-
每个时刻的优先级应为：武器 > 繁殖 > 出生 > 行动。
-
如果两只老鼠在繁殖期间被炸死，小老鼠不会出生。
-
如果两只老鼠在繁殖期间被转化性别，繁殖过程不变。
-
同一位置有恰好两只老鼠才会考虑繁殖。
-
遇到岔路口时先累加遇到的次数再考虑转向。
-
死胡同只需要转一次就变成了单向岔路的情况。
-
考虑繁殖时需要判断两只老鼠是否都满足所有条件。
-
繁殖休息结束后需要动一下，移动转向都行，但必须动一下。
-
注意时间单位和时刻的端点开闭性。
-
强力炸弹的范围是一个十字，不能穿墙，可以取到 \(L\)。
-
神秘射线的范围是一个圆形，可以穿墙，可以取到 \(R\)。
-
如果你使用
vector，删除老鼠时注意指针会不会失效。 -
计算时间的优先级应为：昏迷 > 休息 = 成长。
-
注意在生成老鼠和删除老鼠时更新老鼠的数量。
-
不能逐一对每只老鼠进行繁殖和移动判定，应先对所有老鼠走一遍繁殖判定，再对所有老鼠走一遍移动判定。
代码
不加注释只有 5.1k，应该算短的了。
注释写的比较详细，可以看一看。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
const int N=200,T=1010;
#define left(x) (((x)+3)%4)//x 的左方向
#define right(x) (((x)+1)%4)//x 的右方向
int L,R,m,n,K,P,Limit,EndTime,Time;//Time 表示当前时刻，其他的是题目给的
int MouseNum,MouseId,in1,in2,in3,in4;//当前老鼠的数量与编号
int road[N][N][4];//0-N北，1-E东，2-S南，3-W西
//road[x][y][z] 表示 (x,y) 的 z 方向能否通行
int vx[]={-1,0,1,0},vy[]={0,1,0,-1},se[]={0,1,0,1};
//vx[i] 表示向 i 方向移动 x 坐标的变化量，vy[i] 同理
//se[i] 表示 i 方向的性别
struct Mouse{
int x,y;//坐标
int dir;//方向
int sex;//性别 0-X雄，1-Y雌
int coma;//停止昏迷时刻
int cnt;//第几次遇到转向情况
int adu;//成年还需的时间
int rel;//剩余休息的时间
int move;//是否需要移动再繁殖
}NewM,mo[N];//mo 中储存所有存活过的老鼠，mouse 中储存所有当前存活的老鼠编号
struct Weapon{
int type;//类型 1-强力炸弹，2-神秘射线，3-定时炸弹，4-生物炸弹
int tim;//放置时刻
int x,y;//放置坐标
}we[N];
char inp[5];
vector<int> weatime[T];//weatime[i] 储存 i 时刻需要启动的武器编号
vector<int> mouse,mp[N][N];//mp[x][y] 储存 (x,y) 位置的所有老鼠，这样写起来比较方便，常数也会小一点（？）
vector<int> appear[T];//appear[i] 储存 i 时刻出生的老鼠编号
void bomb(int x,int y,int r){//在 (x,y) 位置爆炸一个半径为 r 的十字炸弹，这里把两种炸弹的爆炸合并了，若是强力炸弹 r=L，若是定时炸弹 r=0
for(int i=0;i<4;i++)//四个方向
for(int j=0;j<=r;j++){
int xx=x+vx[i]*j,yy=y+vy[i]*j;
if(xx<1||yy<1||xx>m||yy>n) break;//超出地图边界
if(j&&!road[xx-vx[i]][yy-vy[i]][i]) break;//穿过墙壁
for(auto it:mp[xx][yy])
mouse.erase(find(mouse.begin(),mouse.end(),it));//删除编号为 it 的老鼠
for(int t=Time;t<=Time+2;t++)//删除接下来此处会出生的老鼠
for(int id=0;id<appear[t].size();){
int now=appear[t][id];
if(mo[now].x==xx&&mo[now].y==yy)
appear[t].erase(find(appear[t].begin(),appear[t].end(),now));
else id++;//注意删除的方法
}
MouseNum-=mp[xx][yy].size();//更新老鼠数量
mp[xx][yy].clear();//清空此处老鼠
}
}
void coma(int x,int y){//在 (x,y) 位置放置神秘射线
for(auto it:mouse)
if((mo[it].x-x)*(mo[it].x-x)+(mo[it].y-y)*(mo[it].y-y)<=R*R){//检测半径
if(mo[it].coma>=Time) mo[it].coma+=3;
else mo[it].coma=Time+3;//更新昏迷时间，这里写麻烦了
}
}
void reve(int x,int y){//在 (x,y) 位置放置生物炸弹
for(auto it:mp[x][y]) mo[it].sex^=1;//反转性别
}
void move(int id){//移动编号为 id 的老鼠
int &dir=mo[id].dir,&x=mo[id].x,&y=mo[id].y;
if(road[x][y][dir]){//首先直行
mp[x][y].erase(find(mp[x][y].begin(),mp[x][y].end(),id));
x+=vx[dir];y+=vy[dir];//更新坐标
mp[x][y].push_back(id);//别忘了更新 mp
}
else if(road[x][y][left(dir)]&&road[x][y][right(dir)]){//岔路口
mo[id].cnt++;//先加
if(mo[id].cnt&1) dir=left(dir);//判断左右移动
else dir=right(dir);
}
else if(road[x][y][left(dir)]||road[x][y][right(dir)]){//单边
if(road[x][y][left(dir)]) dir=left(dir);
else dir=right(dir);
}
else dir=right(dir);
}
void birth(int id){//繁殖
if(mo[id].adu||mo[id].rel||mo[id].move) return ;//判断自己的情况
int x=mo[id].x,y=mo[id].y;
if(mp[x][y].size()!=2) return ;//恰好两只
for(auto it:mp[x][y]){
if(it==id) continue;
if(mo[it].adu||mo[it].sex==mo[id].sex) continue;//判定合法
if(mo[it].coma>Time||mo[it].rel||mo[it].move) continue;//判定对方情况
mo[id].rel=4;mo[it].rel=4;//进入休息，设为 4 是因为这是右开的
for(int i=0;i<4;i++)//向四个方向生成老鼠
if(road[x][y][i]){
MouseId++;
mo[MouseId]=Mouse{x,y,i,se[i],0,0,5,0};//小老鼠的初始化
appear[Time+2].push_back(MouseId);
}
break;
}
}
int main(){
scanf("%d%d%d%d",&L,&R,&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++){
scanf("%d",&in1);
if(in1>=8) road[i][j][3]=1,in1-=8;
if(in1>=4) road[i][j][2]=1,in1-=4;
if(in1>=2) road[i][j][1]=1,in1-=2;
if(in1>=1) road[i][j][0]=1,in1-=1;//读入并生成地图
}
scanf("%d",&K);
for(int i=1;i<=K;i++){//生成老鼠
scanf("%d%d",&in1,&in2);
NewM.x=in1;NewM.y=in2;
scanf("%s",inp+1);
if(inp[1]=='N') NewM.dir=0;
if(inp[1]=='E') NewM.dir=1;
if(inp[1]=='S') NewM.dir=2;
if(inp[1]=='W') NewM.dir=3;//判定方向
scanf("%s",inp+1);
if(inp[1]=='X') NewM.sex=0;
if(inp[1]=='Y') NewM.sex=1;//判定性别
mouse.push_back(i);//更新老鼠所在
mp[in1][in2].push_back(i);
mo[i]=NewM;
}
MouseNum=MouseId=K;
scanf("%d%d",&P,&Limit);
for(int i=1;i<=P;i++){
scanf("%d%d%d%d",&in1,&in2,&in3,&in4);
we[i].type=in1;we[i].tim=in2;
we[i].x=in3;we[i].y=in4;
weatime[in2].push_back(i);//更新武器所在
}
scanf("%d",&EndTime);
for(Time=0;Time<=EndTime;Time++){//开始模拟
for(auto &i:weatime[Time]){//启动 1，2，4 类武器
if(we[i].type==1) bomb(we[i].x,we[i].y,L);
if(we[i].type==2) coma(we[i].x,we[i].y);
if(we[i].type==4) reve(we[i].x,we[i].y);
}
for(auto &i:weatime[max(0,Time-3)])//启动 3 时刻前的定时炸弹
if(we[i].type==3) bomb(we[i].x,we[i].y,0);
for(auto it:mouse){//判定繁殖
if(mo[it].coma>Time||mo[it].rel||mo[it].move) continue;
birth(it);
}
for(auto it:appear[Time]){//判定生成
mouse.push_back(it);
mp[mo[it].x][mo[it].y].push_back(it);//记得加入老鼠所在位置，不然会 RE
MouseNum++;
}
for(auto it:mouse){//更新休息时间
if(mo[it].coma>Time) continue;
if(mo[it].rel){
mo[it].rel--;
if(!mo[it].rel) mo[it].move=1;
continue;
}
}
for(auto it:mouse){//判定移动
if(mo[it].coma>Time||mo[it].rel) continue;
move(it);mo[it].move=0;
if(mo[it].adu) mo[it].adu--;//更新年龄
}
if(MouseNum>Limit){cout<<"-1\n";return 0;}//发生鼠疫
}
cout<<MouseNum<<'\n';
return 0;
}
其他
2022 年 12 月 23 日 16:40：随机跳题 ing。
2022 年 12 月 23 日 16:50：咦？这道题好有意思，写写看。
2022 年 12 月 23 日 20:30：我写完了，开调。
2022 年 12 月 23 日 21:30：20pts 调不出来了，算了。
2023 年 8 月 6 日 15:10：随机跳题 ing。
2023 年 8 月 6 日 15:20：咦？这道题我怎么见过，开写，看我什么时候写完。
2023 年 8 月 6 日 18:10：我写完了，开调。
2023 年 8 月 7 日 9:20：我调完了。