题解：P13964 [VKOSHP 2024] Colony of Bacteria

chenxi797 · 2025-09-07 13:42:34 · 题解

P13964 [VKOSHP 2024] Colony of Bacteria 题解

题意

现有一个无限大的网格，第 1 秒时网格中央有一个细菌。

此后从第 2 秒开始，在奇数秒时，细菌会向相邻的四个方向扩散；在第偶数秒时，细菌会向相邻的八个方向扩散。

如果将要扩散的网格原本没有细菌，那么细菌的数量就会增加 1。

如图，网格上的数字表示细菌扩散至此网格的秒数。

思路

分类讨论，在秒数为奇数和偶数的情况下分别找规律。

当秒数为奇数时，观察下图的情况。

其中红色网格为前一秒的细菌扩散状态，绿色网格为当前秒细菌扩散状态。

不难发现，在第 i 秒时，每个细菌只向周围扩散了一格，即增加的细菌数为 4i。

再观察下图的情况。

可以看到，某些细菌不光只扩散一个，还将拐角处的缝隙填满了。每个角落会增加 \lfloor \frac{i}{2} \rfloor - 1 个细菌，所以 4 个角落增加的细菌数为 4 \times (\lfloor \frac{i}{2} \rfloor - 1)。

所以，奇数秒时细菌增加的数量为 4i + 4 \times (\lfloor \frac{i}{2} \rfloor - 1)。

当秒数为偶数时，观察下图的情况。

当第 i 秒时，每边上的细菌会扩散出 i + 1 个细菌，所以四边增加的细菌数量为 4 \times (i + 1)。

在四个角中，每扩散 3 层，每个角落就会多扩散 1 个细菌，所以四个角落里增加的细菌数量为 4 \times (i - 3)。

所以偶数秒时增加的细菌数量为 4 \times (i + 1) + 4 \times (i - 3)。

代码

#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;
}