洛谷P15350题解

whatareyoudoing

2026-03-17 12:48:11

发布于：福建

9阅读

0回复

0点赞

洛谷P15350题解

为什么洛谷不可以发P15350题解？@kkksc03

回归正题

大家还记得那场推迟了很久的比赛吧

没错，是 COCI 2025/2026 #4 Unofficial Mirror

第一题是《僵尸启示录》

题目传送门

宝贵的标程当然要放在最后。
如果有更好的方法，欢迎各路大佬指导！

现在,我们来看题吧。

有 $m$ 个僵尸和 $k$ 个炸弹，每个炸弹在离窝 $x$ 米，爆炸半径为 $r$ 米，在 $t$ 秒爆炸，僵尸窝离城市 $n+1$ 米。

题目问：有几个僵尸会进入城市？

我们可以定义一个布尔数组 $b$ ，来存现在某个位置是否有僵尸, $true$ 表示有， $false$ 表示没有。

~~僵尸行进的代码我相信你们会写~~

新建一个变量 $m$ ，存未出发的僵尸的数量，如果 $m$ 为 $0$ ，代表所有的僵尸都出发了。

每一次僵尸前进前判断，如果 $b[n]=true$ (等于号不表示赋值)，就把 $b[n]$ 赋值为 $false$ ,存答案的变量自加。

接下来使用 $for$ 循环和 $swap$ 函数，调换数组 $b$ 中的数据。

伪代码如下(cpp)：

/*
变量意思：

数组：
b 表示一个位置有没有僵尸

普通变量：
ans 存答案的变量
n   道路的最右边
m   未出发的僵尸数量

*/

if(b[n]){   //如果僵尸进入城市
  ans++;    //答案自加
  b[n]=0;
}
//每个僵尸前进1步
for(int j=n;j>=2;j--) swap(b[j],b[j-1]);

if(m!=0){   //如果有僵尸未出发
  b[1]=1;   //僵尸出发
  m--;      //未出发僵尸数量减一
}

然后用一个变量 $i$ ，表示时间。如果在这个时间有炸弹刚好爆炸，那么，就把爆炸范围内的僵尸炸没（还记得之前定义的布尔数组 $b$ 吗，就是把爆炸范围里的所有为 $1$ 的值赋值为 $0$ ，表示僵尸被炸没）。如果没有炸弹了，那么剩下的僵尸和未出发的僵尸一定会进入城市，就加入我们的答案。

~~判断炸弹是否爆炸的代码也简单，我相信你们也会写~~

如果有炸弹爆炸，新建两个变量 $L$ 和 $R$ ，表示炸弹爆炸的最左范围和最右范围，再用 $for$ 循环遍历所有地方，把这个地方的所有有僵尸地方全部清空。

对了！记得把炸弹时间按从小到大的顺序排序，不然ＷＡ了别怪我！还有，还要防止数组越界，ＲＥ了别怪我没提醒你。

伪代码如下(cpp)：

/*
变量意思：
结构体：
Book.x 炸弹安放位置
Book.r 炸弹爆炸半径
Book.t 炸弹爆炸时间

普通变量：
i  时间
in 指向第in个炸弹
n  道路的最右边
L  炸弹爆炸的最左范围
R  炸弹爆炸的最右范围
*/

//如果这个时间单位有炸弹可以爆炸，进入循环
while(Book[in].t==i){
			int L=Book[in].x-Book[in].r;
			int R=Book[in].x+Book[in].r;
			//炸弹爆炸的范围

			if(L<=0) L=1;
			if(R>n) R=n;
			//这两个if是防止数组越界，RE了别怪我没提醒你

			for(int j=L;j<=R;j++) b[j]=0;
			//清空僵尸

			in++;
			//指向下一个炸弹位置
		}

还有一点要注意，僵尸先前进，炸弹再爆炸，不然会ＷＡ(~~别问我怎么知道的~~)。

标程

标程第25 ~ 28行用的是冒泡排序，因为冒泡排序代码短，而且题目使用冒泡排序不会超时，所以作者就使用冒泡排序了(~~其实是忘记快排和归排怎么写了~~)

其他关于标程不好的地方，欢迎各路大佬指教。谢谢大家！

码风还好，不喜勿喷。

标程（cpp）：

#include<bits/stdc++.h>
using namespace std;

bool b[205];
void sswap(int,int);
struct Book;
struct Book{
	int x;
	int r;
	int t;
}Book[205];

void sswap(int a,int b){
	swap(Book[a].r,Book[b].r);
	swap(Book[a].x,Book[b].x);
	swap(Book[a].t,Book[b].t);
}

int main(){
	int n,k,m,maxtime(0),ans(0);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;i++){
		scanf("%d%d%d",&Book[i].x,&Book[i].r,&Book[i].t);
		maxtime=max(maxtime,Book[i].t);
	}
	for(int i=1;i<=k;i++)
		for(int j=k;j>i;j--)
		if(Book[j].t<Book[j-1].t)
			sswap(j,j-1);
	int in=1;
	for(int i=1;i<=maxtime;i++){
		if(b[n]){
			ans++;
			b[n]=0;
		}
		for(int j=n;j>=2;j--) swap(b[j],b[j-1]);
		if(m!=0){
			b[1]=1;
			m--;
		}
		while(Book[in].t==i){
			int L=Book[in].x-Book[in].r,R=Book[in].x+Book[in].r;
			if(L<=0) L=1;
			if(R>n) R=n;
			for(int j=L;j<=R;j++) b[j]=0;
			in++;
		}
	}
	for(int i=1;i<=n;i++) if(b[i]) ans++;
	printf("%d",ans+m);
	return 0;
}