专栏文章

题解：P7196 [CTSC2002] 灭鼠行动

IICU_midway_azuma
P7196题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio4tj38
此快照首次捕获于
2025/12/02 13:22
3 个月前
此快照最后确认于
2025/12/02 13:22
3 个月前
查看原文
这一题吧，怎么说呢，读懂题面就做完了一半了。
鉴于本题题意有不少缺失外加数据非常水，仅保证代码可通过本题数据。
还是先明确几个已经在讨论区和题解都被大量提及的注意事项吧：
  • 应当先对所有老鼠走繁殖和出生判定，再走移动判定；
  • 事件优先级为武器大于繁殖大于出生大于行动等于成长；
  • 老鼠繁殖之后需要再动一下（转弯也可）才能繁殖；
  • 题目的 (x,y)(x,y) 指的是第 xx 行 yy 列而不是平面直角坐标系上的坐标。
另外还有几个推论：
  • 如果一个位置有非可繁殖老鼠，那么这个位置一定不能繁殖；
  • 繁殖过程中被生物炸弹攻击将不会中止繁殖过程；
  • 被神秘射线照射后年龄停止增长；
  • 强力炸弹的轨迹不会拐弯；
  • 死路掉头无论向左向右均无影响。
接下来就是具体过程了（方法可能较为繁琐，望包涵）。
先看武器的实现。
强力射线：分别向四个方向搜索，标记会被波及的地图位置，碰到墙立刻停下，遍历所有的老鼠，如果在被波及的位置就标记为死亡。
神秘射线：枚举所有老鼠，用勾股定理绕开浮点精度问题，如果会被影响就将其昏迷时间加 33。
定时炸弹：实际上相当于一个 33 刻后放置的瞬爆炸弹，所以直接输入的时候 tt 变为 t+3t+3，然后直接将在放置位置的老鼠记为死亡。
生物炸弹：如果在放置位置的老鼠更改性别即可。
再看繁殖和出生。
先扫一遍所有老鼠判断是否满足题述繁殖条件的同时在上次繁殖后动过，每有一对满足繁殖条件的老鼠，直接令其原地休息 33 刻。
再扫一遍所有老鼠，如果有剩余休息时间为 11 刻的老鼠，则在原地生成一只小老鼠。
移动直接参照题意即可。
死路随意左转右转，刚刚出生的小老鼠也要加入移动判定。
最后修正计数器，如果昏迷计数器大于 00 则减一。
否则如果休息计数器大于 00 也减一，如果此次休息计数器正好从 11 变为 00，则标记为繁殖后未动过。最后将年龄计数器加 11。
放代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int L,R,m,n,K,P,Limit;
int mousecnt;
bool debug;
int a[105][105];
int d[4]={1,2,4,8};
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool des[55][55];
bool mp[55][55][4];
int weaponp;
int Time;
int T;
struct Mouse{
	int age,deadtime,resttime,x,y,alive,turncnt;
	char forward,sex;
	int sexmove;
}mouse[100005];
struct Weapon{
	int op,t,x,y;
}weapon[100005];
char fwd(int x){
	if(x==0)return 'N';
	else if(x==1)return 'E';
	else if(x==2)return 'S';
	else return 'W';
}
int chg(char x){
	if(x=='N')return 0;
	else if(x=='E')return 1;
	else if(x=='S')return 2;
	return 3;
}
int left(int x){
	if(x!=0)return x-1;
	return 3;
}
int right(int x){
	if(x!=3)return x+1;
	return 0;
}
bool cmp(Weapon a,Weapon b){
	return a.t<b.t;
}
void buildmap(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=3;k>=0;k--){
				if(a[i][j]>=d[k]){
					a[i][j]-=d[k];
					mp[i][j][k]=1;
//					cout<<i<<" "<<j<<" "<<k<<endl;
				}
			}
		}
	}
}
void input(){
	cin>>L>>R>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	buildmap();
	cin>>K;
	for(int i=1;i<=K;i++){
		cin>>mouse[i].x>>mouse[i].y>>mouse[i].forward>>mouse[i].sex;
		mouse[i].age=6;
		mouse[i].deadtime=mouse[i].resttime=0;
		mouse[i].alive=1;
		mouse[i].turncnt=0;
		mouse[i].sexmove=0;
	}
	mousecnt=K;
	weaponp=1;
	cin>>P>>Limit;
	for(int i=1;i<=P;i++){
		cin>>weapon[i].op>>weapon[i].t>>weapon[i].x>>weapon[i].y;
		if(weapon[i].op==3)weapon[i].t+=3;
	}
	sort(weapon+1,weapon+P+1,cmp);
	cin>>Time;
}
void doweapon(){
		int debugcnt=0;
	while(weaponp<=P&&weapon[weaponp].t<=T){
		int x=weapon[weaponp].x,y=weapon[weaponp].y;
		if(weapon[weaponp].op==1){
			memset(des,0,sizeof(des));
			des[x][y]=1;
			bool f[10]={1,1,1,1,1};
			for(int i=1;i<=L;i++){
				if(x-i>=1&&mp[x-i+1][y][0]&&f[0]){
					des[x-i][y]=1;
				}
				else f[0]=0;
				if(y+i<=m&&mp[x][y+i-1][1]&&f[1]){
					des[x][y+i]=1;
				}
				else f[1]=0;
				if(x+i<=n&&mp[x+i-1][y][2]&&f[2]){
					des[x+i][y]=1;
				}
				else f[2]=0;
				if(y-i>=1&&mp[x][y-i+1][3]&&f[3]){
					des[x][y-i]=1;
				}
				else f[3]=0;
			}
			for(int i=1;i<=K;i++){
				if(mouse[i].alive==0)continue;
				if(des[mouse[i].x][mouse[i].y]){
				mouse[i].alive=0,debugcnt++;
//					if(T==30)cout<<mouse[i].x<<"|"<<mouse[i].y<<"\n";
				}
			}
		}
		else if(weapon[weaponp].op==2){
			for(int i=1;i<=K;i++){
				if(mouse[i].alive==0)continue;
				if((mouse[i].x-x)*(mouse[i].x-x)+(mouse[i].y-y)*(mouse[i].y-y)<=R*R){
					mouse[i].deadtime+=3;
				}
			}
		}
		else if(weapon[weaponp].op==3){
			for(int i=1;i<=K;i++){
				if(mouse[i].alive==0)continue;
				if(mouse[i].x==x&&mouse[i].y==y)mouse[i].alive=0,debugcnt++;
			}
		}
		else if(weapon[weaponp].op==4){
			for(int i=1;i<=K;i++){
				if(mouse[i].alive==0)continue;
				if(mouse[i].x==x&&mouse[i].y==y){
					if(mouse[i].sex=='X')mouse[i].sex='Y';
					else mouse[i].sex='X';
				}
			}
		}
		weaponp++;
	}
//		if(debug)cout<<debugcnt<<"|"<<endl;
}
int c[55][55][2];
bool sexed[55][55];
void checksex(){
	memset(c,0,sizeof(c));
	for(int i=1;i<=K;i++){
		if(!mouse[i].alive)continue;
		c[mouse[i].x][mouse[i].y][mouse[i].sex=='X']++;
		if(mouse[i].age<5||mouse[i].deadtime!=0||mouse[i].resttime!=0||mouse[i].sexmove==1)c[mouse[i].x][mouse[i].y][mouse[i].sex=='X']++;
	}
	for(int i=1;i<=K;i++){
		if(!mouse[i].alive)continue;
		if(mouse[i].deadtime!=0||mouse[i].resttime!=0||mouse[i].age<5)continue;
		if(c[mouse[i].x][mouse[i].y][0]==1&&c[mouse[i].x][mouse[i].y][1]==1){
			mouse[i].resttime=3;
		}
	}
}
void checkborn(){
	memset(sexed,0,sizeof(sexed));
	for(int i=1;i<=K;i++){
		if(!mouse[i].alive)continue;
		if(mouse[i].deadtime!=0||mouse[i].age<5)continue;
		if(mouse[i].resttime==1&&!sexed[mouse[i].x][mouse[i].y]){
			sexed[mouse[i].x][mouse[i].y]=1;
			for(int k=0;k<=3;k++){
				if(mp[mouse[i].x][mouse[i].y][k]){
//					if(debug==1)cout<<mouse[i].x<<" "<<mouse[i].y<<" "<<k<<"sfds\n";
					mouse[++K].age=0;
					mouse[K].alive=1;
					mouse[K].deadtime=mouse[K].resttime=0;
					mouse[K].x=mouse[i].x;
					mouse[K].y=mouse[i].y;
					mouse[K].forward=fwd(k);
					mouse[K].sex=(k%2==0?'X':'Y');
					mouse[K].turncnt=0;
					mouse[K].sexmove=0;
//					cout<<mouse[K].x<<"|"<<mouse[K].y<<" "<<mouse[K].forward<<endl;
				}
			}
		}
	}
}
void walk(){
	for(int i=1;i<=K;i++){
		if(!mouse[i].alive)continue;
		if(mouse[i].deadtime!=0||mouse[i].resttime!=0)continue;
		mouse[i].sexmove=0;
		if(mp[mouse[i].x][mouse[i].y][chg(mouse[i].forward)]){
//			cout<<i<<"A"<<endl;
			mouse[i].x+=dx[chg(mouse[i].forward)];
			mouse[i].y+=dy[chg(mouse[i].forward)];
		}
		else{
//			if(mouse[i].x==1&&mouse[i].y==3)cout<<left(chg(mouse[i].forward))<<" "<<mp[mouse[i].x][mouse[i].y][3]<<"s\n";
			if(mp[mouse[i].x][mouse[i].y][left(chg(mouse[i].forward))]){
				if(mp[mouse[i].x][mouse[i].y][right(chg(mouse[i].forward))]){
					mouse[i].turncnt++;
					if(mouse[i].turncnt%2==1){
						mouse[i].forward=fwd(left(chg(mouse[i].forward)));
					}
					else{
						mouse[i].forward=fwd(right(chg(mouse[i].forward)));
					}
				}
				else{
					mouse[i].forward=fwd(left(chg(mouse[i].forward)));
				}
			}
			else if(mp[mouse[i].x][mouse[i].y][right(chg(mouse[i].forward))]){
//				if(mouse[i].x==1&&mouse[i].y==3)cout<<"ADSAD\n";
				mouse[i].forward=fwd(right(chg(mouse[i].forward)));
			}
			else{
//				if(mouse[i].x==1&&mouse[i].y==3)cout<<"ADSAD\n";
				mouse[i].forward=fwd(right(chg(mouse[i].forward)));
			}
		}
	}
}
void downcnt(){
	for(int i=1;i<=K;i++){
		if(!mouse[i].alive)continue;
		if(mouse[i].deadtime>0)mouse[i].deadtime--;
		else if(mouse[i].resttime>0){
			mouse[i].resttime--;
			if(mouse[i].resttime==0)mouse[i].sexmove=1;
		}
		else mouse[i].age++;
	}
}

//int debug(char x){
//	if(x=='N')return 1;
//	else if(x=='E')return 2;
//	else if(x=='S')return 4;
//	else return 8;
//}
int main(){
//	freopen("mouse.in","r",stdin);
//	freopen("test1.out","w",stdout);
	input();
	for(;T<=Time;T++){
		if(T==30)debug=1;
		else debug=0;
		doweapon();
//		cout<<"ENDWEAPON\n";
		checkborn();
		checksex();
		walk();
		downcnt();
//		if(debug)cout<<"P\n";
		int C=0;
		for(int i=1;i<=K;i++){
			if(!mouse[i].alive)continue;
//			cout<<mouse[i].x<<" "<<mouse[i].y<<" "<<debug(mouse[i].forward)<<"\n";
			C++;
		}
		if(C>Limit){
			cout<<"-1";
			return 0;
		}
//		cout<<T<<endl;
//		cout<<C<<endl;
	}
	int ans=0;
	for(int i=1;i<=K;i++){
		if(!mouse[i].alive)continue;
//		cout<<mouse[i].x<<" "<<mouse[i].y<<" "<<mouse<<"\n";
		ans++;
	}
	cout<<ans;
	return 0;
}
//武器>繁殖>出生>行动=成长。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...