专栏文章

题解：P13964 [VKOSHP 2024] Colony of Bacteria

cchenxi797
P13964题解参与者 5已保存评论 7

文章操作

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

当前评论
7 条
当前快照
1 份
快照标识符
@minze45y
此快照首次捕获于
2025/12/02 10:50
3 个月前
此快照最后确认于
2025/12/02 10:50
3 个月前
查看原文

P13964 [VKOSHP 2024] Colony of Bacteria 题解

题意

现有一个无限大的网格，第 11 秒时网格中央有一个细菌。
此后从第 22 秒开始，在奇数秒时，细菌会向相邻的四个方向扩散；在第偶数秒时，细菌会向相邻的八个方向扩散。
如果将要扩散的网格原本没有细菌，那么细菌的数量就会增加 11。
如图，网格上的数字表示细菌扩散至此网格的秒数。
555555444445544333445543222345543212345543222345544333445544444555555\begin{array}{ |c|c|c|c|c|c|c|c|c| } \hline & & 5 & 5 & 5 & 5 & 5 & & \\ \hline & 5 & 4 & 4 & 4 & 4 & 4 & 5 & \\ \hline 5 & 4 & 4 & 3 & 3 & 3 & 4 & 4 & 5 \\ \hline 5 & 4 & 3 & 2 & 2 & 2 & 3 & 4 & 5 \\ \hline 5 & 4 & 3 & 2 & 1 & 2 & 3 & 4 & 5 \\ \hline 5 & 4 & 3 & 2 & 2 & 2 & 3 & 4 & 5 \\ \hline 5 & 4 & 4 & 3 & 3 & 3 & 4 & 4 & 5 \\ \hline & 5 & 4 & 4 & 4 & 4 & 4 & 5 & \\ \hline & & 5 & 5 & 5 & 5 & 5 & & \\ \hline \end{array}

思路

分类讨论，在秒数为奇数和偶数的情况下分别找规律。
当秒数为奇数时，观察下图的情况。
其中红色网格为前一秒的细菌扩散状态，绿色网格为当前秒细菌扩散状态。
不难发现，在第 ii 秒时，每个细菌只向周围扩散了一格，即增加的细菌数为 4i4i。
再观察下图的情况。
可以看到，某些细菌不光只扩散一个，还将拐角处的缝隙填满了。每个角落会增加 ⌊i2⌋−1\lfloor \frac{i}{2} \rfloor - 1 个细菌，所以 44 个角落增加的细菌数为 4×(⌊i2⌋−1)4 \times (\lfloor \frac{i}{2} \rfloor - 1)。
所以，奇数秒时细菌增加的数量为 4i+4×(⌊i2⌋−1)4i + 4 \times (\lfloor \frac{i}{2} \rfloor - 1)。
当秒数为偶数时，观察下图的情况。
当第 ii 秒时，每边上的细菌会扩散出 i+1i + 1 个细菌，所以四边增加的细菌数量为 4×(i+1)4 \times (i + 1)。
在四个角中，每扩散 33 层，每个角落就会多扩散 11 个细菌，所以四个角落里增加的细菌数量为 4×(i−3)4 \times (i - 3)。
所以偶数秒时增加的细菌数量为 4×(i+1)+4×(i−3)4 \times (i + 1) + 4 \times (i - 3)。

代码

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
	int k,ans = 1;
	cin >> k;
	for (int i = 2;i <= k;i++)
	{
		if (i & 1) ans += 4 * i + 4 * (i / 2 - 1);
		else ans += 4 * (i + 1) + 4 * (i - 3);
	}
	cout << ans;
}

评论

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

正在加载评论...