P7196 灭鼠行动题解

Mr_H2T · 2021-07-21 21:28:46 · 题解

这道题就是一道大模拟，~~跟那个与猪打牌的题差不多，但是简单一点。~~

主要注意以下细节：

岔路的拐弯与当前面对岔路的次数奇偶性有关;
繁殖出小鼠后老鼠还需等待一单位时间，小鼠可以直接运动;
强力炸弹的轨迹是一个伸展长度为 L 的十字，而不是距离之和为 L ;
射线范围是一个穿壁的圆形 ;

还有一些隐含的条件，经过不断尝试以及网络搜寻（这里参考了这篇博客）：

武器的优先度比老鼠要高，比如某一时刻同时会有出生与神秘射线，应当先响应神秘射线，在 3 个单位时间（或累加）之后再出生小鼠;
事实上，死路的转弯朝左或右并无影响（转一次后就变成了另一种带一个拐口的状态，无需我们再加以判断）
最为神奇的一个条件，甚至我无法在题面中明确发现：在一次繁殖之后，老鼠必定先运动一下再进行继续繁殖（如果可以）;

还有一个根据题目可推得但是有些奇怪的结论：

若繁殖过程中两只老鼠被生物炸弹照射，那么繁殖过程保持不变。这在题目中是显然的，但是有那么一点点奇怪。

以上就是我总结出来比较重要的一些细节。对于时间的运转，我采取的是仿同上文链接给出的，每一秒计算本一秒操作以及下一秒的状态。

UPD：这里附上一个我自己写的生成数据的代码。

具体代码实现见下。

#include<bits/stdc++.h>
#define rint register int
#define fu(i,a,b,d,c) for(rint i=a;i<=(b)&&c;i+=d)
#define fd(i,a,b,d,c) for(rint i=a;i>=(b)&&c;i-=d)
using namespace std;
inline int read(){
    char c=0,f=1;int num=0;
    while(c<'0'||c>'9'&&c!='-')((c=getchar())=='-')&&(f=-f);
    while(c>='0'&&c<='9')num=(num<<1)+(num<<3)+(c^48),c=getchar();
    return num*f;
}
#define N 1
#define E 2
#define S 4
#define W 8
#define XY 1
#define XX 2
#define BOMB 1
#define RAY 2
#define T_BOMB 3
#define B_BOMB 4
const int dx[9]={0,-1,0,0,1,0,0,0,0},dy[9]={0,0,1,0,0,0,0,0,-1};
int L,R,n,m,K,Limit,P,TimeLimit,curTime,mouseCnt;
int pipes[55][55];
struct Mouse{
    int age,sex,isProducing,towards,facingCross,x,y,stopTime,produceTime;
    Mouse(){
        age=sex=isProducing=towards=facingCross=x=y=stopTime=produceTime=0;
    }
};
struct Weapon{
    int x,y,type,setTime,occurTime;
    bool operator<(const Weapon b)const{
        return occurTime<b.occurTime;
    }
    Weapon(){
        x=y=type=setTime=occurTime=0;
    }
};
vector <Mouse> mice;
vector <Weapon> weapons;
int weaponPointer=0;
void produceNewMouse(int x,int y){
    Mouse tmp;
    tmp.x=x,tmp.y=y,tmp.age=0;
    if((pipes[x][y]&N)){
        tmp.towards=N,tmp.sex=XY;
        mice.push_back(tmp);
    }
    if((pipes[x][y]&E)){
        tmp.towards=E,tmp.sex=XX;
        mice.push_back(tmp);
    }
    if((pipes[x][y]&S)){
        tmp.towards=S,tmp.sex=XY;
        mice.push_back(tmp);
    }
    if((pipes[x][y]&W)){
        tmp.towards=W,tmp.sex=XX;
        mice.push_back(tmp);
    }
}
void moveMouse(Mouse& mouse){
    int x=mouse.x,y=mouse.y,tow=mouse.towards;
    if(pipes[x][y]&tow){
        mouse.x+=dx[tow];
        mouse.y+=dy[tow];
        return;
    }
    //如题描述 
    if(tow==N||tow==S){
        if((pipes[x][y]&E)&&(pipes[x][y]&W)){
            if(!(mouse.facingCross&1)){
                if(tow==N)mouse.towards=W;
                if(tow==S)mouse.towards=E;
            }else{
                if(tow==N)mouse.towards=E;
                if(tow==S)mouse.towards=W;
            }
            mouse.facingCross++;
        }
        else if((pipes[x][y]&W)&&!(pipes[x][y]&E))mouse.towards=W;
        else if((pipes[x][y]&E)&&!(pipes[x][y]&W))mouse.towards=E;
        else mouse.towards=W;
    }
    if(tow==W||tow==E){
        if((pipes[x][y]&S)&&(pipes[x][y]&N)){
            if(!(mouse.facingCross&1)){
                if(tow==W)mouse.towards=S;
                if(tow==E)mouse.towards=N;
            }else{
                if(tow==W)mouse.towards=N;
                if(tow==E)mouse.towards=S;
            }
            mouse.facingCross++;
        }
        else if((pipes[x][y]&N)&&!(pipes[x][y]&S))mouse.towards=N;
        else if((pipes[x][y]&S)&&!(pipes[x][y]&N))mouse.towards=S;
        else mouse.towards=N;
    }
}
void mouseProduce(Mouse& mouse){
    //需满足条件 1.到达年龄 2.不被眩晕 3.未在进行繁殖  
    if(mouse.stopTime||mouse.produceTime||mouse.isProducing||!(mouse.age>=5))return;
    int atMyPos=0;
    for(rint Mouse2=0;Mouse2<mice.size();Mouse2++)if(mice[Mouse2].x==mouse.x&&mice[Mouse2].y==mouse.y)atMyPos++;
    if(atMyPos!=2)return;
    for(rint Mouse2=0;Mouse2<mice.size();Mouse2++)
    if(mice[Mouse2].x==mouse.x&&mice[Mouse2].y==mouse.y&&!mice[Mouse2].stopTime
    &&!mice[Mouse2].isProducing&&mice[Mouse2].sex!=mouse.sex&&mice[Mouse2].age>=5
    &&!mice[Mouse2].produceTime){
        mouse.produceTime=mice[Mouse2].produceTime=curTime+2,mouse.stopTime=mice[Mouse2].stopTime+=3;
        if(mouse.sex==XX)mouse.isProducing=1;
        else mice[Mouse2].isProducing=1;
        break;
    }
}
void dfsForBD(int x,int y,int dir,int lastlength){
    if(lastlength>L)return;
    for(rint nowMouse=0;nowMouse<(int)mice.size();){
        if(mice[nowMouse].x==x&&mice[nowMouse].y==y)mice.erase(mice.begin()+nowMouse);
        else nowMouse++;
    }
    if(pipes[x][y]&dir)dfsForBD(x+dx[dir],y+dy[dir],dir,lastlength+1);
}
void bombOccur(int x,int y){
    if(pipes[x][y]&N)dfsForBD(x,y,N,0);
    if(pipes[x][y]&E)dfsForBD(x,y,E,0);
    if(pipes[x][y]&S)dfsForBD(x,y,S,0);
    if(pipes[x][y]&W)dfsForBD(x,y,W,0);
}
void rayOccur(int x,int y){
    for(rint nowMouse=0;nowMouse<mice.size();nowMouse++)
    if((mice[nowMouse].x-x)*(mice[nowMouse].x-x)+(mice[nowMouse].y-y)*(mice[nowMouse].y-y)<=R*R)
        mice[nowMouse].stopTime+=3,mice[nowMouse].produceTime+=3;
}
void t_bombOccur(int x,int y){
    for(rint nowMouse=0;nowMouse<mice.size();){
        if(mice[nowMouse].x==x&&mice[nowMouse].y==y)mice.erase(mice.begin()+nowMouse);
        else nowMouse++;
    }
}
void b_bombOccur(int x,int y){
    for(rint nowMouse=0;nowMouse<mice.size();nowMouse++)
    if(mice[nowMouse].x==x&&mice[nowMouse].y==y)mice[nowMouse].sex=3-mice[nowMouse].sex;
}
void weaponAct(){
    while(weaponPointer<weapons.size()&&weapons[weaponPointer].occurTime==curTime){
        Weapon tmp=weapons[weaponPointer];
        if(tmp.type==BOMB)bombOccur(tmp.x,tmp.y);
        else if(tmp.type==RAY)rayOccur(tmp.x,tmp.y);
        else if(tmp.type==T_BOMB)t_bombOccur(tmp.x,tmp.y);
        else if(tmp.type==B_BOMB)b_bombOccur(tmp.x,tmp.y);
        weaponPointer++;
    }
}
void checkOver(){
    if(mice.size()>Limit){
        printf("-1");
        exit(0);
    }
}
signed main(){
    L=read(),R=read(),n=read(),m=read();
    fu(i,1,n,1,1)fu(j,1,m,1,1)pipes[i][j]=read();
    K=read();
    fu(i,1,K,1,1){
        int x,y;char t,s;
        scanf("%d %d %c %c\n",&x,&y,&t,&s);
        Mouse tmp;
        tmp.x=x,tmp.y=y;
        if(t=='N')tmp.towards=N;
        if(t=='E')tmp.towards=E;
        if(t=='S')tmp.towards=S;
        if(t=='W')tmp.towards=W;
        tmp.sex=(s=='X'?XY:XX),tmp.age=5;
        mice.push_back(tmp);
    }
    P=read(),Limit=read();
    fu(i,1,P,1,1){
        int ty=read(),t=read(),x=read(),y=read();
        Weapon tmp;
        tmp.x=x,tmp.y=y,tmp.type=ty,tmp.setTime=t;
        if(ty==T_BOMB)tmp.occurTime=t+3;
        else tmp.occurTime=t;
        weapons.push_back(tmp);
    }
    //按发生时间排序 
    sort(weapons.begin(),weapons.end());
    TimeLimit=read();
    checkOver();
    for(curTime = 0; curTime <= TimeLimit;curTime++){
        //武器运作 
        weaponAct();
        //检查繁殖 
        for(rint nowMouse=0;nowMouse<mice.size();nowMouse++)mouseProduce(mice[nowMouse]);
        //检查出生 
        for(rint nowMouse=0;nowMouse<mice.size();nowMouse++){
            if(mice[nowMouse].produceTime==curTime&&mice[nowMouse].isProducing){
                produceNewMouse(mice[nowMouse].x,mice[nowMouse].y);
                mice[nowMouse].isProducing=0;
            }
        }
        checkOver();//事实上这一句在下文for循环之前或之后均无影响，因为下文只有运动，对答案无贡献
        //计算下一秒的状态，位置 
        for(rint nowMouse=0;nowMouse<mice.size();nowMouse++){
            if(mice[nowMouse].stopTime)mice[nowMouse].stopTime--;
            else mice[nowMouse].age++,mice[nowMouse].produceTime=0,moveMouse(mice[nowMouse]);
        }
    }
    printf("%d",mice.size());
}

P7196 灭鼠行动 题解

P7196 灭鼠行动题解