题解：P13964 [VKOSHP 2024] Colony of Bacteria

UNNN · 2025-09-04 23:44:19 · 题解

题意

第一秒时网格中有一个细菌，随后在第偶数秒，每个细菌向八方扩张一格，在第奇数秒，每个细菌向四方(上下左右)扩张一格，问第 k 秒有多少个细菌。

思路

找规律的题，第一秒是 1 个，第二秒是 1 + 8 = 9 个。

对于奇数秒，通过观察题目下方的表格，我们可以发现：设当前为第 i 秒，观察表格能够注意到相对于上一秒存在几个仅横向纵向复制的细菌(如下图)。我们仅考虑单边，可以发现每个单边恰好复制了 i 个细菌。由于存在 4 个单边，所以横纵复制的细菌总数为 4i。

再来看四个角，可以发现第三秒时四个角落没有细菌，第五秒时每个角落间隔了一个细菌。以此类推，第 i 秒的每个角落会间隔 \lfloor \frac{i}{2} \rfloor - 1 个细菌。由于存在 4 个角，所以角落总共会新增 4 \times (\lfloor \frac{i}{2} \rfloor - 1) 个细菌。

所以对于奇数秒，总共会增加 4 \times (i + \lfloor \frac{i}{2} \rfloor - 1) 个细菌。

对于偶数秒，可以发现：第四秒时，每个仅横向或纵向的单边相比于上一秒的单边要多复制了两个细菌(如下图)，也就是说，假设当前为第 i 秒，那么每个单边将复制 i + 1 个细菌。由于存在 4 个单边，所以横纵复制总数为 4 \times (i + 1) 个。

再看四个角，可以发现第四秒时，单边的内部的每个角落多出了 1 个细菌，同样我们可以在该图中推出第六秒的细菌布局，可发现所有角落的 6 能够恰好将下图中剩余的空格填满，也就是每个角落会多出 3 个细菌。由此，可以推断出第 i 秒时，每个角落会多出 i - 3 个细菌。由于存在 4 个角落，所以角落总共新增 4 \times (i - 3) 个细菌。

所以对于偶数秒，总共会增加 4 \times (2i - 2) 个细菌。

从第一秒遍历到第 k 秒，每秒进行计算，即可求出第 k 秒的细菌数。

Code

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll k, ans = 0LL, add = 0LL;
int main()
{
    scanf("%lld", &k);
    for(ll i = 1;i <= k;i++){
        // 两个特判
        if(i == 1){
            ans = 1LL;
            add = 1LL;
            continue;
        }
        if(i == 2){
            ans = 9LL;
            add = 8LL;
            continue;
        }

        if(i & 1) add = (i + (i >> 1LL) - 1) << 2LL; // 奇数秒
        else add = ((i << 1LL) - 2) << 2LL; // 偶数秒
        ans = ans + add; // 累加
    }
    printf("%lld", ans); // 输出
    return 0; // 结束 (｡･ω･｡)
}