题解：P13964 [VKOSHP 2024] Colony of Bacteria

题意

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

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

CPP

#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; // 结束 (｡･ω･｡)
}

题解：P13964 [VKOSHP 2024] Colony of Bacteria

文章操作

题意

思路

Code

相关推荐

评论

题解：P13964 [VKOSHP 2024] Colony of Bacteria