1 条题解

  • 0
    @ 2025-8-24 22:27:33

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar Mr_H2T
    这个家伙很懒，什么也没有留下

    搬运于2025-08-24 22:27:33，当前版本为作者最后更新于2021-07-21 21:28:46，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

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

    主要注意以下细节：

    • 岔路的拐弯与当前面对岔路的次数奇偶性有关;

    • 繁殖出小鼠后老鼠还需等待一单位时间，小鼠可以直接运动;

    • 强力炸弹的轨迹是一个伸展长度为 LL 的十字，而不是距离之和为 LL ;

    • 射线范围是一个穿壁的圆形 ;

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

    • 武器的优先度比老鼠要高，比如某一时刻同时会有出生与神秘射线，应当先响应神秘射线，在 33 个单位时间（或累加）之后再出生小鼠;

    • 事实上，死路的转弯朝左或右并无影响（转一次后就变成了另一种带一个拐口的状态，无需我们再加以判断）

    • 最为神奇的一个条件，甚至我无法在题面中明确发现：在一次繁殖之后，老鼠必定先运动一下再进行继续繁殖（如果可以）;

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

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

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

    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());
}
    • 1

    [CTSC2002] 灭鼠行动

    信息

    ID
    6287
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 20ms